アトム/ 1述語がプロローグでどのように機能しますか？

Question

私は述語がルール

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

あるProlog.whereで経路探索の問題を解決しようとしているがであります edge(X,Y) :- edge(X,Z), edge(Z,Y).
次に、私がコンパイルしてクエリを実行したとき | ?- edge(a,X)。 Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ) 私は解決策を探して、我々のルールでatom(x).,atom(y).を含むことがスタックオーバーフローの問題を解決できることを発見しました。つまり、新しいルールが

edge(X,Y) :- atom(X), atom(Y), edge(X,,Z), edge(Z,Y).で、はい、それは、スタックオーバーフローの問題を解決しなかった.but、私は（原子/ 1） 述語がここに私の問題を解決する方法を、まさにこのお知りになりたい？それは私たちに何をしますか変数X,Yは、StackOverflowの問題を解決するには？ 私はPrologの初心者であり、何か助けていただければ幸いです ありがとうございます。 :)

Answer 1

最初の命名では、edge/2という名前はあなたの述語をうまく説明していません。おそらく、実際には、1つまたは複数のエッジで構成されるpath/2が必要です。

atom/1は本当にあなたの問題を解決しますか？言い換えれば、edge(X, Y)は本当にすべての正しいソリューションをクエリに提供していますか？すべてatom/1は、その引数がアトムであることを保証しているため、バインドされていない変数にすることはできません。だからedge(X, Y)は、すべての正しい解決策を提供していません。現在定義されている述語edge(X, Y)は、常にXまたはYのいずれかでアンバインドされているため、直接的な事実を持つソリューションのみが得られます。

| ?- edge(a, Y). 

Y = b ? ; 

Y = c ? ; 

no 

たとえば、Y = dの解決策はありますか？ edge(X, Y)は、edge/2のファクトに記載されているソリューションをピックアップしていますが、複数の接続エッジを含むソリューションはありません。

元の問題は無限再帰によるものです。これは、edge/2が不必要に呼び出されたためです。ロジックをより正確かつ正確にするため、実際にはネーミングが重要になります。 edge(X, Y)は、XとYがエッジ（XとYが直接接続されている）を形成していることを意味します。 path(X, Y)は、のパスからXからYまでの1つ以上ののエッジを経由することを意味します。換言すれば、XからYへパスは、XからYへエッジのいずれかであり得る、またはそれは、ZおよびZからYへパスにXからエッジすることができます。

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

今我々が得る：例えばaからeに得るための複数の方法があるかもしれないので、

| ?- path(a, X). 

X = b ? a 

X = c 

X = d 

X = e 

X = f 

X = g 

X = d 

X = e 

X = f 

X = g 

(1 ms) no 
| ?- 

は重複があります。横断したパスを示す引数を含めると、これは明らかになります。

しかし、この解決策はストーリーの終わりではありません。あなたの現在の事実は、「迂回路」のパスがないようなものです（それに続くと同じノードに最終的に戻ってくるパス）。これを処理するには、すでに通過したノード/エッジを追跡し、それらを再び通過するのを避けるために、述語引数が必要です。