我想在Prolog中找到两个节点之间的最短路径。我知道如何找到两个节点之间的所有路径,但是不幸的是,以下代码陷入了循环:
arc(a,b).
arc(b,a).
arc(b,c).
arc(c,b).
arc(c,d).
arc(d,c).
path(X,Y,[arc(X,Y)]) :-
arc(X,Y).
path(X,Y,[arc(X,Z)|P]) :-
arc(X,Z),
path(Z,Y,P).
代码运行为:
?- path(a,c,R).
R = [arc(a, b), arc(b, c)] ;
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, c)] ;
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, a), arc(a, b), arc(b, c)]
....
所以,我的问题是:如何获取所有路径而不会无限循环?
最终,我将获得列表的长度并找到最小值。
[请尽可能提供ISO Prolog解决方案。
注意:这是更新的代码,依我所知。显然,成员谓词在检查事实而不是原子时不起作用。
xxx([]).
path(X,Y,[arc(X,Y)]) :-
arc(X,Y).
path(X,Y,[arc(X,Z)|P]) :-
arc(X,Z)
,xxx(L)
,member(arc(X,Z),L)->
!;
(member(arc(Z,X),L)->
!;
(append(L,[arc(X,Z)],R),retract(xxx(_)),assert(xxx(R)),path(Z,Y,P))).
我的成员谓词是:
member(X,[X|T]).
member(X,[H|T]) :- member(X,T).
谢谢。
我们将meta-predicate path/4
与您提供的path/4
的定义结合使用:
arc/2
?- path(arc,Path,From,To).
From = To , Path = [To]
; From = a, To = b, Path = [a,b]
; From = a, To = c, Path = [a,b,c]
; From = a, To = d, Path = [a,b,c,d]
; From = b, To = a, Path = [b,a]
; From = b, To = c, Path = [b,c]
; From = b, To = d, Path = [b,c,d]
; From = c, To = b, Path = [c,b]
; From = c, To = a, Path = [c,b,a]
; From = c, To = d, Path = [c,d]
; From = d, To = c, Path = [d,c]
; From = d, To = b, Path = [d,c,b]
; From = d, To = a, Path = [d,c,b,a]
; false.
的定义不包括所有循环。
要获得最短路径,我们需要查看所有解决方案!
为了显示实际上是这样,让我们像这样扩展path/4
的定义:
arc/2
假设我们要“获取从arc(a,b).
arc(b,a).
arc(b,c).
arc(a,c). % (new)
arc(b,d). % (new)
arc(c,b).
arc(c,d).
arc(d,c).
到a
的所有最短路径,因此我们查询:
d
在上面的查询中,有从?- path(arc,Path,a,d).
Path = [a,b,c,d]
; Path = [a,b,d] % shortest path #1
; Path = [a,c,b,d]
; Path = [a,c,d] % shortest path #2
; false.
到a
的两个不同的最短路径。
要获得两者,我们必须查看所有路径-或使用更智能的d
(留作作业)。>>
当您只需要一种解决方案时,您可以研究剪切运算符“!”。