prolog - Prolog 显示路径

Question

我有以下简单的图表：

x <---> y <---> z

edge(x,y).
edge(y,z).

path(Start,End,Path) :-           % path/3: there is a `Path` from `Start` to `End`
    path(Start,End,[Start],Path).

path(End,End,RPath,Path) :-       % internal helper predicate `path/4`
    reverse(RPath,Path).
path(Start,End,Visited,Path) :-
    edge(Start,Next),
    \+ memberchk(Next,Visited),
    path(Next,End,[Next|Visited],Path).

示例查询：

?- path(x,z,P).
P = [x, y, z] ;                   % works as expected
false.

?- path(z,x,P).                        
false.                            % unexpectedly fails!

我该怎么做才能使上述查询成功？

Answer 1

如果要处理无向图：

path(Start, End, Visited, Path) :-
    ( edge(Start, Next) ; edge(Next, Start) ),
    ...

Answer 2

首先，我们通过定义谓词写下已知事实edge/2：

edge(x,y).
edge(y,x).
edge(y,z).
edge(z,y).

然后我们像这样与元谓词edge/2一起使用： path/4

?- path(edge,Path,x,z).              % one direction
  Path = [x,y,z]
; false.

?- path(edge,Path,z,x).              % other direction
  Path = [z,y,x]
; false.

下面这个非常一般的查询怎么样？所有可能的路径都基于什么edge/2？

?- path(edge,Path,From,To).
  From = To,         Path = [To]
; From = x , To = y, Path = [x,y]
; From = x , To = z, Path = [x,y,z]
; From = y , To = x, Path = [y,x]
; From = y , To = z, Path = [y,z]
; From = z , To = y, Path = [z,y]
; From = z , To = x, Path = [z,y,x]
; false.