1

次の簡単なグラフがあります。

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!

上記のクエリを成功させるにはどうすればよいですか?

4

2 に答える 2

1

無向グラフを処理する場合:

path(Start, End, Visited, Path) :-
    ( edge(Start, Next) ; edge(Next, Start) ),
    ...
于 2013-05-20T06:51:25.563 に答える
1

まず、 predicate を定義して既知の事実を書き留めます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.
于 2015-08-20T08:37:33.680 に答える