prolog - 如何使用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).

我以为满足唯一条件，所以我认为应该增加原始的 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的最后一个参数，它是最短路径的长度，是一个变量)。

我已经看过以下问题，但不能解决我的情况:

Find the shortest path between two nodes in a graph in Prolog(不处理加权边，也使用复杂的谓词(例如path/4)。

search all paths and the shortest path for a graph - Prolog(不包含带循环的地址图)。

Find the shortest path between two nodes in a graph in (Prolog) and display the result as array(不处理加权边)。

请随时将我引向其他任何可以解决我的问题的问题。

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 +列表基本上等于Dijkstra算法中使用的集合。就像Python中的 in一样；尝试至少在没有 member/2的情况下尝试在Prolog中做任何真正的事情都是疯狂的。

这些更改使 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保持兴奋!