Ответ в теме: Поиск кратчайшего пути в графе (Prolog)

      Комментарии к записи Ответ в теме: Поиск кратчайшего пути в графе (Prolog) отключены
#2381

Функция step принимает исходную вершину и список посещенных вершин. Выбирает дугу, ведущую из текущей вершины в узел, который не был ранее посещен (для проверки используется встроенная функция member). Если такая дуга найдена – ее начальный и конечный узел добавляется в список посещенных вершин, результат возвращается в третьем аргументе. Функция является недетерменированной, т.е. ей можно перебрать все варианты дуг из стартовой вершины.

Правило path\4 возвращает перевернутый путь (тут путь – последовательность вершин, а не дуг). Правило формирует двухуровневый список путей из начальной вершины в каждый посещенный узел. Правило выбирает смежные вершины, подобно тому, как это выполнялось в правиле add_adj. Из первого пути списка выделяется первый элемент (Х) и остаток пути (PathPart), которые передаются правилу step\3. За счет использования предикатов findall и step формируется список необработанных вершин, смежных со стартовой. Этот список присоединяется к очереди еще не обработанных вершин (ProcList) и передается в path\4.
Процесс повторяется пока первого списка-пути не совпадет с конечной вершиной (в этом случае правило вернет перевернутый путь) или не кончится список путей (при этом правило завершится неудачей).

В связи с тем, что вершины добавляются в начало списка, представляющего собой искомый кратчайший путь, он окажется перевернутым. Функция path/2 выполняет вызов path/4, инициализируя список посещенных вершин стартовой и переворачивает результирующий путь.

Важно также то, что функция path\4 является недетерменированной (изменить это можно добавив оператор отсечения в обработку случая, когда путь найден), за счет этого можно найти кратчайшие пути во все остальные вершины.

Вложения: