如何使用SWI Prolog找到加权有向图的唯一最短路径？

Question

这是我在Prolog课上所做的扩展。在课堂上，我被要求编写一个谓词path(X, Y, N)，如果且仅当从节点X到节点Y存在长度为N的路径时返回true。给定的是带有相应权重的有向边列表，例如edge(a, b, 3)和edge(c, d, 10)。

给定问题非常直接（只需一些递归和基本情况）。但是，我想或许可以进一步扩展。考虑到简单的有向图输入可能包含循环，并且仅包含非负权重，给定节点A和B，请问唯一最短路径的长度是多少。（通过唯一，我是指如果从A到B存在多个最短路径，则此谓词应返回false）。

下面是一个包含循环的数据库示例（a，b，c，e，a）。

edge(a, b, 1).
edge(b, c, 2).
edge(c, d, 1).
edge(b, d, 4).
edge(c, e, 1).
edge(e, a, 10).
edge(e, d, 6).

我认为为了满足“unique”条件，应该增强原始的path/3谓词，将路径信息作为列表包含在其中（以便稍后比较路径唯一性）。这个新的增强体现在新的path/4谓词中。

path(X, X, 0, []).
path(X, Y, N, [Y]) :- edge(X, Y, N).
path(X, Y, N, [Z|T]) :- edge(X, Z, N1), N2 is N - N1, N2 > 0, path(Z, Y, N2, T).

path(X, Y, N) :- path(X, Y, N, _).

根据此代码，我已经发现了一个问题：如果我尝试将谓词与path(a, b, N, Z)统一，则无法成功，因为N无法与N2 is N - N1 统一。但是，如果我将此部分更改为N is N1 + N2，这仍然不起作用，因为N2仍未被统一。如果我将整个谓词行更改为:

path(X, Y, N, [Z|T]) :- edge(X, Z, N1), path(Z, Y, N2, T), N is N1 + N2.

这将永无止境地运行，因为路径的数量可能是无限的，因为图可能包含循环（我想保持它作为一个挑战）。

至于 shortestpath/3 谓词，我不能找到所有路径并检查所有路径是否更长，因为路径的数量可能由于有一个循环而是无限的。相反，我尝试找到任何长度介于0和给定的 N 之间的路径；如果不存在路径，则这绝对是最短的路径。

countdown(N, N).
countdown(N, X) :- N1 is N - 1, N1 >= 0, countdown(N1, X).

shortestpath(A, B, N) :- path(A, B, N), \+((countdown(N, N1), N > N1, path(A, B, N1))).

然而，这并没有解决作为变量给出的N（因为倒计时函数不起作用），更不用说唯一约束了。

所以我的问题是，有没有办法使这个问题可行，或者说它实际上是不可能做到的？如果有这样的解决方案，请在这里提供（或者如果您认为这是一个“作业”问题，请至少指导我正确的方向）。

限制条件：

- 我不想使用任何内置谓词。只能使用“简单”或“核心”谓词，例如\+、is、+等。var、nonvar、asserta和类似的谓词也可以接受（因为没有实现相同功能的替代方法）。 - 我希望它尽可能通用；也就是说，谓词的任何参数都应该能够给出变量。（或者至少有shortestpath/3的最后一个参数，即最短路径的长度，是一个变量）。

---

我已经查看了以下问题，但它们都没有回答我的情况：

• 在Prolog中找到两个节点之间的最短路径（不涉及加权边，并且使用复杂谓词（例如path/4）。

• 搜索图形的所有路径和最短路径- Prolog（不涉及循环图）。

• 在图形中找到两个节点之间的最短路径（Prolog），并将结果显示为数组（不涉及加权边）。

请随意指向任何其他解答我的问题的问题。

- krismath

---

你能提供一个包含循环的简单数据库示例，用于测试吗？ - coder

它是可以完成的，你的方法并没有错。在一些方面上，你让生活变得比必要的艰难；Prolog的解析算法是深度优先的，而你正在与此作斗争，同时只想返回唯一的解决方案也是一个微小的难点。但这是一个有趣的问题，肯定可以解决；我相信其他聪明的人已经在寻找答案了。 - Daniel Lyons

看一下Dijkstra算法。它是专门为此而设计的。 - Jakob Lovern

Answer 1

很高兴能够回答一道由作业灵感启发的问题，而不仅仅是纯粹的作业！让我们从您的谓词开始，并看看是否可以将其打磨得更加完美，然后我们可以讨论一些替代方法。

