找到两个节点之间的最短路径在序言图(Find the shortest path between t

我想找到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).

谢谢。

Answer 1:

我们使用元谓词 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 。

为了得到这两个，我们必须看所有路径---或者用一个更聪明元谓词（左功课）。