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.

问题在于，如果您问“兄弟（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/3和的组合。member/2

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

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

您可以通过比较消除一组：

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 是将解决方案减半的好方法。

您的第二个问题是 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是“兄弟”，c并且也是“兄弟” d——Prolog 两次生成该解决方案是正确的，因为有一个隐藏变量被实例化为两个不同的价值观。

一个更优雅的解决方案可能是用来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）。％乌拉卡的每个兄弟都没有重复
  • 兄弟（'乌拉卡'，'桑乔一世'）。% 是的，因为乌拉卡和桑乔我有同一个父亲和母亲。事实上，即使他们只有同一个母亲或同一个父亲，它也会返回真实的。有点脱离上下文但仍然有效，如果他们有三个或更多共同的父母，它仍然可以工作

它失败并显示以下内容：

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

所以像这样我可以，例如，问：兄弟（X，Y），然后开始按“;” 看到每一个兄弟姐妹，没有任何重复。

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

就这样。

于 2013-02-23T23:28:05.690 回答