首先我从您的简化谓词开始：

path(X, Y, N, [X-Y]) :- edge(X, Y, N).
path(X, Z, N, [X-Y|T]) :-
    edge(X, Y, N0),
    path(Y, Z, N1, T),
    N is N0 + N1.

这里的主要区别在于，我只是生成路径然后计算长度。我没有做任何减法。在Prolog中，通常从最简单的生成和测试方法开始，然后对生成器或测试进行改进，直到满意为止，因此这只是一个非常简单的生成器。目前，我将源节点和目标节点都保留在路径序列中，只是为了帮助我可视化正在发生的事情，但是通过它，您立即可以看到循环的问题：

?- path(a, e, N, T).
N = 4,
T = [a-b, b-c, c-e] ;
N = 18,
T = [a-b, b-c, c-e, e-a, a-b, b-c, c-e] ;
N = 32,
T = [a-b, b-c, c-e, e-a, a-b, b-c, c-e, e-a, ... - ...|...] .

我认为我们与您的示例图不一样，但我们可能会受到Prolog深度优先搜索的影响：只要没有失败，Prolog就没有理由回溯并尝试另一条路径。您可以在那里看到循环。如果使用广度优先搜索，您可以相当确信第一个解决方案是最短的，因为通过将所有内容向前推进一步，您永远不会在生成第一个解决方案之前陷入兔子洞中。Dijkstra算法（感谢@JakobLovern的提醒）通过着色已访问的节点并且不重复统计它们来规避此问题。

通过创建元解释器可以控制搜索行为，这听起来并不太糟糕，但比调整搜索以考虑循环更加困难，我认为大多数人在处理图形时都采用了后者，请先尝试这种方法。

path(X, Y, N, Path) :- path(X, Y, N, [], Path).

path(X, Y, N, Seen, [X]) :-
    \+ memberchk(X, Seen),
    edge(X, Y, N).
path(X, Z, N, Seen, [X|T]) :-
    \+ memberchk(X, Seen),
    edge(X, Y, N0),
    path(Y, Z, N1, [X|Seen], T),
    \+ memberchk(X, T),
    N is N0 + N1.

添加Seen参数，并使用\+ memberchk/2避免将已经存在于路径中的内容再次添加到路径中并不是一件罕见的事情。memberchk/2虽然不是ISO标准，但它是一个非常常用的谓词。您可以像这样自己实现它（请不要这样做！）：

memberchk(X, L) :- once(member(X, L)).
member(X, [X|_]).
member(X, [_|Xs]) :- member(X, Xs).

值得注意的是，memberchk/2与lists结合起来基本上等于Dijkstra算法中使用的sets。这就像Python中的in一样；在Prolog中进行任何实际操作都至少需要member/2。

这些更改使path/4避免了循环，因此您现在可以找到所有解决方案而不会出现虚假的解决方案。注意：我没有使您的图形成无环图。我只是让path/4知道了循环。

请注意，我们会获得多个解：

?- path(a, d, X, Y).
X = 5,
Y = [a, b] ;
X = 4,
Y = [a, b, c] ;
X = 10,
Y = [a, b, c, e] ;
false.

有一个很好的库aggregate，对于这种情况非常有帮助。但是，您要求不使用无用的库。 :)

让我们只获取最短路径：

uniq_shortest_path(X, Y, MinCost, Path) :-
    path(X, Y, MinCost, Path), 
    \+ (path(X, Y, LowerCost, OtherPath), 
        OtherPath \= Path, 
        LowerCost =< MinCost).

这句话的字面意思是，如果没有其他花费小于或等于我们花费的路径，那么Path就是X和Y之间唯一最短的路径（恰好具有MinCost成本）。试一试：

?- uniq_shortest_path(a, d, MinCost, Path).
MinCost = 4,
Path = [a, b, c] ;

这个技巧并不便宜；它可能是通过将所有解决方案相互比较来实现的。但它确实有效，没有任何额外的花招。

一个显著的改进可能是通过获取所有解决方案，按成本排序，然后确保前两个解决方案的成本不相同，然后报告第一个解决方案的成本和路径。

可能可以通过直接实现Dijkstra算法或尝试制作广度优先元解释器来实现更大的改进。进行迭代加深方法可能会起作用，但我怀疑它的性能不会更好，因为它经常必须做并重新执行导致结果被修剪为太昂贵的所有工作。

无论如何，希望这有所帮助！继续对Prolog保持兴奋！

- Daniel Lyons