时间戳

首页 > 解决方案 > 在 Prolog 中递归创建后代列表

list - 在 Prolog 中递归创建后代列表

问题描述

我对 Prolog 真的很陌生，并且正在努力递归地附加到列表中。我正在尝试创建一个程序，告诉您一个人是否是另一个人的后代，以及他们之间的后代列表。例如，样本数据和所需的输出：

parent(greatgrandma, grandma).
parent(grandma, mom).
parent(mom, daughter).

?- relatives(greatgrandma, daughter, Lineage).
Lineage = [greatgrandma, grandma, mom, daughter]

?- relatives(mom, son, Lineage).
False.

我能够递归搜索以检查两个人是否与以下代码相关，并将其作为测试基础案例......

relatives(X, Y, Lineage):- isChild(X,Y, Lineage).
isChild(X,Y, Lineage):- parent(X,Y), append([X], [Y], Lineage).
isChild(X,Y, Lineage):- parent(X,Z), isChild(Z,Y, Lineage).

但是到目前为止，我尝试从这个后代搜索中建立一个列表的一切都没有奏效。这是我得到的最接近的：

relatives(X, Y, Lineage):- append([X], Lineage, NewLineage), isChild(X,Y, NewLineage).
isChild(X,Y, Lineage):- parent(X,Z), append(Lineage, [Z], NewLineage), isChild(Z,Y, NewLineage).
isChild(X,Y, Lineage):- parent(X,Y), append(Lineage, [Y], NewLineage).

[trace]  ?- relatives(grandma, daughter, P).
   Call: (10) relatives(grandma, daughter, _12442) ? creep
   Call: (11) lists:append([grandma], _12442, _12904) ? creep
   Exit: (11) lists:append([grandma], _12442, [grandma|_12442]) ? creep
   Call: (11) isChild(grandma, daughter, [grandma|_12442]) ? creep
   Call: (12) parent(grandma, _13040) ? creep
   Exit: (12) parent(grandma, mom) ? creep
   Call: (12) lists:append([grandma|_12442], [mom], _13136) ? creep
   Exit: (12) lists:append([grandma], [mom], [grandma, mom]) ? creep
   Call: (12) isChild(mom, daughter, [grandma, mom]) ? creep
   Call: (13) parent(mom, _13272) ? creep
   Exit: (13) parent(mom, daughter) ? creep
   Call: (13) lists:append([grandma, mom], [daughter], _13368) ? creep
   Exit: (13) lists:append([grandma, mom], [daughter], [grandma, mom, daughter]) ? creep
   Call: (13) isChild(daughter, daughter, [grandma, mom, daughter]) ? creep
   Call: (14) parent(daughter, _13510) ? creep
   Fail: (14) parent(daughter, _13554) ? creep
   Redo: (13) isChild(daughter, daughter, [grandma, mom, daughter]) ? creep
   Call: (14) parent(daughter, daughter) ? creep
   Fail: (14) parent(daughter, daughter) ? creep
   Fail: (13) isChild(daughter, daughter, [grandma, mom, daughter]) ? creep
   Redo: (12) isChild(mom, daughter, [grandma, mom]) ? creep
   Call: (13) parent(mom, daughter) ? creep
   Exit: (13) parent(mom, daughter) ? creep
   Call: (13) lists:append([grandma, mom], [daughter], _13914) ? creep
   Exit: (13) lists:append([grandma, mom], [daughter], [grandma, mom, daughter]) ? creep
   Exit: (12) isChild(mom, daughter, [grandma, mom]) ? creep
   Exit: (11) isChild(grandma, daughter, [grandma]) ? creep
   Exit: (10) relatives(grandma, daughter, []) ? creep
P = [] .

因此，我以 [奶奶，妈妈，女儿] 的正确顺序获取列表，但我不知道如何返回 P 的值而不是空列表。此外，使用 'son' 的测试会导致使用此代码的无限递归循环，但不会使用前面的基本情况。

任何帮助或建议将不胜感激。

标签： listrecursionprologappend

解决方案

你很近！如果你想采用这种方法，主要缺少的是以下观察：如果isChild两者都接受“当前血统”并且预计会产生“新血统”，那么它需要两个血统参数。一种用于“旧”状态，一种用于“新”状态。

像这样：

isChild(X,Y, Lineage, NewLineage) :-
    parent(X,Z),
    append(Lineage, [Z], Lineage2),
    isChild(Z,Y, Lineage2, NewLineage).
isChild(X,Y, Lineage, NewLineage) :-
    parent(X,Y),
    append(Lineage, [Y], NewLineage).

当您调用它时，您需要传入正确的初始血统以开始：

relatives(X, Y, Lineage) :-
    isChild(X,Y, [X], Lineage).

这现在的行为就像你想要的那样：

?- relatives(grandma, daughter, Lineage).
Lineage = [grandma, mom, daughter] ;
false.

?- relatives(mom, son, Lineage).
false.

然而，真正的答案是，在 Prolog 中进行此类搜索时，您通常不会将内容附加到列表中。相反，您预先添加数据。这更有效，也更短，更易读，中间状态更少：

ancestor_successor_lineage(Ancestor, Successor, [Ancestor, Successor]) :-
    parent(Ancestor, Successor).
ancestor_successor_lineage(Ancestor, Successor, [Ancestor | Lineage]) :-
    parent(Ancestor, Intermediate),
    ancestor_successor_lineage(Intermediate, Successor, Lineage).

请注意，这与您对血统不感兴趣时​​所写的内容基本相同。添加中间状态的记录只是添加一个（而不是两个，像以前一样！）额外参数并使用列表构造函数[_ | _]将“单步”parent与递归步骤中的列表结合起来。这确实是在 Prolog 中编写它的首选方式。

这与其他解决方案的行为相同：

?- ancestor_successor_lineage(grandma, daughter, Lineage).
Lineage = [grandma, mom, daughter] ;
false.

?- ancestor_successor_lineage(mom, son, Lineage).
false.

推荐阅读