Гуманитарные основы комбинаторных алгоритмов

Иван Гаврюшин

Книга о гуманитарных основах комбинаторных алгоритмов представляет собой сборник статей и заметок, опубликованных в Интернете автором в период с 2015 по 2022 год. Книга предназначена для программистов с гуманитарным образованием и широкого круга читателей. Издание создано на основе личного блога автора на сайте Хабрахабр.

Игра с комбинаторными алгоритмами

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

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

Однажды вечером после чтения книжек о путешествиях, — кажется, это были знаменитое «Путешествие из Петербурга в Москву» Радищева и «Тарантасъ» Владимира Соллогуба — я сел смотреть лекцию об алгоритме Дейкстры. Смотрел, рисовал что-то на бумажке и нарисовал ориентированный граф. После некоторых размышлений мне стало интересно, как бы я реализовал алгоритм поиска всех путей из одной начальной точки (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

Дополнение

В качестве дополнения приведу описание полученного алгоритма более кратко: ребра ориентированного графа выписаны в отдельные массивы в порядке возрастания. Т.е. вершины графа и рёбра упорядочены. Это обязательное условие. До начала алгоритма находим первый путь, который с учетом первого условия будет с наименьшими именами вершин. Способ нахождения не особенно важен.

Описание для проверки на бумаге

На входе первый найденный путь x=abdef:

— Двигаемся справа налево по массиву х, выделяем два соседних элемента (кроме последнего) abd [e] f, левый (d) используем в качестве указателя на массив с вершиной, правый (e) в качестве указателя на элемент этого массива.

Ищем элемент в d после е, если он есть, убираем в x справа от e все элементы. Получаем в x=abde. Заменяем правый элемент (е) на найденный элемент.

— Дописываем (вторым циклом) правую часть от элемента (или индекса правого элемента), который был заменен и до последнего элемента (f). В этом цикле требуется брать всегда массивы с 0 индексом, так как массивы упорядочены по условию. В данном случае мы сразу получили в правой части последний элемент x=abdf, поэтому второй цикл сработает вхолостую.

— После формирования правой части возвращаемся к обходу массива справа налево.

Отсутствие элементов в первой вершине (массив а) — условие выхода из алгоритма.

Тот же код без функций и рекурсии, первый путь в x задан:

<?php

//Массивы ребер

$a=array (’b’,’c’,’d’);

$b=array (’d’,’e’,’f’);

$c=array (’d’,’e’,’f’);

$d=array (’e’);

$e=array (’f’);

//Первый путь

$x=’abdef’;

print $x;

print '<br>»;

$j=strlen ($x);

while ($j!=0) {

Конец ознакомительного фрагмента.