时间戳

首页 > 解决方案 > Prolog - 获取朋友的朋友列表

recursion - Prolog - 获取朋友的朋友列表

问题描述

我正在努力获得一个体面的结果，

我有几个朋友，

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)I'm getting all direct friends ofa

List=[b,b2,b3].

例如，我想获取 的 3 级好友列表a，例如我想要 的直接好友a、好友的好友a（即b、b2、b3的好友）和 的好友c。获取列表：

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

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

帮助！！

标签： recursionprologprolog-findall

解决方案

对于在给定距离内查找朋友的谓词，正如您在评论中要求的那样，您需要三个参数，即两个朋友和距离。让我们给它一个很好的关系名称，比如说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].

但是，由于使用>/2and is/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).

如果您现在尝试有问题​​的查询，您将得到答案而不是错误。但是，您会在答案中获得剩余目标（有关详细信息，请参阅文档）：

?- 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) 版本现在类似于真正的关系，正如其关系名称所暗示的那样。

推荐阅读