3

実装しようとすると問題が発生します

friends(mia, ellen).
friends(mia, lucy).
friends(X,Y) :-
  friends(X,Z),
  friends(Y,Z).

私が尋ねる?- friends(mia, X).と、ローカルスタックが不足します。

それから私は追加します

friends(ellen, mia) friends(lucy, mia)

私は尋ねます ?- friends(mia, X).、それは答え続けX = miaます。

理解できません、なぜ再帰的なのですか？

4

2 に答える 2

2

まず、次の 2 つの仮定があります。

  • 書きたかった実際のコードは、適切なドットを付けた次のコードです。

    friends(mia,ellen).
friends(mia,lucy).
friends(X,Y) :- 
   friends(X,Z),
   friends(Z,Y).

  • 推移性が成立します: 友達の友達は私の友達でもあります (私はむしろ友情を距離としてモデル化します: 「A は B の近くにあり、B は C の近くにある」は必ずしも「A は C の近くにある」ことを意味しません)。繰り返しの答えは、モデル化したいものを最初に把握することについて正しいです。

では、なぜ無限再帰に入るのか見てみましょう。

ステップバイステップ

では、次のように尋ねるとどうなりfriends(mia,X)ますか。

  1. 最初の句が与えますY=ellen（より多くの解決策を求めます）
  2. 2番目の句は次のとおりY=lucyです（さらに解決策をもう一度尋ねます）
  3. スタックオーバーフロー ！

3 番目の節を詳しく説明しましょう。

  1. friends(mia,Y)いくつかの変数が保持されているかどうかを知りたいですY。

  2. を保持するZような変数はありますか？friends(mia,Z)

    Yからへの名前変更とは別に、Z上記のステップ 1 と同じ質問をしていることに注意してください。 これは無限再帰の匂いがしますが、見てみましょう...

  3. の最初の 2 つの句を試しますが、 norfriendsがないために失敗します。friends(ellen,Y)friends(lucy,Y)
  4. 推移的な友情があるかどうかを調べるために 3 番目の節を呼び出し、それ以上進めずにステップ 1 に戻ります => 無限再帰。

この問題は、文脈自由文法における無限左再帰に似ています。

修正

次の 2 つの述語があります。

  1. known_friends/2、直接的な関係を提供します。

  2. friends/2、これも推移性をエンコードします

    known_friends(mia,ellen).
known_friends(mia,lucy).

friends(X,Y) :- known_friends(X,Y).
friends(X,Y) :- known_friends(X,Z), friends(Z,Y).

ここで、 を尋ねるfriends(mia,X)と、friends/2は の 2 つの節と同じ答えを返しknown_friends/2ますが、他動詞節に対する答えは見つかりません。ここでの違いはknown_friends、少し進歩することです。つまり、mia(再帰なしで)の既知の友人を見つけます。その友人が他の人の友人であるかどうかを（再帰的に）見つけようとします。

友達の友達

known_friends(ellen, bishop) :-)を追加すると、friendsも検出さY=bishopれます。

  • known_friends(mia,ellen)保持し、
  • friends(ellen,bishop)再帰的に見つけられます。

真円度

フレンドシップ グラフ ( known_friends) に循環依存関係を追加すると、 でこのグラフを無限にトラバーサルできますfriends。これを修正する前に、次の質問を検討する必要があります。

  • friends(X,Y) <=> friends(Y,X)すべてに当てはまります(X,Y)か？
  • friends(X,X)はどうXですか？

次に、上記のプロパティを考慮しながら、 をfriendsループしているときを検出するために、評価するときにすべての見た人のセットを保持する必要があります。known_friends試してみたい場合は、これを実装するのはそれほど難しくありません。

于 2015-04-28T21:28:50.990 に答える