0

JIPrologでグラフ検索をしたいです。以下の例はmemberchk、がなくても正常に機能しますが、サイクルのあるパスが返されます。これは望ましくありません。しかし、私がそれを含めると、おそらく無限の検索のために、Prologがフリーズします。

connected(ac,a,b). connected(ac,a,c). connected(ac,b,c). 
connected(ac,b,a). connected(ac,c,a). connected(ac,c,b).

path(A,B,[AB]) :- connected(AB,A,B).
path(A,C,[H|T]) :- connected(H,A,B), path(B,C,T), \+ memberchk(H,T).

この回答で、理由（エッジのリストはまだインスタンス化されていません）と解決策のヒント（を使用freeze/2）を見つけました。ただし、freeze/2私が使用しているJIPrologでは機能しません。誰かが私を別の解決策に助けることができますか？

編集：一般的なグラフの場合、この例のように、代わりにノードを追跡することが解決策になることはわかっていますが、私の特定のアプリケーションでは、「ノード」もエッジにある可能性があるため、チェックしたいのは訪問されたノードではなく、訪問されたエッジ。

4

1 に答える 1

0

あなたの要件を理解するのはよくわかりません。私は提案された答えを適応させようとします。

% get a path from start to end
path(Start, End, Path) :-
    path(Start, End, [], Path).

path(A, B, Visited, [AB|Visited]) :- connected(AB, A, B).

path(A, C, Visited, Path) :-
    connected(AB, A, B),
    \+ memberchk(AB, Visited),
    path(B, C, [AB|Visited], Path).

注意：テストされていないコード...

于 2012-10-05T23:08:58.127 に答える