这是我在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的最后一个参数，它是最短路径的长度，是一个变量)。 我已经看过以下问题，但不能解决我的情况:
path/4)。请随时将我引向其他任何可以解决我的问题的问题。
最佳答案
很高兴收到一个受家庭作业启发的问题，而不仅仅是实际的家庭作业!让我们从您的谓词开始，看看是否可以击败它来提交，然后再讨论一些替代方法。
首先，我从您的简化谓词开始:
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保持兴奋!
关于prolog - 如何使用SWI Prolog为加权有向图找到唯一的最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47778959/