9

次の内容のデータベースがあるとします。

son(a, d).
son(b, d).
son(a, c).
son(b, c).

したがって、aとbはdとcの息子です。今、あなたは、誰が誰の兄弟であるかを、より大きなデータベースを考えて知りたいと思います。解決策は次のとおりです。

brother(X, Y) :-
    son(X, P),
    son(Y, P),
    X \= Y.

これに伴う問題は、「brother（X、Y）」と尋ねると、「;」を押し始めます 次のような冗長な結果が得られます。

  • X = a、Y = b;
  • X = b、Y = a;
  • X = a、Y = b;
  • X = b、Y = a;

これらの結果が得られる理由は理解できますが、これを修正する方法を探しています。私に何ができる？

4

6 に答える 6

6

Prolog は常に、一連の真実を考慮して、ステートメントに対して利用可能なすべての解決策を見つけようとします。展開は深さ優先検索として機能します。

son(a, d).
son(b, d).
son(a, c).
son(b, c).

brother(X, Y) :-
    son(X, P),
    son(Y, P),
    X \= Y.

                         brother(X, Y)
       _______________________|____________________________        [son(X, P)]
      |               |                  |                 |
X = a, P = d     X = b, P = d       X = a, P = c      X = a, P = b
      |               |                  |                 |  
      |              ...                ...               ...
      |
      | (X and P are already defined for this branch;
      |  the algorithm now looks for Y's)
      |__________________________________________                  [son(Y, d)]
                |                                |
      son(a, d) -> Y = a               son(b, d) -> Y = b
                |                                |
                |                                |                 [X \= Y]
      X = a, Y = a -> false            X = a, Y = b -> true
                                                 |
                                                 |
                                  solution(X = a, Y = b, P = d)

しかし、ご覧のとおり、展開はすべてのブランチで実行されるため、最終的な回答と同じソリューションが得られます。@Daniel Lyons が指摘したように、setofビルトインを使用できます。

!分岐が有効であることが判明したら、「水平」展開を停止する --cut 演算子 -- を使用するか、複数のソリューションを回避するステートメントを追加することもできます。

詳細については、統一アルゴリズムをご覧ください。

于 2013-02-23T15:59:58.003 に答える
5

まず、Prolog データベースを動的に更新しないことをお勧めします。いくつかの理由から、記事 「Prolog 動的データベースの扱い方」を検討してください。.

@DanielLyons が回答で示唆しているように、ビルトインとの組み合わせを使用できます。setof/3member/2

さらに別の方法として、次のsetof/3ようなかなり変わった方法で使用する次のクエリを検討してください。

?- setof(t,brother(X,Y),_).
X = a, Y = b ;
X = b, Y = a.
于 2015-04-29T14:39:40.897 に答える
4

比較で 1 つのセットを削除できます。

brother(X, Y) :-
   son(X, P),
   son(Y, P),
   X \= Y, X @< Y.

?- brother(X, Y).
X = a,
Y = b ;
X = a,
Y = b ;
false.

X と Y は両方の方法でインスタンス化されるため、X が Y よりも小さいことを要求することは、ソリューションを半分に削減する良い方法です。

2 番目の問題は、X と Y が複数の親を持つ兄弟であることです。ここでの最も簡単な解決策は、ルールをより明確にすることです。

mother(a, d).
mother(b, d).
father(a, c).
father(b, c).

brother(X, Y) :-
  mother(X, M), mother(Y, M),
  father(X, F), father(Y, F),
  X \= Y, X @< Y.

?- brother(X, Y).
X = a,
Y = b ;
false.

このメソッドはこの特定の問題に非常に固有のものですが、根本的な理由はそうではありません:aとbが「兄弟」であるため、2 つのコピーがあっcた — dProlog がそのソリューションを 2 回作成したのは正しかったのです。異なる値。

より洗練された解決策は、おそらく を使用setof/3して解決策を取得することです。これは、元のコードでも機能します。

?- setof(X-Y, (brother(X, Y), X @< Y), Brothers).
Brothers = [a-b].

このアプローチの欠点は、Prolog がさまざまなソリューションを生成するのではなく、リストになってしまうことですが、member/2.

于 2013-02-23T15:55:19.847 に答える
0

これはうまくいくはずです。しかし、改善できると思います (私は Prolog の専門家ではありません)。

brother(X, Y) :-
    son(X, P1),
    son(Y, P1),
    X @< Y,
    (son(X, P2), son(Y, P2), P1 @< P2 -> false; true).
于 2013-02-23T17:50:20.270 に答える
0

Strawberry Prolog コンパイラを使用している場合、次のように入力してもすべての回答が得られるわけではありません。

?- brother(X, Y),
   write(X), nl,
   write(Y), nl.

すべての答えを得るには、次のように書きます。

?- brother(X, Y),
   write(X), nl,
   write(Y), nl,
   fail.

お役に立てば幸いです。:)

于 2013-02-23T20:18:41.757 に答える
-2

答えが出ました。

% Include the dictionary
:- [p1]. % The dictionary with sons

:- dynamic(found/2).

brother(X, Y) :-
    % Get two persons from the database to test
    son(X, P),
    son(Y, P),

    % Test if the two persons are different and were not already used
    testBrother(X, Y).

% If it got here it's because there is no one else to test above, so just fail and retract all
brother(_, _) :-
    retract(found(_, _)),
    fail.

testBrother(X, Y) :-
    X \= Y,
    \+found(X, Y),
    \+found(Y, X),

    % If they were not used succed and assert what was found
    assert(found(X, Y)).

最終的には常に失敗を返しますが、次の場合は成功します。

  • 兄弟（X、Y）。% 繰り返しのないすべての兄弟
  • 兄弟（「ウラカ」、X）。% 繰り返しのないウラカのすべての兄弟
  • 兄弟（「ウラカ」、「サンチョI」）。% 確かに、ウラカとサンチョは父と母が同じだから。実際、同じ母親または同じ父親しかいない場合でも、true が返されます。少し文脈から外れていますが、それでも有効です。3 つ以上の共通の親がいる場合でも機能します

次のように失敗します。

  • 兄弟（X、X）。% 同一人物だから嘘
  • 兄弟（「いや」、X）。% False は、データベースにないためです。
  • 兄弟（「いいえ」、「サンチョ私」）。% 誤り、同じ理由

このように、たとえば、次のように尋ねることができます: 兄弟(X, Y)、そして「;」を押し始めます。繰り返しなしですべての兄弟姉妹に会うこと。

また、a と b がデータベース内の人物であると仮定して、brother(a, b) と brother(b, a) を行うこともできます。一部のソリューションでは @< を使用して物事をテストし、brother(b, a) が失敗するため、これは重要です。

それで、それはあります。

于 2013-02-23T23:28:05.690 に答える