Пролог - получение списка друзей друзей

Я изо всех сил пытаюсь получить достойный результат,

У меня есть друзья,

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 (это означает друзья b, b2, b3) и друзья c. Получение списка:

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

Я пытаюсь все. Я могу получить только прямых друзей или всех друзей друзей.

Помощь!!


recursion prolog prolog-findall
person Daniel Fialho    schedule 09.05.2018    source источник
comment
Определите предикат friend_of_friend_of_friend для моделирования отношений друзей уровня 3 и используйте для этого findall. Это делает отношение проверяемым изолированно, упрощает вызов findall и не включает временные переменные, которые вызывают у вас проблемы.   -  person Isabelle Newbie    schedule 09.05.2018
comment
Вам нужно определить предикат, который определяет отношения между непрямыми друзьями. Это будет рекурсивное правило. Если вам нужно ограничить глубину, вы можете включить аргумент (счетчик), который ограничивает глубину рекурсии.   -  person lurker    schedule 09.05.2018

Ответы (2)


arrow_upward
1
arrow_downward

Следующее означает 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]
person Rafalon    schedule 09.05.2018
comment
большое спасибо. Но если вы можете помочь мне еще в одном. я хотел сделать что-то вроде бесконечной рекурсивной части, но мне нужно общее правило, которое для заданного «N» останавливает рекурсию. например для N=0 -> List=[] , для N=1 -> прямые друзья. Я пытаюсь использовать аккумуляторы для остановки рекурсии, но безуспешно. - person Daniel Fialho; 09.05.2018
comment
Вы можете использовать что-то вроде recursive_friend(X,Y,N), а внутри предиката использовать N > 0, M is N - 1 и изменить рекурсивный вызов на recursive_friend(Z,Y,M) - редактировать: я только что посмотрел ответ Таса, и он похож на то, что он сделал. - person Rafalon; 12.05.2018

arrow_upward
4
arrow_downward

Для предиката, который находит друзей на заданном расстоянии, как вы просили в комментариях, вам понадобятся три аргумента, то есть два друга и расстояние. Дадим ему красивое реляционное имя, скажем, 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].

Однако из-за использования >/2 и 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)-версия предиката теперь напоминает истинное отношение, как следует из его реляционного имени.

person tas    schedule 09.05.2018