1

SWI-Prolog で簡単なグラフ検索をコーディングしようとしています。私は次のプログラムを思いつきました：

adjacent(1,4). adjacent(4,2). adjacent(3,6).
adjacent(6,4). adjacent(7,10). adjacent(4,9).
adjacent(5,10). adjacent(7,10). adjacent(7,12).
adjacent(6, 11). adjacent(13,11). adjacent(9,14).
adjacent(14,12). adjacent(10,15). adjacent(9,12).

connected(X,Y) :- adjacent(X,Y); adjacent(Y,X).

path(A,B,[A|B]) :-
    connected(A,B).
path(A,B,[A|R]) :-
    \+member(R,A),
    connected(A,C),
    A \== C,
    path(C,B,R).

しかし、このプログラムはスタック オーバーフローを引き起こします。私は何を間違っていますか?どうすれば修正できますか?

4

2 に答える 2

3

ループを回避するためのチェックとしても、返されたパスを使用しようとしています。パスは否定でまだインスタンス化されていないため、パスを検索する場合は機能しません。

最も簡単な解決策は、すでにアクセスしたノードを収集する別の入力引数を追加し、これらをチェックして繰り返しを回避することです。

また、A \==CではなくA\== Bをチェックする必要があると思います。ノードにループがないため、後者は発生しません。ケースA==Bは最初の句で処理されるため、2番目の句で再度処理する必要はありません。

また、メンバーの引数を逆方向に取得し、Martinが書いたように、最初の句のリストを修正する必要があります。

余分な引数なしで無限ループを回避する高度な方法は、否定にfreeze/2を使用することです。

また、Prologでデバッグがどのように機能するかを見てください。これは、物事をよりよく理解するのに役立つ可能性があります。

于 2009-10-22T16:53:03.193 に答える
2

ここでの主な問題はメンバーテストです。署名はmember(Element,List);です。あなたは議論が逆であると仮定しているようです。

さらに、最初のパス述語は2要素のリストをテストすることを目的としていますが、Bは実際には残りのリスト（接続されていない）と統合します。

これらを修正すると、バインドされていない変数では否定がうまく機能しないため、これは完全にインスタンス化された変数に対してのみ機能することがわかります。

于 2009-10-22T14:42:51.607 に答える