2

まず文脈。次の双方向グラフがあります。

グラフ

Prolog では次のように表されます。

relation(a,c).
relation(b,d).
relation(c,d).
relation(d,e).
relation(e,f).

connection(X,Y) :- relation(X,Y).
connection(X,Y) :- relation(Y,X).

したがって、ノード間の関係と、ノード間の接続が、前に述べたように、両方向に関係しています。

私が探しているのは、2 つのノード間のグラフにパスがあるかどうかを判断path(X,Y)できるプロローグ定義です(両方のノード間に少なくとも 1 つのパスが存在する場合は true、両方のノード間に既存のパスがない場合は false を返します)。

したがって、このモデルの目標出力は次のようになります。

?- path(a,d).
true.

?- path(b,a).
true. 

?- path(f,b).
true

?  path(a,g).  % The node g doesn't exist
false.

これには訪問済みリストの使用が含まれることを知っています。これの例を見たことがありますが、2つのノード間のすべての可能なパスを示しています。しかし、これは私が探しているものではありません。私が探しているのは、2 つのノード間にパスがあるかどうかを検出する定義であり、2 つのノード間に可能なすべてのパスを提供するわけではありません。

編集: @mbratch のおかげで、提案された問題を解決策に適応させることができるようになりました。

relation(a,c).
relation(b,d).
relation(c,d).
relation(d,e).
relation(e,f).

connection(X,Y) :- relation(X,Y).
connection(X,Y) :- relation(Y,X).

path_exists(X,Y) :- path(X,Y,_), !.

path(A,B,Path) :-
       travel(A,B,[A],Q), 
       reverse(Q,Path).

travel(A,B,P,[B|P]) :- 
       connection(A,B).
travel(A,B,Visited,Path) :-
       connection(A,C),           
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path).
4

1 に答える 1

2

取得したいものは、一般に「二項関係の推移閉包」と呼ばれます。

次のようなを使用して、のを取得できます。connection/2 closure/3

% Q: ` From`から始まる `connection` 経由で到達できる `To` はどれですか?
?- クロージャ(接続、From、To )。

まず、OPが提供したクエリを実行しましょう：

?- closure(connection,a,d).
  true                                % OK: succeeds non-deterministically
; false.                      

?- closure(connection,b,a).
  true                                % OK: succeeds non-deterministically
; false.

?- closure(connection,f,b).
  true                                % OK: succeeds non-deterministically
; false.

?- closure(connection,a,g).
false.                                % OK: finitely fails

最も一般的な質問をしましょう。

?- closure(connection,X,Y).
  X = a, Y = c
; X = a, Y = d
; X = a, Y = e
; X = a, Y = f
; X = a, Y = b
; X = b, Y = d
; X = b, Y = e
; X = b, Y = f
; X = b, Y = c
; X = b, Y = a
; X = c, Y = d
; X = c, Y = e
; X = c, Y = f
; X = c, Y = b
; X = d, Y = e
; X = d, Y = f
; X = e, Y = f
; X = c, Y = a
; X = d, Y = b
; X = d, Y = c
; X = d, Y = a
; X = e, Y = d
; X = e, Y = b
; X = e, Y = c
; X = e, Y = a
; X = f, Y = e
; X = f, Y = d
; X = f, Y = b
; X = f, Y = c
; X = f, Y = a
false.
于 2015-09-03T11:46:14.810 に答える