15

私はプロローグが初めてです。graph.pl次のグラフで定義しました。

グラフ

そして、ここに私のプロローグコードがあります:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

私はそれを次のように理解しています：頂点と頂点の間にエッジがあり、頂点と頂点の間にパスがある場合にのみ、頂点とX頂点の間にパスがありますYXZZY（ある種の再帰）。

提示されたグラフでよろしいですか？A頂点と頂点の間のパスについて Prolog に尋ねると、Fそれは私に与えられますtrue...これは正しくありません! このコードで何が間違っている可能性がありますか?

4

4 に答える 4

15

グラフのサイクル。アクセスしているノードを追跡して確認する必要があります。ヘルパー述語とアキュムレータを使用して、訪問したノードを追跡して、これを試してください。

path(A,B) :-   % two nodes are connected, if
  walk(A,B,[]) % - if we can walk from one to the other,
  .            % first seeding the visited list with the empty list

walk(A,B,V) :-       % we can walk from A to B...
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - we haven't yet visited X, and
  (                  % - either
    B = X            %   - X is the desired destination
  ;                  %   OR
    walk(X,B,[A|V])  %   - we can get to it from X
  )                  %
  .                  % Easy!

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
于 2014-01-17T22:07:29.500 に答える
7

パスが存在するかどうかを知りたい場合(ただし、実際のパスにあるとは限りません) 、二項関係の推移閉包edge/2を計算します。

幸いなことに、はの一般的なイディオムです。

の非反射推移閉包を表現するには、先の質問「再帰推移閉包の定義」で定義されたedge/2を使用 します。 closure/3

?- クロージャー (エッジ、X、Y)。
   X = a、Y = e
; X = a、Y = d
; X = a、Y = c
; ...

closure/3非常に優れた終端特性を持つことに注意してください。

のすべての節edge/2が根拠のある事実である場合、closure(edge, _, _)普遍的に終了します! 見て：

?- closure(edge, _, _), false.
false.
于 2016-05-13T16:50:38.570 に答える
7

使用する形式 (edge/2) は、Prolog について学習するのに意味があり、チュートリアルに関する mbratch のアドバイスに従う必要があります。

実際には、いくつかのケースでは便利な述語がすぐに使えるようになっています: たとえば、ライブラリ ( ugraph ) には、到達可能な/3 があります。さて、あなたのデータで、このパス/2述語

path(X,Y) :-
    findall(A-B, edge(A,B), Es),
    vertices_edges_to_ugraph([],Es,G),
    reachable(X,G,Path),
    member(Y,Path).

する

?- path(a,X).
X = a ;
X = b ;
X = c ;
X = d ;
X = e.

それが何を意味するか見てみましょう：

findall(A-B, edge(A,B), Es)

ライブラリで必要な表記法を使用して、すべてのエッジを Es に入れます。

vertices_edges_to_ugraph([],Es,G)

G で対応するグラフを作成します

reachable(X,G,Path)

Xから到達可能なすべての頂点のリストパスを作成します（当然）

member(Y,Path)

Y が Path に存在するかどうかを確認します。

Y freeでクエリを実行したので、バインド先の X から到達可能なすべての頂点を取得しaます。

于 2014-01-16T15:38:52.610 に答える
2

サイクルチェック中です！事前にコマンドを使用して例を実行したtrace.ところ、循環後にプログラムが問題に戻り、a から f へのパスを見つけることがわかりました。path(a,f) は path(e,f) が true である必要があり、簡単に言うと、true である必要があります。

(d,f)、(c,f)、(b,f)、そして (a,f) です。

ループを解決するには、ループを防止するメカニズムが必要です。私の最初のアイデアは、ノード名のリストを保持し、パスの確認中にリストに現在の X が含まれていないかどうかも確認することです。

于 2014-01-16T12:44:18.517 に答える