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

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

В Visual Prolog первым делом надо описать типы данных, т.к. он является языком с явной типизацией:

domains
node_d = string
edge_d = edge(node_d, node_d)
way_d = edge_d*
ways_d = way_d*

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

Затем нужно описать прототипы используемых функций в секции predicates. В решении применяются стандартные функции member и append для поиска дуги в пути и соединения списков путей:

nondeterm member(edge_d, way_d)
append(ways_d, ways_d, ways_d)

Граф должен задаваться дугами (edge_p), при этом сама по себе дуга является ориентированной, если требуется определить неориентированный граф — можно применить вспомогательную функцию (way_d_exist), выполняющую проверку наличия прямой или обратной дуги:

nondeterm edge_p(edge_d)
nondeterm way_d_exist(edge_d)

Функция step формирует новый участок пути добавляя дугу к существующему пути:
nondeterm step(node_d, way_d, way_d)

Функция path принимает начальную вершину и список начальных путей, возвращает найденный путь, функция bfs_start запускает функцию path инициализируя аргументы:

path(node_d, ways_d, way_d)
bfs_start(node_d, node_d, way_d)

В разделе clauses необходимо разместить реализацию функций и задать граф. Граф представляется в виде набора дуг:

edge_p(edge("a", "b")).
edge_p(edge("b", "c")).
edge_p(edge("c", "d")).
edge_p(edge("a", "e")).
edge_p(edge("e", "d")).

Функция way_d_exist принимает дугу и выполняет ее поиск. Если дуга не найдена — ищет дугу, направленную в обратную сторону:

way_d_exist(edge(From, To)):-
edge_p(edge(From, To)); edge_p(edge(To, From)).

Функция step может как непосредственно обращаться к дугам (если граф надо рассматривать как ориентированный), так и к функции way_d_exist:

step(From, PrevSteps, [edge(From, To)|PrevSteps]):-
way_d_exist(edge(From, To)),
not(member(edge(From, To), PrevSteps)).

Функция path работает аналогично реализации на SWI Prolog и также возвращает перевернутый путь, но собирает не вершины, а дуги, поэтому для ее запуска требуется собрать все дуги, выходящие из стартовой вершины. Такая работа выполняется функцией bfs_start:

path(Finish, [[edge(From, Finish) | PathPart] | _], [edge(From, Finish) | PathPart]):-!.
path(Finish, [HeadPath | ProcList], Path):-
HeadPath = [edge(_From, To) | _PathPart],
findall(NewHeadPath, step(To, HeadPath, NewHeadPath), NewHeadPaths),
append(ProcList, NewHeadPaths, NewProcList), !,
path(Finish, NewProcList, Path).  
bfs_start(Start, Finish, ResultPath):-
findall(Path, step(Start, [], Path), InitPaths),
path(Finish, InitPaths, ResultPath).