4

私は何時間も私を悩ませてきた2つの問題があります。connected/2二人がつながっているかどうかを判断することになっています。distance/3親族関係を測定することになっています。だが：

  1. 私trueはクエリに対して無限にsを取得し続けますconnected(x,y);
  2. そして、私はクエリNのために無限に増えていdistance(x,y,N)ます。助言がありますか？

これが私の事実です：

male(ted).
male(barney).
male(ranjit).
male(marshall).
male(tony).
male(swarley).
male(steve).
male(chuck).
male(john).
male(devon).
male(morgan).

female(robin).
female(lily).
female(wendy).
female(stellar).
female(abby).
female(victoria).
female(carina).
female(sarah).
female(ellie).

married(ted,      robin).
married(marshall, lily).
married(ranjit,   wendy).
married(stellar,  tony).
married(steve,    carina).
married(sarah,    chuck).
married(ellie,    devon).

father(ted,      barney).
father(ted,      ranjit).
father(marshall, wendy).
father(ranjit,   stellar).
father(tony,     abby).
father(tony,     swarley).
father(tony,     victoria).
father(steve,    chuck).
father(steve,    ellie).
father(chuck,    john).
father(devon,    morgan).

mother(robin,    barney).
mother(robin,    ranjit).
mother(lily,     wendy).
mother(wendy,    stellar).
mother(stellar,  abby).
mother(stellar,  swarley).
mother(stellar,  victoria).
mother(carina,   chuck).
mother(carina,   ellie).
mother(sarah,    john).
mother(ellie,    morgan).

今、私の述語：

parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).

son(X,Y) :-
    male(X),
    parent(Y,X).

daughter(X,Y) :-
    female(X),
    parent(Y,X).

sibling(X,Y) :-
    parent(Z,X),
    parent(Z,Y).

cousin(X,Y) :-
    parent(Z,X),
    parent(W,Y),
    parent(G,Z),
    parent(G,W).

ancestor(X,Y) :-
    parent(X,Z),
    ancestor(Z,Y).
ancestor(X,Y) :- parent(X,Y).

notmember(X,[]).
notmember(X,[H|T]) :- 
    X \= H,
    notmember(X,T).

connected(X,Y,_) :- X == Y.
connected(X,Y,Visited) :- 
    ancestor(X,Z),
    notmember(Z,Visited),
    connected(Z,Y,[Z|Visited]).
connected(X,Y,Visited) :- 
    ancestor(Z,X),
    notmember(Z,Visited),
    connected(Z,Y,[Z|Visited]).
connected(X,Y,Visited) :- 
    sibling(X,Z),
    notmember(Z,Visited),
    connected(Z,Y,[Z|Visited]).
connected(X,Y,Visited) :- 
    married(X,Z),
    notmember(Z,Visited),
    connected(Z,Y,[Z|Visited]).
connected(X,Y) :- connected(X,Y,[X]).

minimum(X,[X]).
minimum(X,[M,H|T]) :- 
    M =< H,
    minimum(X,[M|T]).
minimum(X,[M,H|T]) :-
    M > H,
    minimum(X,[H|T]).

distance(X,X,_,0).
distance(X,Y,Visited,N) :- 
    parent(X,Z),
    notmember(Z,Visited),
    distance(Z,Y,[Z|Visited],N1),
    N is N1+1.
distance(X,Y,Visited,N) :- 
    parent(Z,X),
    notmember(Z,Visited),
    distance(Z,Y,[Z|Visited],N1),
    N is N1+1.
distance(X,Y,N) :- distance(X,Y,[],N).

編集：ありがとう、私は今問題の半分を解決することができたと思います。@twintererのアドバイスを受けて、私はこのような述語を修正しました

connected(X,Y,_) :- X == Y.
connected(X,Y,V) :-
    married(X,Z),
    notmember(Z,V),
    connected(Z,Y,[Z|V]),!.
connected(X,Y,V) :-
    sibling(X,Z),
    notmember(Z,V),
    connected(Z,Y,[Z|V]),!.
connected(X,Y,V) :-
    parent(X,Z),
    notmember(Z,V),
    connected(Z,Y,[Z|V]),!.
connected(X,Y,V) :-
    parent(Z,X),
    notmember(Z,V),
    connected(Z,Y,[Z|V]),!.
connected(X,Y) :- connected(X,Y,[X]).

minimum(X,[X]).
minimum(X,[M,H|T]) :- 
    M =< H,
    minimum(X,[M|T]).
minimum(X,[M,H|T]) :-
    M > H,
    minimum(X,[H|T]).

count(X,[],0).
count(X,[X|T],N) :-
    count(X,T,N1),
    N is N1+1.
count(X,[H|T],N) :-
    X \== H,
    count(X,T,N1),
    N is N1.

distance(X,X,Visited,0) :-
    count(X,Visited,N),
    N =< 1, !.
distance(X,Y,Visited,N) :- 
    parent(X,Z),
    (notmember(Z,Visited)->
        distance(Z,Y,[Z|Visited],N1),
        N is N1+1
    ;
        fail
    ),!.
distance(X,Y,Visited,N) :- 
    parent(Z,X),
    (notmember(Z,Visited)->
        distance(Z,Y,[Z|Visited],N1),
        N is N1+1
    ;
        fail
    ),!.
distance(X,Y,N) :- 
    findall(N1,distance(X,Y,[X],N1),L),!,
    minimum(N,L),!.

しかし、今、新しい一連の問題があります

  1. 次のような任意のクエリを実行することはできませんdistance(X,y,n)
  2. connected(X,y)重複した結果を返すなどのクエリ

重複する結果を削除するには、その述語を使用することで達成できると思いますがfindall/3、実際にどのように実装できるかについてはわかりません。

4

1 に答える 1

5

1）無限ループで終わるとは思いませんが、プログラムに2人が接続されているすべての方法を探索させます。これは、非常に多くの数になります。おそらくそれらが接続されているかどうかだけに関心があるのでconnected/3、2人が接続されていると正常に判断したら、バックトラックを防ぐために句の最後にカットを追加する必要があります。

connected(X,Y,_) :- X == Y,!.
connected(X,Y,Visited) :- 
    ancestor(X,Z),
    notmember(Z,Visited),
    connected(Z,Y,[Z|Visited]),!.
...

2）コードをテストしたときに、Nの値が無限に増加することはありませんでしたが、それでもdistance/3述語は、2人がどのように接続されているかによって異なるパスを決定します。人によっては、最小距離が最初に計算されるわけではありません。の定義distance/3を次のように変更します。

distance(X,Y,N) :- 
    findall(N0, distance(X,Y,[],N0), Ns), !,
    minimum(N, Ns).

これはあなたのminimum/2述語を再利用しています。誤った選択ポイントを回避するために、この述語の最初の2つの節にカットを追加する必要があることに注意してください。

追加の質問について：

3）最小のNを探すことと、次数Nに一致する人を探すことを区別する必要があります。

distance(X,Y,N) :-
  nonground(N),!,
  findall(N0, distance(X,Y,[],N0), Ns), !,
  minimum(N, Ns).
distance(X,Y,N) :-
  distance(X,Y,[X],N).

また、に追加したカットを削除する必要がありますdistance/4。connected/3これは、 ！に追加されたカットとは異なります。

これらの2つのモードを区別しないようにするためのより良い方法はおそらくありますが、現時点で考えられるのは、（最小度を保証するために）ある種の幅優先探索を使用することだけです...

?- connected(X,victoria).4）例がありますか？のようなクエリに対して重複した回答が得られません。

于 2012-05-03T08:42:29.067 に答える