1

まず文脈。プロローグでモデル化しようとしているのは、 2 つの別々のグラフであり、どちらも友人のグループを表しているため、両方に関係を置くことができますfriend(X,Y)。また、このモデルでは友情が相互に関係していないという意味がないため、関係も入れておきfriend(Y, X)ます。

したがって、これは、両方のグラフの要素間に双方向の関係があることを意味します。

例えば：

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

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

ではとfoo1関連しfoo2、 と も同様ですが、最初の 2 つは別の 2 と関連していません。foo3foo4

これは友人のグループであるため、同じ友人グループの中で同じグループの 2人が友人ではないという意味もありません。

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

私が抱えている問題は、あるグループの1人が他のグループの人の友達であるかどうかを確認しようとするときです. つまり、グラフの 1 つの要素が他のグラフの別の要素と関連しているかどうかを確認します。

予想される結果であるfalse を取得する代わりに、コンパイラ (この場合は SWI-Prolog)は out of local stack というエラーを返します。

これを解決する方法を知りたいです。

編集

したがって、CapelliC のおかげで、この問題に対処することができました。主な目的は完了しましたが、副次的な問題があるため、これから説明します。

グラフ1 グラフ2

これらは私が取り組んでいる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を使用しても、false になります。また、実行する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

2 番目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 に答える
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 は、完全な順序付けを強制することにより、循環を防ぐ 1 つの便利な方法を提供します。ここではそれが正しいアプローチだとは思いませんが、その理由をはっきりとは言えません。ただし、できることの 1 つは、訪問したリストを提供してチェックし、既に行ったノードを再入力しないようにすることです。そのコードは次のようになります。

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