Путешествие из Москвы в Казань через Санкт-Петербург или процесс разработки алгоритма поиска всех путей

Данный материал публикуется с расчетом на начинающих программистов и неспециалистов...

Однажды вечером после чтения книжек о путешествиях, — кажется, это были знаменитое «Путешествие из Петербурга в Москву» Радищева и «Тарантасъ» Владимира Соллогуба — я сел смотреть лекцию об алгоритме Дейкстры. Смотрел, рисовал что-то на бумажке и нарисовал ориентированный граф. После некоторых размышлений мне стало интересно, как бы я реализовал алгоритм поиска всех путей из одной начальной точки (a) в какую-то другую единственную конечную точку (f) на ориентированном графе. Я уже было начал читать об алгоритмах поиска в глубину и ширину , но мне подумалось, что интереснее было бы попробовать «изобрести» алгоритм заново, часто ведь при таком подходе можно получить интересную модификацию уже известного алгоритма. Заодно я поставил себе несколько условий: 1 ) не использовать литературу; 2) использовать нерекурсивный подход; 3) хранить ребра в отдельных массивах, без вложенности. Далее постараюсь описать процесс поиска алгоритма и его реализации, как обычно на PHP.

Сам граф получился такой:

В общем: на входе ориентрованный граф с шестью вершинами, задача найти все пути из а в f без рекурсии и с минимальными затратами средств.

Ребра хранятся в нескольких массивах, имя массива — вершина:

$a=array('b','c','d');
$b=array('d','e','f');
$c=array('d','e','f');
$d=array('e','f');
$e=array('f');

Чтобы получить первый путь, я решил пройтись по нулевым индексам каждого массива и склеить их в одну строку х (в этой переменной на каждом этапе будет хранится найденный путь). Но как это сделать с минимальными затратами?! Мне показалось, что самым простым вариантом будет ввести еще один массив — инициализирующий.
В массиве int все элементы, которые есть в графе в обратном порядке.

$int=array('f','e','d','c','b','a'); 

Тогда получить первый путь очень просто, достаточно пройтись циклом по всем массивам,
добавлять в х новое значение с помощью конкатенации, и на каждом этапе использовать элемент из предыдущего массива в качестве указателя на следующий массив.

Этот стиль немного напоминает bash, но код выглядит довольно понятным:

	$x='a';
	$z=$a[0];
while (1) {
	$x.=$z; 
	$z=${$z}[0];
	if ($z == 'f') {$x.=$z;  break ;}
}

И так, мы получили первый путь x=abdef .

Можем вывести его на экран и заняться непосредственно самим алгоритмом, так как все, что было выше, — это только подготовительная часть. По идее от нее можно было бы избавиться, но я ее оставляю и публикую, чтобы был лучше понятен ход мысли.

Выводим на экран первый путь и запускаем первую функцию.

print $x;
print '<br>';
search_el ($x,$a,$b,$c,$d,$e);

Сам алгоритм фактически сводится к двум циклам, которые вынесены в отдельные функции.
Первая функция принимает полученный ранее первый путь x. Далее в цикле осуществляется обход x справа налево. Мы ищем два элемента, один из которых будет
работать в качестве указателя на массив, другой (правый, тут только стоит помнить, что массив перевернут) в качестве указателя на элемент массива. С помощью array_search найдем ключ элемента и проверим, есть ли что-нибудь в данном массиве после него. Если есть, то заменим элемент на найденный, но перед этим отрежем хвост (для этого нужен substr). Замену можно организовать и по другому:

function search_el($x, $a, $b, $c, $d, $e)
	{
	$j = strlen($x);
	while ($j != 0)
		{
		$j--;
		if (isset(${$x[$j - 1]})) 
         $key = array_search($x[$j], ${$x[$j - 1]});
		if (${$x[$j - 1]}[$key + 1] != '')
			{
			$x = substr($x, 0, $j);
			$x.= ${$x[$j - 1]}[$key + 1];
			new_way_search($x, $a, $b, $c, $d, $e);
			break;
			}
		}
	}

Условие с isset нужно, чтобы интерпретатор не выбрасывал предупреждение. К самому алгоритму оно отношения не имеет. Если никаких элементов в массивах найдено не было, то алгоритм завершится, но если все-таки чудо свершилось, то переходим в новую функцию, суть которой крайне проста — дописать хвост к x, вывести на экран и… «дорисовать восьмерку» или петлю — вернуться в функцию, из которой мы пришли, но уже с новым значением x:

function new_way_search($x, $a, $b, $c, $d, $e)
	{
	$z = $x[strlen($x) - 1];
	$z = ${$z}[0];

	while (1)
		{
		$x.= $z;
		if ($x[strlen($x) - 1] == 'f') break;

		if ($z == 'f')
			{
			$x.= $z;
			break;
			}

		$z = ${$z}[0];
}
	echo $x;
	echo '<br />';
	search_el($x, $a, $b, $c, $d, $e);
}

Результат работы алгоритма для графа, что на рисунке выше:

abdef
abdf
abef
abf
acdef
acdf
acef
acf
adef
adf

На этом все! Надеюсь, данная заметка будет кому-нибудь полезной.

Автор: Ivan Gavryushin

Источник