Prologで指示されたグラフ

Question

旅行（A、B、訪問済み、経路）と旅行（A、B、P、[B | P]）の機能/条件を詳しく説明してください。点AとBが互いに直接接続されている場合」は、我々が直接サブを発見した

travel(A,B,P,[B|P]) :- 
    connectedEdges(A,B). 

：グラフ

edge(a,b). 
edge(b,c). 
edge(b,d). 
edge(c,d). 
edge(d,b). 
edge(e,f). 
edge(e,g). 
edge(e,h). 
edge(h,i). 
edge(i,g). 
edge(b,e). 

connectedEdges(X,Y) :- edge(X,Y). 
connectedEdges(X,Y) :- edge(Y,X). 

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

travel(A,B,P,[B|P]) :- 
     connectedEdges(A,B). 

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

Answer 1

におけるパスA及びBは、第travel/4ルールで開始しますこれまで訪問したすべてのポイントで統一されたパスにポイントBを追加することで成功する可能性があります。

つまり、（2つのノードへの直接接続を見つけることによって）サブ問題を解決したので、これは本質的にはP（これまで訪問したものすべて）、パスリストの末尾[B|P]（総パスは私たちが訪問した最後のノードです....現在の宛先ノードは、先に訪れたすべてのノードに先行してです）。次travel/4ルールの今

---

：

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

それは、最初のルールが成功したかどうか、この第二のルールは常に代替として試されることに注意することが重要です。この実装のこの事実のために、このコードは複数のパス（複数存在する場合）を見つける可能性があります。

とにかく、この第2のルールでは、A、に接続されているノードがすべてB以外であることがわかります。なぜですか？これは、上記の最初のルールが既にそれを試みたためです。このルールでは、代替案を探しています。そのノードCがまだ訪問されていない場合、その点（C）から目的地まで簡単に移動しようとします。次に、完全なパスが見つかるまで、travel/4を再帰的にクエリ/コールします。

この実装では、特定のクエリに対して0,1、または1より多くの解が見つかる場合があります。

---

要約すると、最初のルールは、 のポイント間の接続を見つけるために呼び出されます。第2の規則は、 間接的にの接続を見つけるために呼び出されます。