不要在Prolog中重复解决方案

Question

假设您有一个包含以下内容的数据库:

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.

问题是,如果你问"兄弟(X,Y)." 并开始按";" 你会得到多余的结果,如:

• X = a,Y = b;
• X = b,Y = a;
• X = a,Y = b;
• X = b,Y = a;

我能理解为什么我得到这些结果,但我正在寻找一种方法来解决这个问题.我能做什么？

Answer 1

考虑到您的一组真理，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 运算符 -- 停止“水平”扩展，一旦发现分支有效，或添加一些避免多个解决方案的语句。

有关更多信息，请查看统一算法。

Answer 2

首先，我建议不要动态更新 Prolog 数据库。出于某些原因，请考虑文章 “如何处理 Prolog 动态数据库？” .

您可以使用内置setof/3和的组合member/2，正如@DanielLyons 在他的回答中所建议的那样。

作为另一种选择，请考虑以下setof/3以一种相当不寻常的方式使用的查询，如下所示：

?- setof(t,brother(X,Y),_).
X = a, Y = b ;
X = b, Y = a.

Answer 3

我得到了答案。

% 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）。% 乌拉卡的每个兄弟都没有重复
• 兄弟（'乌拉卡'，'桑乔一世'）。%是的，因为乌拉卡和桑乔有同一个父亲和母亲。事实上，即使他们只有同一个母亲或同一个父亲，它也会返回 true。有点偏离上下文，但仍然有效，如果他们有三个或更多共同父母，它仍然有效

它失败并显示以下内容：

• 兄弟（X，X）。% 错误，因为是同一个人
• 兄弟（'不'，X）。% False 因为 not 甚至不在数据库中
• 兄弟（'不'，'桑乔一世'）。% 错误，原因相同

例如，我可以这样问：brother(X, Y)，然后开始按“;” 见到每一位弟兄姊妹，没有任何重复。

我也可以做兄弟（a，b）和兄弟（b，a），假设a和b是数据库中的人。这很重要，因为某些解决方案会使用 @< 来测试事物，而 Brother(b, a) 会失败。

就是这样。