3

ここで私の問題は、2 つのノードが接続されているかどうかを確認することです。

私の知識ベースは、

edge(a,b):-!.
edge(b,a):-!.
edge(a,e):-!.
edge(e,a):-!.
edge(b,c):-!.
edge(c,b):-!.
edge(b,d):-!.
edge(d,b):-!.
edge(c,e):-!.
edge(e,c):-!.
edge(d,e):-!.
edge(e,d):-!.
edge(a,f):-!.
edge(f,a):-!.

isConnected(X,X):-!.
isConnected(X,Y):-edge(X,Y),!.
isConnected(X,Z):-not(edge(X,Y)),edge(X,Y),isConnected(Y,Z),!.
isConnected(X,Z):not(edge(X,Y)),edge(X,Z),not(isConnected(Y,Z)),isConnected(Z,Y),!.
4

1 に答える 1

2

おっと。それはたくさんのカットです。Prolog では、不必要な回答を削除するためにカットが役立つ場合がありますが、次のような事実がある場合:

edge(a, b).

次のように書いても何も得られません。

edge(a, b) :- !.

結局のところ、そこには変数がなく、代替ソリューションがないため、選択ポイントはありません。まず、これらのカットをすべて削除して、事実を修正しましょう。

次に isConnected が何を言っているのか見てみましょう。英語で声に出して読んで、意味があるかどうか見てみましょう。

  1. X は X に接続されています。
  2. X から Y へのエッジがある場合、X は Y に接続されます。
  3. X から Y へのエッジがない場合、X は Z に接続されますが、X から Y へのエッジがあり、Y は Z に接続されます。 (???)
  4. X から Y へのエッジがなく、X から Z へのエッジがあり、Y が Z に接続されていないが Z が Y に接続されている場合、X は Z に接続されます。 (???)

最初の 2 つはかなり合理的に思えます。3番目のものは、すぐに矛盾しているようです。not(edge(X, Y))と同時にどのように真になることができますedge(X, Y)か? Prolog のコンマはthenだけでなくandを意味することに注意してください。これら 2 つの条件が両方とも true になることはあり得ないため、句の残りの部分は無意味です。おそらくあなたが言いたかったのは、次のようなものでした: X から Y へのエッジがあり、Y が Z に接続されている場合、X は Z に接続されています。Prolog では次のようになります。

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

論理的には、これは確かに真実ですが、X が Z に接続されているかどうかを確認することは、すべての同じノードについて Y が Z に接続されているかどうかを確認することを意味する可能性があるため、あらゆる種類の複雑なグラフの計算には非常にコストがかかります。

4 番目の句には、 が である:必要があるというタイプミスがあり:-ます。さらに重要なことに、ここでエッジの方向性を補正しようとしているようです。これを行うのに適した場所は、ステップ 2 あたりで、両方のケースを提供します。

isConnected(X, Y) :- edge(X, Y) ; edge(Y, X).

あなたの事実データベースに基づいて、あなたが実際にこれを意味するかどうかはわかりません。両方の方向を説明するためにすべての事実を複製しました。ファクト データベースが有向グラフを表す場合、これはおそらく必要であり、ルールはノードの反転を試みるべきではありません。代わりに無向グラフを表す場合、述語は、両側をチェックするこのようなルールでそれを説明する必要があり、各エッジを 1 回だけリストする必要があります。両方の方法で行うと、Prolog に一連の不必要な作業を行うように指示していることになります。最初に をチェックedge(a, b)し、次にルールがそれを に反転しedge(b, a)、次に次のファクトに移動してから、edge(b, a)ルールがそれを に反転し、事実上edge(a, b)すべてを 2 回チェックするからです。 .

ここで問題なのは、これを問題の論理的な解決策にうまく変換できたとしても、非常に非効率的であるということです。見られたものと見られなかったものを追跡する 2 つのものが関連しているかどうかを判断するためのアルゴリズムがあり、そのうちの 1 つを実装する方がはるかに良いと思います。

于 2013-01-22T16:36:28.600 に答える