4

我有两个问题困扰了我好几个小时。connected/2应该判断两个人是否有联系；distance/3应该衡量亲属关系。但：

  1. 对于查询，我不断得到trues 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）我不认为你以无限循环结束，但是你让你的程序探索两个人联系的所有方式，这将是一个非常大的数字。由于您可能只对他们是否完全连接感兴趣，因此您应该在子句末尾添加剪切，以connected/3防止在您成功确定两个人连接后回溯，例如：

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

2）当我测试你的代码时，我没有得到 N 的无限增加值，但distance/3谓词仍然会确定两个人如何连接的不同路径。根据人的不同，最小距离不会是第一个被计算的。我会将 的定义更改为distance/3如下所示：

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

这是重用您的minimum/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！

可能有更好的方法可以避免区分这两种模式，但目前我能想到的只是使用某种广度优先搜索（以保证最小程度）......

4）我没有得到重复的答案，比如?- connected(X,victoria).你有例子吗？

于 2012-05-03T08:42:29.067 回答