Prolog - 获取朋友的朋友列表

Prolog - getting a list of friends of friends

我正在努力获得一个不错的结果,

我有一些朋友,

friend(a,b).
friend(a,b2).
friend(a,b3).
friend(b,c).
friend(c,d).
friend(d,e).  
friend(e,f).

使用 findall(X,friend(a,X),List) 我得到了 a

的所有直接朋友
List=[b,b2,b3].

比如我想获取a的3级好友列表,比如我想要a的直接好友,a好友的好友(它表示 bb2b3) 的朋友和 c 的朋友。获取列表:

List=[b,b2,b3,c,d].

我正在尝试一切。我只能得到直接朋友或朋友的所有朋友。

求助!!

以下代表3级友情。正如评论中所说,如果你想要更多,你可能想要寻找递归。

% my friend is my friend
friend_of_friend(X,Y):-
    friend(X,Y).
% the friend of my friend is my friend
friend_of_friend(X,Y):-
    friend(X,Z),
    friend(Z,Y).
% the friend of the friend of my friend is my friend
friend_of_friend(X,Y):-
    friend(X,A),
    friend(A,B),
    friend(B,Y).

然后

findall(X, friend_of_friend(a,X), List).

给出:

List = [b, b2, b3, c, d]

这代表无限递归友谊:

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

并给出:

List = [b, b2, b3, c, d, e, f]

对于在给定距离内找到朋友的谓词,如您在评论中所要求的,您需要三个参数,即两个朋友和距离。让我们给它一个很好的关系名称,比如 friend_of_maxdist/3。现在让我们试着描述一下关系:

friend_of_maxdist(F1,F2,D) :-
   D > 0,                        % if the distance is greater than 0
   friend(F1,F2).                % F2 is a friend in range
friend_of_maxdist(F1,F2,D) :-
   D > 1,                        % if the distance is greater than 1
   D0 is D-1,                    
   friend(F1,X),                 % X is an intermediary friend
   friend_of_maxdist(X,F2,D0).   % of distance minus 1

这个谓词将给定距离内的所有朋友一一送达:

?- friend_of_maxdist(a,F2,1).
F2 = b ;
F2 = b2 ;
F2 = b3 ;
false.

?- friend_of_maxdist(a,F2,2).
F2 = b ;
F2 = b2 ;
F2 = b3 ;
F2 = c ;
false.

?- friend_of_maxdist(a,F2,3).
F2 = b ;
F2 = b2 ;
F2 = b3 ;
F2 = c ;
F2 = d ;
false.

现在您可以将所有解决方案收集在一个列表中。我将使用 bagof/3 显示示例查询,请参阅下文了解原因:

?- bagof(F2,friend_of_maxdist(a,F2,1),L).
L = [b, b2, b3].

?- bagof(F2,friend_of_maxdist(a,F2,2),L).
L = [b, b2, b3, c].

?- bagof(F2,friend_of_maxdist(a,F2,3),L).
L = [b, b2, b3, c, d].

然而,由于 >/2is/2 的使用,如果第三个参数不为基础,friend_of_maxdist/3 会产生错误,例如对于查询:

?- friend_of_maxdist(a,F2,N).
ERROR: >/2: Arguments are not sufficiently instantiated

如果您不打算以这种方式使用谓词,您就完了。否则你可能想看看 CLP(FD)。对上面的代码做如下改动:

:- use_module(library(clpfd)).   % <- new

friend_of_maxdist(F1,F2,D) :-
   D #> 0,                       % <- change
   friend(F1,F2).
friend_of_maxdist(F1,F2,D) :-
   D #> 1,                       % <- change
   D0 #= D-1,                    % <- change
   friend(F1,X),
   friend_of_maxdist(X,F2,D0).

如果您现在尝试有问题​​的查询,您会得到答案而不是错误。但是,您会在答案中获得剩余目标(有关详细信息,请参阅 documentation):

?- friend_of_maxdist(a,F2,N).
F2 = b,
N in 1..sup ;
F2 = b2,
N in 1..sup ;
F2 = b3,
N in 1..sup ;
F2 = c,
N in 2..sup,
_G778+1#=N,
_G778 in 1..sup ;
F2 = d,
N in 3..sup,
_G1264+1#=N,
_G1264 in 2..sup,
_G1288+1#=_G1264,
_G1288 in 1..sup ;
F2 = e,
N in 4..sup,
_G1855+1#=N,
_G1855 in 3..sup,
_G1879+1#=_G1855,
_G1879 in 2..sup,
_G1903+1#=_G1879,
_G1903 in 1..sup ;
F2 = f,
N in 4..sup,
_G2446+1#=N,
_G2446 in 4..sup,
_G2470+1#=_G2446,
_G2470 in 3..sup,
_G2494+1#=_G2470,
_G2494 in 2..sup,
_G2518+1#=_G2494,
_G2518 in 1..sup ;
false.

要获取 N 的实际数字而不是范围,请限制其范围并为其添加标签:

?- N in 0..3, friend_of_maxdist(a,F2,N), label([N]).
N = 1,
F2 = b ;
N = 2,
F2 = b ;
N = 3,
F2 = b ;
N = 1,
F2 = b2 ;
N = 2,
F2 = b2 ;
N = 3,
F2 = b2 ;
N = 1,
F2 = b3 ;
N = 2,
F2 = b3 ;
N = 3,
F2 = b3 ;
N = 2,
F2 = c ;
N = 3,
F2 = c ;
N = 3,
F2 = d ;
false.

现在您可以像上面那样收集解决方案:

?- bagof(F2,(N in 0..3, friend_of_maxdist(a,F2,N), label([N])),L).
N = 1,
L = [b, b2, b3] ;
N = 2,
L = [b, b2, b3, c] ;
N = 3,
L = [b, b2, b3, c, d].

在上面的查询中,您可以看到为什么我建议使用 bagof/3 来收集解决方案:N 绑定到一个值,然后您可以获得与该值相关的所有解决方案。如果你用 findall/3 做同样的尝试,你会在一个列表中得到三个列表的所有元素:

?- findall(F2,(N in 0..3, friend_of_maxdist(a,F2,N), label([N])),L).
L = [b, b, b, b2, b2, b2, b3, b3, b3|...].

要获得与 bagof/3 相同的解决方案,您必须明确告诉 bagof/3 不要在目标中绑定 N

?- bagof(F2,N^(N in 0..3, friend_of_maxdist(a,F2,N), label([N])),L).
L = [b, b, b, b2, b2, b2, b3, b3, b3|...].

请注意,正如其关系名称所示,谓词的 CLP(FD) 版本现在类似于真实关系。