kri*_*ath 7 graph unique prolog shortest-path
这是我在Prolog课程中所做的扩展.在课堂上,我被要求编写一个谓词path(X, Y, N),当且只有从节点X到节点的路径Y有长度时才返回true N.给出的是具有相应权重的有向边的列表,例如edge(a, b, 3)和edge(c, d, 10).
给定的问题非常简单(只有一些递归和基本情况).但是,我想也许我可以进一步扩展它.鉴于简单向图输入可以含有周期和仅包含非负权重,什么是长度独特最短路径从给定节点A和B.(通过独特的,我的意思是,如果一个以上的最短路径从存在这个谓词应该返回false A到B).
以下是包含循环(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,即最短路径的长度,一个变量).
我已经查看了以下问题,并没有回答我的情况:
在Prolog中找到图形中两个节点之间的最短路径(不解决加权边缘并且还使用复杂谓词(例如path/4)).
搜索图形的所有路径和最短路径 - Prolog(不解决带循环的图形).
在(Prolog)中找到图形中两个节点之间的最短路径,并将结果显示为数组(不解决加权边缘).
请随时指出解决我问题的任何其他问题.
很高兴得到一个受家庭作业启发而不仅仅是实际作业的问题！让我们从你的谓词开始，看看我们是否可以击败它提交，然后我们可以讨论一些替代方法。
首先，我从你的简化谓词开始：
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 算法中使用的基本集合。这就像in在 Python 中一样；在 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.
有一个不错的库，聚合对于这种情况很有帮助。但是，您要求没有虚假的库。:)
让我们得到最短的路径：
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 的兴奋！