如何使用 SWI Prolog 找到加权有向图的唯一最短路径？
How to find the unique shortest path for a weighted directed graph with SWI Prolog?
这是我在 Prolog class 中所做的扩展。在 class 中，我被要求编写一个谓词 path(X, Y, N)，当且仅当存在从节点 X 到节点 Y 的路径且长度为 return 时，该谓词才为真N。给出的是具有相应权重的有向边列表，例如edge(a, b, 3) 和 edge(c, d, 10).
给定的问题非常简单（只有一些递归和基本情况）。但是，我认为也许我可以进一步扩展它。鉴于简单的有向图输入可能包含循环并且仅包含非负权重，那么从给定节点 A 和 [=21= 的 唯一最短路径 的长度是多少？ ]. （通过 unique，我的意思是如果从 A 到 B 存在不止一条最短路径，则此谓词应该 return 为假）。
这是一个包含循环 (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 将无法与 [=28 统一=].但是，如果我把这部分改成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（因为倒计时功能不起作用），更不用说 unique 约束了。
所以我的问题是，有没有办法使这个问题有效，或者实际上不可能这样做？如果有这样的解决方案，请在这里提供（或者如果您认为这是一个 "homework" 问题，请至少指导我正确的方向）。
约束条件：
我不想使用任何内置谓词。仅 'simple' 或 'core' 谓词，例如 \+、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（不解决加权边）。
请随时向我指出解决我的问题的任何其他问题。
很高兴得到一个受作业启发而不仅仅是实际作业的问题！让我们从您的谓词开始，看看我们是否可以将其击败提交，然后我们可以讨论一些替代方法。
首先，我从您的一个简化谓词开始：
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 equals 基本上是 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).
字面上的意思是，当且仅当没有其他路径的成本小于或等于我们的成本。尝试一下：
?- uniq_shortest_path(a, d, MinCost, Path).
MinCost = 4,
Path = [a, b, c] ;
这个技巧并不便宜；它很可能通过将所有解决方案相互比较来起作用。但它确实有效，没有任何额外的恶作剧。
获得所有解决方案，按成本排序，然后在报告第一个解决方案的成本和路径之前确保前两个解决方案的成本不同，可能会带来重大改进。
通过直接实现 Dijkstra 的算法，或者可能通过尝试制作广度优先元解释器，可能会发现更大的改进。进行迭代深化的方法 可能 有效，但我怀疑它会表现得更好，因为它经常需要做并重新做所有导致被修剪的结果的工作因为太贵了。
无论如何，我希望这对您有所帮助！对 Prolog 保持兴奋！
这是我在 Prolog class 中所做的扩展。在 class 中，我被要求编写一个谓词 path(X, Y, N)，当且仅当存在从节点 X 到节点 Y 的路径且长度为 return 时，该谓词才为真N。给出的是具有相应权重的有向边列表，例如edge(a, b, 3) 和 edge(c, d, 10).
给定的问题非常简单（只有一些递归和基本情况）。但是，我认为也许我可以进一步扩展它。鉴于简单的有向图输入可能包含循环并且仅包含非负权重，那么从给定节点 A 和 [=21= 的 唯一最短路径 的长度是多少？ ]. （通过 unique，我的意思是如果从 A 到 B 存在不止一条最短路径，则此谓词应该 return 为假）。
这是一个包含循环 (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 将无法与 [=28 统一=].但是，如果我把这部分改成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（因为倒计时功能不起作用），更不用说 unique 约束了。
所以我的问题是，有没有办法使这个问题有效，或者实际上不可能这样做？如果有这样的解决方案，请在这里提供（或者如果您认为这是一个 "homework" 问题，请至少指导我正确的方向）。
约束条件：
我不想使用任何内置谓词。仅 'simple' 或 'core' 谓词，例如
\+、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（不解决加权边）。
请随时向我指出解决我的问题的任何其他问题。
很高兴得到一个受作业启发而不仅仅是实际作业的问题！让我们从您的谓词开始，看看我们是否可以将其击败提交，然后我们可以讨论一些替代方法。
首先，我从您的一个简化谓词开始：
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 equals 基本上是 Dijkstra 算法中使用的集合。这就像 Python 中的 in；在没有至少 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).
字面上的意思是，当且仅当没有其他路径的成本小于或等于我们的成本。尝试一下：
?- uniq_shortest_path(a, d, MinCost, Path).
MinCost = 4,
Path = [a, b, c] ;
这个技巧并不便宜；它很可能通过将所有解决方案相互比较来起作用。但它确实有效，没有任何额外的恶作剧。
获得所有解决方案，按成本排序，然后在报告第一个解决方案的成本和路径之前确保前两个解决方案的成本不同，可能会带来重大改进。
通过直接实现 Dijkstra 的算法，或者可能通过尝试制作广度优先元解释器，可能会发现更大的改进。进行迭代深化的方法 可能 有效，但我怀疑它会表现得更好，因为它经常需要做并重新做所有导致被修剪的结果的工作因为太贵了。
无论如何，我希望这对您有所帮助！对 Prolog 保持兴奋！