7

次の事実を含むグラフが与えられます。

edge(a,b)
edge(a,c)
edge(b,a)
edge(c,d)
edge(d,d)
edge(d,e)
edge(e,f)
edge(f,g)
edge(g,e)

cycle(X)そして、ノード から始まるサイクルがあるかどうかを決定するルール を定義するよう求められますX。

これを行う方法が本当にわかりません。ノードをトラバースして、次のノードが最初のノードになるかどうかを確認しようとしましたが、機能しないようです

4

6 に答える 6

5

Archieのアイデアは良い出発点ですが、パスの検索中に別のサイクルが見つかると、無限ループが作成されます。

path(X,Y,Visited)私も何年もプロローグを使用していませんが、訪問したノードを追跡し、無限ループを防ぐようなものが必要になります。

于 2011-07-17T01:47:17.827 に答える
2

トラバーサル中に訪問したノードに遭遇した場合、訪問したノードリストで深さ優先検索を使用しました。これは true を返します。小さな入力でテストしたところ、正しく動作しているように見えました。

cycle(X):- cycleh(X,[X]).
cycleh(X,Visited) :- edge(X,Y), (member(Y,Visited) -> !,true; cycleh(Y,[Y|Visited])).
于 2011-07-17T09:50:15.483 に答える
2

これでうまくいくはずです：

cycle( X ) :-
  cycle( X , [] ).

cycle( Curr , Visited ) :-
  member( Curr, Visited ) ,
  !. 
cycle( Curr , Visited ) :-
  edge( Curr , Next ) ,
  cycle( Next , [Curr|Visited] ) .

@Gökhan Uras と同様の解決策のように見えますが、偉大な心は同じように考えます! または何か B ^)

基本的なロジックは、現在のノードが既に訪問されている場合 (cycle/2ヘルパー述語の最初の節) にサイクルがあるということです。その時点で、カット (!) して成功を宣言します。カット (!) の理由は、それがないためです、バックトラックは、すでに訪れたノードを再訪することになり、無限のサイクルセットになります。

現在のノードにアクセスしていない場合は、現在のノードに固定されているエッジを取得してアクセスします。訪問の 2 番目の句にバックトラックするとcycle/2、次のエッジを訪問するため、特定のパスが使い果たされると、cycle/2バックトラックして別のパスを試行します。

于 2011-07-21T18:39:54.660 に答える
1

Prologシステムにフォワードチェイナーがある場合は、それを使用してサイクルを決定できます。path/2ただし、事実を生成して保持するため、かなりのメモリを消費する可能性があることに注意してください。

自動的に重複を排除しないフォワードチェインでルールを作成する方法は次のとおりです。\+重複を明示的に排除するためにあります：

:- forward edge/2.
:- forward path/2.

path(X,Y) :- edge(X,Y), \+ path(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y), \+ path(X,Y).
cycle(X) :- path(X,X).

結果に関係する例をもう少し面白くするために、を削除しましたedge(d,d)。実行例は次のとおりです。

?- postulate(edge(a,b)), postulate(edge(a,c)), postulate(edge(b,a)),    
postulate(edge(c,d)), postulate(edge(d,e)), postulate(edge(e,f)), 
postulate(edge(f,g)), postulate(edge(g,e)), cycle(X).
X = a ;
X = b ;
X = e ;
X = f ;
X = g

ここでのpostulate/1述語はイベントを投稿し、フォワードチェイナーのプロパゲーターを実行し続けます。転送ルールの書き方は、使用しているPrologシステムのそれぞれのライブラリによって異なります。

PS：まだいくつかの調査が進行中です：http：
//x10.sourceforge.net/documentation/papers/X10Workshop2011/elton_slides.pdf

于 2012-05-17T23:24:35.697 に答える
1

私はしばらく Prolog を使用していませんが、この問題に対する私のアプローチは次のとおりです。

ノードから へpath(X,Y)のパスが存在するかどうかをチェックするルールを作成できます。パスは、単一のエッジまたはパスにつながるエッジです。これがあれば、ノードから始まるサイクルを見つけるのは簡単です- それは単純になります. これが私の実装です（頭のてっぺんから取られたもので、必ずしも正しいとは限りませんが、アイデアは得られます）：XYXpath(X,X)

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

cycle(X) :- path(X,X).
于 2011-07-17T00:35:37.337 に答える
0

Prolog を使用してからしばらく経ちましたが、おそらくこのアプローチはうまくいくでしょう:パスは、各エッジが前のエッジが終了したノードで始まるエッジのシーケンスです (たとえば、a -> b、b -> c、c -> d)。自明なパスは 1 つのエッジであり、既存のパスにエッジを追加することで、より複雑なパスを形成できます。サイクルは、同じノードで開始および終了するパスです。これらの定義を使用して Prolog ルールを作成できますか?

于 2011-07-17T00:33:57.100 に答える