如何从Prolog中的选择中选择最短路径

Question

我是一位序言初学者，具有以下代码，列出了从一个给定节点到另一个节点的所有可能路径。每个边缘本质上都是双向的，需要注意。

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.

我将如何为给定的一对节点选择“最短”​​路径？谢谢

Answer 1

[通常，在Prolog中，您不想使用write和故障驱动的循环来显示所有解决方案。规范的方法是让每个解决方案都成功的谓词（如path/5谓词所做的那样），然后使用findall/3或bagof/3或setof/3将所有解决方案收集在列表中。 setof/3的优点是消除重复，并对所得集合进行排序。

这里是[prolog] shortest path directed graph上的堆栈溢出搜索。这个站点已经报道了很多次，我不想只选择其中之一。我没有看到使用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|_]).