代码之家 › 专栏 › 技术社区 › Matt

Prolog GNU-很难处理这个、列表和递归

prolog recursion list

2

Matt · 技术社区 · 16 年前

所以,我仍然不完全理解prolog中的列表和递归是如何工作的,这可能是我遇到麻烦的原因,但我甚至不知道如何开始这个问题。

有一份朋友名单。

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].

这似乎是可行的,但我似乎可以用递归来压缩它,只是不确定如何压缩。

1 回复 | 直到 16 年前

1

Fred Foo 16 年前

我想你已经定义了 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.