在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). 

感谢您。

- Aaron Azhari

Answer 1

我们与您提供的arc/2定义相结合，使用meta-predicate path/4：

?- 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 有 两条不同的最短路径。

要获取这两个路径，我们必须查看所有路径---或者使用更聪明的元谓词（留作家庭作业）。

- repeat

---

难道没有比枚举所有路径更好的算法吗？ - user502187

Answer 2

如果你只想要一个解决方案，可以尝试使用 cut 操作符 "!"。

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

- tokage

---

我更新了我的代码，请看一下。似乎我的成员谓词出了问题。 - Aaron Azhari

任何实际的编码都比建议更受欢迎。 - Aaron Azhari