在 Prolog 中查找图中两个节点之间的最短路径

Question

我想在 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

当您只需要一种解决方案时，您可以查看剪切运算符“！”。

为了避免陷入无限循环，您应该使用累加器列表来存储已访问过的节点。