Prolog GNU - С этим трудно справиться, списки и рекурсия

Question

Итак, я до сих пор не до конца понимаю, как списки и рекурсия работают в прологе, возможно, поэтому у меня возникли проблемы с этим, но я даже не знаю, как начать эту проблему.

Есть список друзей.

f(a,b).
f(a,c).
f(a,d).
f(b,c).
f(b,e).
f(b,f).
f(c,e).
f(c,g).
f(g,e).
etc..

Я должен выяснить, является ли кто-то другом через кого-то, кроме двух друзей друзей.

Так, например, если бы я сделал

fof(a,e, List).

Тогда я должен получить

List = [a, b, e];
List = [a, c, e];
List = [a, c, g, e]; <-- anything past this point won't work

Таким образом, в основном вы проверяете себя, затем смотрите, дружат ли ваши друзья с person2, а затем смотрите, дружат ли их друзья с person2, и добавляются ли они в список.

не совсем уверен, как это выполнить.

Хорошо, у меня есть нечто похожее на то, что мне нужно.

fb(X,X,_).
fb(X,Y,List) :- 
    friend(X,Y),
    X \== Y,
    List = [X,Y].
fb(X,Y,List) :-
    friend(X,Z),friend(Z,Y),
    X \== Y, X \== Z, Z \== Y,
    List = [X,Z,Y].
fb(X,Y,List) :-
    friend(X,Z),friend(Z,Q),friend(Q,Y),
    X \== Y,X \== Z, X \== Q, Z \== Q, Z \== Y, Q \== Y,
    List = [X,Z,Q,Y].

Кажется, это работает, но, кажется, я мог бы сжать это с помощью рекурсии, просто не знаю, как.

Answer 1

Я предполагаю, что вы определили friend(X,Y) как истинное, если либо f(X,Y), либо f(Y,X).

Ваша проблема может быть рекурсивно решена путем добавления аргумента, который задает максимально допустимую длину пути, иуменьшая это перед каждым рекурсивным вызовом.

fof(X,X,[X],_).
fof(X,Z,[X|Path],N) :-
    N >= 1,
    friend(X,Y),
    M is N-1,
    fof(Y,Z,Path,M),
    \+ member(X,Path).  % no duplicates

Чтобы добраться до друга друга через макс.два посредника, т.е. в три этапа:

?- fof(a,e,L,3).
L = [a, b, c, e] ;
L = [a, b, e] ;
L = [a, c, e] ;
L = [a, c, g, e] ;
L = [a, c, b, e] ;
false.

?- fof(a,z,L,3).
false.