2

私はプロローグにこのプログラムを持っています。ここでは、基本的に人々のグラフを定義し、どの人々が関連しており、どの派閥であるかを示すいくつかの述語を作成する必要があります。事実は次のとおりです。

graph([person(susan, [reed, jen, andrzej, jessica]),
   person(reed, [tony, jessica]),
   person(jessica, [jen,susan]),
   person(tony, []),
   person(ken, [andrzej]),
   person(jen, [tony, susan, jessica]),
   person(andrzej, [susan, ken])]).

そして、これがクリークという名前の述語の定義です。パラメータとしてグラフ G と人物のリストを取り、リスト内の人物が実際に友人のグループであるかどうかをチェックしようとします (つまり、述語 goodfriends は、リスト内の人物の各ペアに対して真です)。

clique(G, [FriendOne, FriendTwo]):-
  goodfriends(G, FriendOne, FriendTwo).
clique(G, [FriendOne | FriendList]):-
  atLeastTwoElements(FriendList),
  clique(G, FriendList),
  goodFriendWith(G, FriendOne, FriendList).

clique が行うことは、リストが 2 人だけで構成されている場合、この 2 人が仲良しかどうかをチェックすることです。これが本当なら、2人の間に派閥があります。人のリストに 2 人以上の人がいる場合、リストの先頭ごとに、つまり、リストの末尾にいる残りの人と良い友達かどうかをチェックし、それをすべてのリストに対して再帰的に行います。人。以下は、クリークが機能するための残りのヘルパー述語の定義です。

goodfriends(G, FriendOne, FriendTwo):-
  getPerson(G, FriendOne, PersonOne),
  getPerson(G, FriendTwo, PersonTwo),
  hasFriend(PersonOne, FriendTwo),
  hasFriend(PersonTwo, FriendOne).

%% checks if this friend is goodfriend with all these friends
goodFriendWith(_, _, []).
goodFriendWith(G, FriendOne, [FriendTwo | FriendList]):-
  goodFriendWith(G, FriendOne, FriendList),
  goodfriends(G, FriendOne, FriendTwo).

%% gets specific person by a name from the graph
getPerson([person(Name, Friends)|_], Name, person(Name, Friends)).
getPerson([_|T], Name, Result):-
  getPerson(T, Name, Result).

%% checks if a person has a certain friend
hasFriend(person(_, Friends), Friend):-
  member_(Friend, Friends).

member_(X, [X|_]).
member_(X, [_|Tail]) :- member_(X, Tail).
atLeastOneElement([_|_]).
atLeastTwoElements([_,_|_]).

質問

述語「クリーク」をテストするために、runner という名前の述語を作成すると、次のようになります。

runner(R):-
  graph(G),  
  clique(G, R).

グラフ内のすべてのクリークを返したいのですが、結果は次のとおりです。

?- runner(R).
R = [susan, jessica] ;
R = [susan, jen] ;
R = [susan, andrzej] ;
R = [jessica, susan] ;
R = [jessica, jen] ;
R = [ken, andrzej] ;
R = [jen, susan] ;
R = [jen, jessica] ;
R = [andrzej, susan] ;
R = [andrzej, ken] ;
R = [jen, susan, jessica] ;
R = [jessica, susan, jen] ;
R = [jen, jessica, susan] ;
R = [susan, jessica, jen] ;
R = [jessica, jen, susan] ;
R = [susan, jen, jessica] ;
ERROR: Out of local stack

再帰の何が間違っていますか? 正しい結果が得られることはわかっていますが、何らかの理由で、すべての結果が再帰的に表示されます。

前もって感謝します。

4

1 に答える 1

3

あなたのような純粋で単調なプログラムには、簡単なデバッグ手法があります。falseプログラムに目標を追加するだけです。結果のプログラムがまだループする場合は、残りの可視部分を修正する必要があります。(もっとエラーがあるかもしれませんが、その部分を直さない限り問題は解決しません)

これが私がこれまでに得たものです：

ランナー(R):-
  グラフ(G)、
  clique(G, R), false .

clique(G, [FriendOne, FriendTwo]):- false , 
  goodfriends(G, FriendOne, FriendTwo).
clique(G, [FriendOne | FriendList]):-
  atLeastTwoElements(FriendList)、
  goodFriendWith(G, FriendOne, FriendList), false ,
   clique(G, FriendList) .

したがって、1 つまたは 1 つの問題は にありますgoodFriendWith。次のように無限に多くのリストに対して定義が成功するのは、少しイライラすることがわかりました。

?- length(L,N),
   maplist(=(jessica),L),
   goodFriendWith(
      [  person(susan,[reed,jen,andrzej,jessica]),
         person(reed,[tony,jessica]),
         person(jessica,[jen,susan]),
         person(tony,[]),
         person(ken,[andrzej]),
         person(jen,[tony,susan,jessica]),
         person(andrzej,[susan,ken])],
      susan,
      L).
L = [],
N = 0 ;
L = [jessica],
N = 1 ;
L = [jessica, jessica],
N = 2 ;
L = [jessica, jessica, jessica],
N = 3 ;
L = [jessica, jessica, jessica, jessica],
N = 4 ;
L = [jessica, jessica, jessica, jessica, jessica],
N = 5 ...

したがって、2 人だけでも、さまざまな解決策が無限にあります。それは終了できません！これを修正する必要があります。

または、さらに正確に言えば：

?- goodFriendWith([person(susan,[jessica]),person(jessica,[susan])],susan,L).
L = [] ;
L = [jessica] ;
L = [jessica, jessica] ;
L = [jessica, jessica, jessica] ;
L = [jessica, jessica, jessica, jessica] ;
L = [jessica, jessica, jessica, jessica, jessica]

この目標は、有限数の解を生成する必要があります。ただし、無数にあります。

あなたは結果に驚いているので、デバッグを続けましょう。さらに明確にするために、追加の目標を追加し(=)/2ます。これらの目標は、プログラムも専門化します。

goodFriendWith(_, _, []) :- false .
goodFriendWith(G, FriendOne, [FriendTwo | FriendList]):-
  FriendOne = スーザン、
   FriendTwo = ジェシカ、
  仲良し(G、FriendOne、FriendTwo)、
  goodFriendWith(G, FriendOne, FriendList), false .

?- goodFriendWith([人(スーザン,[ジェシカ]),人(ジェシカ,[スーザン])],スーザン,L).

繰り返しますが、クエリはループします。あなたは本当に今問題を見るべきです。

于 2014-09-27T15:26:05.310 に答える