如何从 Prolog 中的 selection select 最短路径

Question

我是一名 prolog 初学者，有以下代码可以找出从一个给定节点到另一个节点的所有可能路径。每条边在本质上都是双向的，这一点需要注意。

nodeLink(1,2,4).
nodeLink(1,3,10).
nodeLink(1,5,2).

nodeLink(2,1,4).
nodeLink(2,5,1).
nodeLink(2,4,6).
nodeLink(2,6,1).

nodeLink(3,1,10).
nodeLink(3,5,2).
nodeLink(3,4,1).

nodeLink(4,3,1).
nodeLink(4,5,8).
nodeLink(4,2,6).

nodeLink(5,1,2).
nodeLink(5,2,1).
nodeLink(5,3,2).
nodeLink(5,4,8).

nodeLink(6,2,1).


path([B | BRest], B, [B | BRest], Length, Length).
path([A | ARest], B, Path, CurrentLength, Length) :-
    nodeLink(A, C, X),
    \+member(C, [A | ARest]),
    NewLength is CurrentLength + X,

    path([C, A | ARest], B, Path, NewLength, Length).

all_paths(Start, End) :-
    path([Start], End, Path, 0, Length),
    reverse(Path, RevPath),
    write('Path: '),
    printPath(RevPath),
    write(' with a cost of '),
    writeln(Length),
    fail.

printPath([]).
printPath([X]) :-
    !,
    write(X).
printPath([X|Xrest]) :-
    write(X),
    write(', '),
    printPath(Xrest).

例如：

?- all_paths(6,3).

打印出来：

Path: 6, 2, 1, 3 with a cost of 15
Path: 6, 2, 1, 5, 3 with a cost of 9
Path: 6, 2, 1, 5, 4, 3 with a cost of 16
Path: 6, 2, 5, 1, 3 with a cost of 14
Path: 6, 2, 5, 3 with a cost of 4
Path: 6, 2, 5, 4, 3 with a cost of 11
Path: 6, 2, 4, 3 with a cost of 8
Path: 6, 2, 4, 5, 1, 3 with a cost of 27
Path: 6, 2, 4, 5, 3 with a cost of 17
false.

我将如何为给定的一对节点选择 'shortest' 路径？谢谢

Answer 1

通常，在 Prolog 中，您不想使用 write 和失败驱动循环来显示所有解决方案。一个规范的方法是让每个解决方案都成功的谓词（就像你的 path/5 谓词一样），然后使用 findall/3 或 bagof/3 或 setof/3 来收集所有的列表中的解决方案。 setof/3 具有消除重复项并对生成的集合进行排序的好处。

这是 [prolog] shortest path directed graph 上的 Whosebug 搜索。这在本网站上已被多次提及，我不想只选择其中之一。我没有看到使用 setof/3 的解决方案，所以这里有一个采用该方法的解决方案。

我将使用您现有的 path/5 定义。由于路径集合在设计上是唯一的，因此使用 setof/3 将比使用 findall/3 后跟 msort/2 稍有改进，您至少可以在其中一个链接中找到解决方案。这里的想法是创建一个 Cost-Path 形式的解决方案列表，这些解决方案按 Cost 排序。然后您需要从列表中选择成本最低的元素，这是排序后的第一个元素。

shortest_path(Start, End, ShortestPath, ShortestLength) :-
    setof(Length-Path, path([Start], End, Path, 0, Length), [ShortestLength-ShortestPath|_]).

如果你想打印出你的列表，你可以使用 maplist:

print_path(Cost-Path) :-
    write('Path: '),
    write(Path),
    write(' with a cost of '),
    write(Cost), nl.

print_paths(CostPaths) :-
    maplist(print_path, CostPaths).

其中 CostPaths 是上面执行的 setof/3 的结果。

如何从 Prolog 中的 selection select 最短路径

How to select the shortest path from a selection in Prolog

prolog

shortest-path