1

Prolog スクリプトに一連の可能性があり、リストのすべてのペアに適用される特定の述語が true と評価される最大のセットを見つけたいと考えています。

単純化された例は、一連の人々であり、すべてが相互の友人である最大のグループを見つけたいと考えています。したがって、与えられた：

% 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]

2 人で一致するものはすべて次のように見つけることができます。

% 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

しかし、それを実行すると、2 人のリストを列挙した後、Prolog がハングアップし、最終的にスタック スペースが不足します。私は何を間違っていますか？

私がやろうとしているのは、ウェブを歩くことです。これは、5人の友達のウェブの場合、これらのペアのそれぞれの友達のステータスをチェックすることになります:

(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内の 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て）。sortfindallforall

% 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 に答える