1

我在 Prolog 脚本中有一组可能性，并希望找到最大的集合，其中应用于所有列表对的特定谓词评估为真。

一个简化的例子是一组人，你想找到最大的一组，其中所有人都是共同的朋友。所以，给定：

% Four-way friend CIRCLE
link(tom, bill).
link(bill, dick).
link(dick, joe).
link(joe, tom).

% Four-way friend WEB
link(jill, sally).
link(sally, beth).
link(beth, sue).
link(sue, jill).
link(jill, beth).
link(sally, sue).

% For this example, all friendships are mutual
friend(P1, P2) :- link(P1, P2); link(P2, P1).

可能的匹配应该是（为了清楚起见，按字母顺序显示每一对）：

% the two-person parts of both sets :
[bill, tom], [bill, dick], [dick, joe], [joe, tom],
[jill, sally], [beth, sally], [beth, sue], [jill, sue],
  [beth, jill], [sally, sue]

% any three of the web :
[beth, jill, sally], [beth, sally, sue], [beth, jill, sue]

% and the four-person web :
[beth, jill, sally, sue]

我可以找到所有两人匹配：

% Mutual friends?
friendCircle([Person1, Person2]) :-
    friend(Person1, Person2),
    % Only keep the alphabetical-order set:
    sort([Person1, Person2], [Person1, Person2]).

但后来我在试图找到更大的集合时遇到了困难：

friendCircle([Person1|Tail]) :-
    friendWithList(Person1, Tail),
    Tail = [Person2|Tail2],
    % Only keep if in alphabetical order:
    sort([Person1, Person2], [Person1, Person2]),
    friendWithList(Person2, Tail2).

% Check all members of the list for mutual friendship with Person:
friendWithList(Person, [Head|Tail]) :-
    friend(Person, Head), % Check first person in list
    friendWithList(Person, Tail). % Check rest of list

但是当我运行它时，在枚举了两人列表之后，Prolog 只是挂起并最终耗尽了堆栈空间。我究竟做错了什么？

我正在尝试做的是浏览网络，对于一个有五个朋友的网络，它会检查这些对中的每一对的朋友状态：

(1,2) (1,3), (1,4), (1,5) % Compare element 1 with the rest of the list
      (2,3), (2,4), (2,5) % Remove element 1 and repeat
             (3,4), (3,5)
                    (4,5)

这就是我认为我在规则中的两个friendsWithList/2电话正在做的事情。friendCircle/1

4

3 回答 3

2

我相信你正在进入一个循环。在建立朋友圈时，您应该检查您是否已经“访问”过朋友。

我对此的看法：

friendCircle(Friends):-
  findall(SFriendCircle,
    (
      friend(Person1, Person2),
      friendCircle([Person1, Person2], FriendCircle),
      sort(FriendCircle, SFriendCircle)
     ),
    LFriends),
  sort(LFriends, SFriends),
  member(Friends, SFriends).

friendCircle([From|Tail], Friends):-
  friend(From, To),
  \+ member(To, Tail),
  forall(member(Friend, Tail), friend(To, Friend)),
  friendCircle([To,From|Tail], Friends).
friendCircle(Friends, Friends).

测试：

?- friendCircle(Friends).
Friends = [ben, tom] ;
Friends = [dick, joe] ;
Friends = [dick, joe, tom] ;
Friends = [dick, tom] ;
Friends = [joe, tom].
于 2012-04-27T14:25:56.063 回答
1

这是我最终使用的清理版本（带有注释以增加清晰度），它消除了bagof,sort和findall调用（并且forall，如果您的序言没有）：

% Four-way friend CIRCLE
link(tom, bill).
link(bill, dick).
link(dick, joe).
link(joe, tom).

% Four-way friend WEB
link(jill, sally).
link(sally, beth).
link(beth, sue).
link(sue, jill).
link(jill, beth).
link(sally, sue).

% Assume if one is friends with the other, it's reflexive
friend(Person1, Person2) :- (link(Person1, Person2); link(Person2, Person1)).

% Replace a forall/2 call
friendWithList(_, []).
friendWithList(Person, [Friend|Tail]) :-
    friend(Person, Friend),
    friendWithList(Person, Tail).

% Build a friend web
friendCircle(Friends):-
    friend(Person1, Person2), % Start with two random friends...
    Person1 @=< Person2, % ...who are in alphabetical order.
    validCircle([Person1, Person2], Friends). % Build a web with them.


% Given a valid web in the first parameter,
% find a valid web and put it in the second parameter.

% Because the input is a valid web, the simplest output is itself:
validCircle(Friends, Friends).

% The other option is to try and grow the web:
validCircle([Person|Tail], Output):-
    friend(Person, NewGuy), % Grab a friend of the first person in the list... 
    NewGuy @=< Person, % ...who alphabetically comes before that person...
    \+ member(NewGuy, Tail), % ...and we don't have in the list already.

    % Check that the new guy is friends with everyone already on the list
    % If you have the forall/2 predicate,
    % you can swap the comment on the next two lines
    friendWithList(NewGuy, Tail), 
    %forall(member(ExistingFriend, Tail), friend(NewGuy, ExistingFriend)),

    % Build a valid circle with the new inputs,
    % and put that in the output slot.
    validCircle([NewGuy,Person|Tail], Output).
于 2012-04-27T18:55:41.160 回答
0

这个观察

?- setof(Friend, friend(Person, Friend), Friends).
Person = beth,
Friends = [jill, sally, sue] ;
Person = bill,
Friends = [dick, tom] ;
....

引导我写：

pair(P1, A, B) :-
    append(_, [A|As], P1),
    append(_, [B|_], As).

circles(Cs) :-
    setof(C, X^P^A^B^(setof(Person, friend(Person, X), P),
              forall(pair(P, A, B), friend(A, B)),
              sort([X|P], C)
             ), Cs).

有了这个结果

?- circles(L).
L = [[beth, jill, sally, sue]].
于 2012-04-27T20:09:36.233 回答