1

首先是上下文。我试图用 prolog 建模的是两个分开的图，都代表一组朋友，所以我可以在他们两个中放置关系friend(X,Y)，并且，因为它没有意义，所以在这个模型中友谊不是相互的，我也把关系friend(Y, X)。

所以这意味着两个图在它们的元素之间都有双向关系。

例如：

friend(foo1, foo2).
friend(foo2, foo1).

friend(foo3, foo4).
friend(foo4, foo3).

其中与 ,foo1相关foo2, and 也是如此foo3,foo4但前两个与另外两个无关。

因为是一群朋友，所以在同一个朋友群里，同一个群里的两个人不是朋友也是没有意义的，所以我用递归来判断一个人是否是另一个人的朋友。

definitivefriend(X, Z) :- friend(X, Z). 
definitivefriend(X, Z) :- friend(X, Y), definitivefriend(Y, Z).

我遇到的问题是当我尝试检查一组中的一个人是否是另一组的一个人的朋友时。换句话说，检查一个图的一个元素是否与另一个图的另一个元素相关。

编译器（在本例中为 SWI-Prolog）没有得到 false （这是预期的结果），而是给了我out of local stack 的错误。

我想知道如何解决这个问题。

编辑

所以感谢 CapelliC，我有一个解决这个问题的方法。因为主要目标已经完成，但是还有一个次要问题我从现在开始描述它。

图1 图2

这是我正在使用的两个图表。请记住，我之前说过，两个图都是双向的。

这是我在序言中的程序：

writeit :- write('Frienship').
definitivefriend(X, Z) :- friend(X, Z), friend(Z, X).   
definitivefriend(X, Y) :- friend(X, Z), X @< Z, definitivefriend(Z, Y), Y \= X.
friend(amanda, ryan).       % graph1 %
friend(ryan, amanda).
friend(ryan, lisa).
friend(lisa, ryan).
friend(bryan, ryan).
friend(ryan, bryan).
friend(sara, ryan).
friend(ryan, sara).
friend(sara, simone).
friend(simone, sara).       % graph2 %
friend(sandra, jeff).
friend(jeff, sandra).
friend(betty, jeff).
friend(jeff, betty).
friend(jeff, antonia).
friend(antonia, jeff).
friend(jeff, oskar).
friend(oskar, jeff). 
friend(jeff, leslie).
friend(leslie, jeff).

这是我得到的一些输出

?- definitivefriend(amanda, ryan).
true .                         % It's correct, both nodes are neighbours %

?- definitivefriend(amanda, simone).
true .                         % It's correct, both nodes are in the same graph %

?- definitivefriend(ryan, simone).
true .                         % It's correct, same explanation as before %

?- definitivefriend(simone, amanda).
false.                         % It's wrong, expected result is true %

?- definitivefriend(ryan, jeff).
false.                         % It's correct, nodes are in different graphs %

?- definitivefriend(amanda, leslie).
false.                         % It's correct, same explanation as before %

?- definitivefriend(sandra, oskar).
false.                         % It's wrong, expected result is true %

?- definitivefriend(oskar, sandra).
false.                         % It's wrong, expected result is true %

?- definitivefriend(betty, oskar).
true .                         % It's correct, both nodes are in the same graph %

?- definitivefriend(oskar, betty).
false.                         % It's wrong, expected result is true %

正如我在评论中所说，即使有同一张图的某些元素（除了相邻的元素），也会definitivefriend给我错误的信息。在某些情况下，当我执行时definitivefriend(X, Y)我得到了真实，但是当我执行时definitivefriend(Y, X)我得到了错误。

4

3 回答 3

2

我觉得你没有以正确的方式建模，无论如何这似乎有效（滥用 Jean-Bernard 的建议，+1）

definitivefriend(X, Y) :-
    friend(X, Y),
    friend(Y, X).

definitivefriend(X, Y) :-
    friend(X, Z), X @< Z,
    definitivefriend(Z, Y), Y \= X.

编辑：这不适用于您的模型。除了遵循丹尼尔的建议（+1）之外，我看不到任何其他方式。

于 2013-06-13T13:27:09.523 回答
1

基本上，问题在于周期。您的图表是非循环的，但您的代码不是。这是问题。假设我给出查询:- definitivefriend(foo1, foo2).。是什么阻止 Prolog 像这样扩展它：

definitivefriend(foo1, foo2) 
:- friend(foo1, foo2), definitivefriend(foo2, foo2).                     % by clause 2
:- friend(foo1, foo2), friend(foo2, foo1), definitivefriend(foo1, foo2). % by clause 2

:- friend(foo1, foo2), friend(foo2, foo1), friend(foo1, foo2), 
   definitivefriend(foo2, foo2).                                         % by clause 2

等等

@Jean-Bernard Pellerin 通过强制总排序提供了一种防止循环的有用方法。我认为这不是正确的方法，但我不能完全说明原因。但是，您可以做的一件事是提供一个访问过的列表来检查，而不是重新输入您已经访问过的节点。该代码将如下所示：

definitivefriend(X, Z) :- definitivefriend(X, Z, [X]).

definitivefriend(X, Y, Visited) :- 
    friend(X, Y), \+ memberchk(Y, Visited).
definitivefriend(X, Z, Visited) :- 
    friend(X, Y), \+ memberchk(Y, Visited), 
    definitivefriend(Y, Z, [Y|Visited]).
于 2013-06-13T05:35:53.883 回答
1

对于您的第二definitivefriend条规则，添加 X < Y 的条件。这将避免循环。然后只需添加一个规则：

definitivefriend(X,Y) :- definitivefriend(Y,X)

就像现在一样，您可以拥有：

definitivefriend(1,2) :- friend(1,3), definitivefriend(3,2)
definitivefriend(3,2) :- friend(2,1), definitivefriend(1,2)

这导致无限递归

于 2013-06-12T22:50:35.750 回答