4

プロローグを独学しようとしています。以下に、無向グラフのノード間のすべてのパスを返す必要があると思われるコードをいくつか書きましたが、そうではありません。この特定のコードが機能しない理由を理解しようとしています (これにより、この質問が同様の Prolog パスファインディングの投稿と区別されると思います)。これを SWI-Prolog で実行しています。手がかりはありますか？

% Define a directed graph (nodes may or may not be "room"s; edges are encoded by "leads_to" predicates).
room(kitchen).
room(living_room).
room(den).
room(stairs).
room(hall).
room(bathroom).
room(bedroom1).
room(bedroom2).
room(bedroom3).
room(studio).
leads_to(kitchen, living_room).
leads_to(living_room, stairs).
leads_to(living_room, den).
leads_to(stairs, hall).
leads_to(hall, bedroom1).
leads_to(hall, bedroom2).
leads_to(hall, bedroom3).
leads_to(hall, studio).
leads_to(living_room, outside).  % Note "outside" is the only node that is not a "room"
leads_to(kitchen, outside).

% Define the indirection of the graph.  This is what we'll work with.
neighbor(A,B) :- leads_to(A, B).
neighbor(A,B) :- leads_to(B, A).

A --> B --> C --> D がループのないパスの場合、

path(A, D, [B, C])

真であるべきです。つまり、3 番目の引数には中間ノードが含まれます。

% Base Rule (R0)
path(X,Y,[]) :- neighbor(X,Y).

% Inductive Rule (R1)
path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), not(member(Z, P)), path(Z,Y,P).

まだ、

?- path(bedroom1, stairs, P).

は偽です。なんで？R1 に一致させるべきではありませんか

X = bedroom1
Y = stairs
Z = hall
P = []

以来、

?- neighbor(bedroom1, hall).
true.

?- not(member(hall, [])).
true.

?- path(hall, stairs, []).
true .

?

実際に評価してみると

?- path(A, B, P).

長さ 1 の解しか得られません。

4

1 に答える 1

5

プロローグへようこそ！not(member(Z, P))問題は、基本的に、R1 に到達したとき、Pまだ純粋な変数であるということです。これは、評価がpath(Z, Y, P)まだそれを定義していないためです。Prolog に関する驚くべき、しかし刺激的なことの 1 つは、member(Ground, Var)を含むリストを生成し、Groundそれらを統合することVarです。

?- member(a, X).
X = [a|_G890] ;
X = [_G889, a|_G893] ;
X = [_G889, _G892, a|_G896] .

これには、インスタンス化されていないリストの値のチェックが常に成功するという紛らわしい副作用があります。そのため、not(member(Z, P))常に失敗し、R1 が常に失敗します。すべての R0 ソリューションが取得され、R1 ソリューションがまったく取得されないという事実は、R1 の何かが常に失敗する原因になっているという手がかりです。結局のところ、R0 が機能することはわかっています。

これら 2 つの目標を交換すると、最初に必要な結果が得られます。

path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), path(Z,Y,P), not(member(Z, P)).

?- path(bedroom1, stairs, P).
P = [hall]

別の解決策を求めると、スタック オーバーフローが発生します。これは、変更後、 で可能な限り迅速にサイクルを使用してソリューションを喜んで生成しpath(Z,Y,P)、 でそれらを事後的に破棄するためnot(member(Z, P))です。(ちなみに、わずかな効率向上のために、 のmemberchk/2代わりに に切り替えることができmember/2ます。もちろん、間違ったことをより速く行うことはあまり役に立ちません。:)

私はこれを幅優先検索に変換する傾向があります.Prologでは、まだ試していないソリューションを含めるために「オープンセット」引数を追加し、各ノードで最初にオープンセットで何かを試し、次にそのノードの可能性をオープン セットの最後に追加します。オープン セットが消えると、到達できるすべてのノードを試したことになります。いくつかのパス検索の問題では、深さ優先検索よりも優れたソリューションです。別の方法として、パスを訪問済みコンポーネントと将来のコンポーネントに分けて、訪問済みコンポーネントのみをチェックすることもできます。現在のステップでサイクルを生成していない限り、サイクルをまったく生成していないことを確認できます。将来のステップについて心配する必要はありません。

あなたの質問の言い方から、あなたは完全な解決策ではなく、ただのヒントを望んでいると思われるので、これで十分だと思います。それが正しくない場合はお知らせください。

于 2013-03-18T03:38:59.200 に答える