Завершить данную заметку хотел бы эпилогом с рифмой:
Комбинаторика! Как прекрасна ведь она! Но все же разума игра!
Post Scriptum
Для примера возьмём две фразы. «Am I like a god?» и «Am I like a dog?»
Пример того, как можно связать атомизм Демокрита и комбинаторику. Мы переставили буквы в одном слове, осуществили комбинаторный прием перестановку и получили новый смысл вопроса. Более того, оба вопроса приобрели для нас религиозно-философский смысл. Для самой комбинаторики наше действие, может быть, не имеет смысла, оно похоже на механическое, но оно и результат, который оно даёт, имеет смысл для нас, оно имеет смысл для нас как для волевого, разумного, чувствующего субъекта, иначе говоря для состояния самого нашего духа.
Игра с комбинаторными алгоритмами
3) Путешествие из Москвы в Казань через Санкт-Петербург или процесс разработки алгоритма поиска всех путей
Данный материал публикуется с расчетом на начинающих программистов и неспециалистов
Однажды вечером после чтения книжек о путешествиях, кажется, это были знаменитое «Путешествие из Петербурга в Москву» Радищева и «Тарантасъ» Владимира Соллогуба я сел смотреть лекцию об алгоритме Дейкстры. Смотрел, рисовал что-то на бумажке и нарисовал ориентированный граф. После некоторых размышлений мне стало интересно, как бы я реализовал алгоритм поиска всех путей из одной начальной точки (a) в какую-то другую единственную конечную точку (f) на ориентированном графе. Я уже было начал читать об алгоритмах поиска в глубину и ширину, но мне
подумалось, что интереснее было бы попробовать «изобрести» алгоритм заново, часто ведь при таком подходе можно получить интересную модификацию уже известного алгоритма. Заодно я поставил себе несколько условий: 1) не использовать литературу; 2) использовать нерекурсивный подход; 3) хранить ребра в отдельных массивах, без вложенности. Далее постараюсь описать процесс поиска алгоритма и его реализации, как обычно на PHP.
Сам граф получился такой:
В общем: на входе ориентированный граф с шестью вершинами, задача найти все пути из а в f без рекурсии и с минимальными затратами средств.
Ребра хранятся в нескольких массивах, имя массива вершина:
Чтобы получить первый путь, я решил пройтись по нулевым индексам каждого массива и склеить их в одну строку х (в этой переменной на каждом этапе будет хранится найденный путь). Но как это сделать с минимальными затратами?! Мне показалось, что самым простым вариантом будет ввести еще один массив инициализирующий.
В массиве int все элементы, которые есть в графе в обратном порядке.
$int=array (f,e,d,c,b,a);
Тогда получить первый путь очень просто, достаточно пройтись циклом по всем массивам, добавлять в х новое значение с помощью конкатенации, и на каждом этапе использовать элемент из предыдущего массива в качестве указателя на следующий массив.
Этот стиль немного напоминает bash, но код выглядит довольно понятным:
Можем вывести его на экран и заняться непосредственно самим алгоритмом, так как все, что было выше, это только подготовительная часть. По идее от нее можно было бы избавиться, но я ее оставляю и публикую, чтобы был лучше понятен ход мысли.
$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:
В качестве дополнения приведу описание полученного алгоритма более кратко: ребра ориентированного графа выписаны в отдельные массивы в порядке возрастания. Т.е. вершины графа и рёбра упорядочены. Это обязательное условие. До начала алгоритма находим первый путь, который с учетом первого условия будет с наименьшими именами вершин. Способ нахождения не особенно важен.
Описание для проверки на бумаге
На входе первый найденный путь x=abdef:
Двигаемся справа налево по массиву х, выделяем два соседних элемента (кроме последнего) abd [e] f, левый (d) используем в качестве указателя на массив с вершиной, правый (e) в качестве указателя на элемент этого массива.
Ищем элемент в d после е, если он есть, убираем в x справа от e все элементы. Получаем в x=abde. Заменяем правый элемент (е) на найденный элемент.
Дописываем (вторым циклом) правую часть от элемента (или индекса правого элемента), который был заменен и до последнего элемента (f). В этом цикле требуется брать всегда массивы с 0 индексом, так как массивы упорядочены по условию. В данном случае мы сразу получили в правой части последний элемент x=abdf, поэтому второй цикл сработает вхолостую.
После формирования правой части возвращаемся к обходу массива справа налево.
Отсутствие элементов в первой вершине (массив а) условие выхода из алгоритма.
Тот же код без функций и рекурсии, первый путь в x задан: