如何表达“祖先"?递归地 [英] How to express "ancestor" recursively
问题描述
我坚持使用这个递归，它不像我预期的那样工作.
I'm stuck with this recursion which doesn't work as I expect.
我的错误在哪里?
#!/usr/bin/prolog
% Facts
mother( jeanne , michel ). % great-grandmother, grandfather
mother( genevieve, aubin ). % grandmother, father
mother( irene , alain ). % great-grandmother, grandfather
mother( emilie , colette ). % great-grandmother, grandmother
mother( colette , muriel ). % grandmother, mother
mother( muriel , eve ). % mother, daughter
father( joseph , michel ). % great-grandfather, grandfather
father( michel , aubin ). % grandfather, father
father( xxx , alain ). % great-grandfather, grandfather
father( marcel , colette ). % great-grandfather, grandmother
father( alain , muriel ). % grandfather, mother
father( aubin , eve ). % father, daughter
% Rules
parent( Mother, Child ) :- mother( Mother, Child ).
parent( Father, Child ) :- father( Father, Child ).
ancestors( [Parent|Ancestors], Child ) :-
parent( Parent, Child ),
ancestors( Ancestors, Parent ).
% Queries
:-
ancestors( Ancestor, eve ),
format( 'Eve ancestors: ~w~n', Ancestor ).
% expected answer is [muriel, colette, alain, emilie, marcel, irene, xxx, aubin, michel, genevieve, joseph, jeanne]
编辑这是最终的解决方案，谢谢大家.
EDIT here is the final solution, thank you all.
#!/usr/bin/prolog
/*##- Facts -##*/
mother( jeanne , michel ).
mother( genevieve, sylvie ).
mother( genevieve, brigitte ).
mother( genevieve, aubin ).
mother( irène , alain ).
mother( émilie , colette ).
mother( colette , muriel ).
mother( colette , olivier ).
mother( colette , audrey ).
mother( colette , stéphane ).
mother( muriel , eve ).
father( joseph , michel ).
father( michel , sylvie ).
father( michel , brigitte ).
father( michel , aubin ).
father( séraphin, alain ).
father( marcel , colette ).
father( alain , muriel ).
father( alain , olivier ).
father( yves , audrey ).
father( yves , stéphane ).
father( aubin , eve ).
/*##- Rules -##*/
parent( Mother, Child ) :- mother( Mother, Child ).
parent( Father, Child ) :- father( Father, Child ).
ancestor( Parent, Child ) :- parent( Parent, Child ).
ancestor( GrandParent, Child ) :-
parent( GrandParent, Parent ),
ancestor( Parent, Child ).
grandMothers( GrandMother, Child ) :-
mother( GrandMother, FatherOrMother ),
parent( FatherOrMother, Child ).
grandsFathers( GrandsFather, Child ) :-
father( GrandsFather, FatherOrMother ),
parent( FatherOrMother, Child ).
parents( Mother, Father, Child ) :-
father( Father, Child ),
mother( Mother, Child ).
strictSiblings( SisterOrBrother, Child ) :-
parents( Mother, Father, Child ),
parents( Mother, Father, SisterOrBrother ),
SisterOrBrother \= Child.
siblings( SisterOrBrother, Child ) :-
mother( Mother, Child ), mother( Mother, SisterOrBrother ), SisterOrBrother \= Child ;
father( Father, Child ), father( Father, SisterOrBrother ), SisterOrBrother \= Child .
/*##- Queries -##*/
theMother :-
mother( Mother, eve ),
format( 'Ève\'s mother: ~w~n', [Mother] ).
theFather :-
father( Father, eve ),
format( 'Ève\'s father: ~w~n', [Father] ).
theParents :-
setof( MotherOrFather, parent( MotherOrFather, eve ), MotherAndFather ),
format( 'Ève\'s parents: ~w~n', [MotherAndFather] ).
theGrandMothers :-
setof( GrandMother, grandMothers( GrandMother , eve ), GrandMothers ),
format( 'Ève\'s grand-mothers: ~w~n', [GrandMothers] ).
theGrandFathers :-
setof( GrandsFather, grandsFathers( GrandsFather , eve ), GrandsPères ),
format( 'Ève\'s grand-fathers: ~w~n', [GrandsPères] ).
lesEnfants :-
setof( Child, parents( genevieve, michel, Child ), Children ),
format( 'Geneviève and Michel children: ~w~n', [Children] ).
theTwoParents :-
parents( Mother, Father, eve ),
format( 'Ève\'s mother and father: ~w, ~w~n', [Mother, Father] ).
theStrictSiblings :-
setof( SisterOrBrother, strictSiblings( SisterOrBrother, muriel ), SistersAndBrothers ),
format( 'Muriel\'s strict siblings: ~w~n', [SistersAndBrothers] ).
theSiblings :-
setof( SisterOrBrother, siblings( SisterOrBrother, muriel ), SistersAndBrothers ),
format( 'Muriel\'s siblings: ~w~n', [SistersAndBrothers] ).
theAncestors :-
setof( Ancestor, ancestor( Ancestor, eve ), Ancestors ),
format( 'Ève\'s ancestors: ~w~n', [Ancestors] ).
:-
theMother,
theFather,
theParents,
theGrandMothers,
theGrandFathers,
lesEnfants,
theTwoParents,
theStrictSiblings,
theSiblings,
theAncestors,
halt( 0 ).
输出为:
Ève's mother: muriel
Ève's father: aubin
Ève's parents: [aubin,muriel]
Ève's grand-mothers: [colette,genevieve]
Ève's grand-fathers: [alain,michel]
Geneviève and Michel children: [aubin,brigitte,sylvie]
Ève's mother and father: muriel, aubin
Muriel's strict siblings: [olivier]
Muriel's siblings: [audrey,olivier,stéphane]
Ève's ancestors: [alain,aubin,colette,genevieve,irène,jeanne,joseph,marcel,michel,muriel,séraphin,émilie]
推荐答案
让我们以交互方式(在 SWI Prolog 中)而不是使用 format/2 在最后打印答案的脚本中执行此操作.
Let's do this interactively (in SWI Prolog) instead of in a script which prints the answers at the end using format/2.
我们希望 eve 的所有可能祖先都在一个列表中.
We want all possible ancestors of eve in a list.
所以我们必须
- 查询 Prolog 程序以获得目标的所有可能解
ancestor(A,eve) - 然后将它们收集到一个列表中
这是使用谓词 bagof/3、setof/3 或 findall/3 之一完成的，它们回溯到一个目标并使用包含所有答案的列表统一变量(bagof/3 的重复答案，setof 的 重复答案/3，并且没有可能的答案"产生 [] 而不是 findall/3 的失败.
This is done using one of the predicates bagof/3, setof/3 or findall/3, which backtrack over answers to a goal and unify a variable with a list containing all the answers (with duplicate answers for bagof/3, without duplicate answers for setof/3, and with "no possible answer" yielding [] instead of failure for findall/3).
所以我们只需要确保找到任何祖先的目标是正确的.
So we just need to make sure the goal to find any ancestor is correct.
如果
A是C或 的父级A是一些D的父级，D是C 的祖先
Ais a parent ofCorAis a parent of someD, andDis an ancestor ofC
(注意:只是'if'，而不是'if an only if'.但是，假设没有其他方式，其中A可能是一个C 的祖先......一个合理的封闭世界假设")
(Note: just 'if', not 'if an only if'. However, it is assumed there are no other ways in which A could possibly be an ancestor of C ... a reasonable "closed world assumption")
上述公式很好地适应了 Prolog 的搜索策略，它试图首先解决正文中最左边的子目标:
The above formulation is well adapted to the search strategy of Prolog, which attempts to resolve a leftmost sub-goal in the body first:
ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- parent(A,D),ancestor(D,C).
以检查左侧的祖先"的方式进行:
Doing it in the way "check for ancestor on the left":
ancestor(A,C) :- parent(A,C).
ancestor(A,C) :- ancestor(A,D),parent(D,C).
应该导致相同的结果但实际上不会:在最初给出好的答案后，Prolog Processor最终将进入无限循环，其中ancestor(A,C) 调用 ancestor(A,D).(这适用于更简单的Datalog"语言).
should lead to the same result but actually does not: After initially giving good answer, the Prolog Processor will eventually enter an infinite loop, where ancestor(A,C) calls ancestor(A,D). (This would work in the simpler "Datalog" language).
无论如何，我们完成了吗?
Anyway, are we done?
?- ancestor(X,eve).
X = muriel ;
X = aubin ;
X = jeanne ;
X = genevieve ;
X = irene ;
X = emilie ;
X = colette ;
X = joseph ;
X = michel ;
X = xxx ;
X = marcel ;
X = alain ;
false.
现在将所有内容收集到列表中:
Now collect everything into a list:
(在 SWI-Prolog 中，你必须说你想打印长列表，而不是用省略号代替，所以):
(In SWI-Prolog, you have to say that you want long lists printed, not replaced by ellipses, so):
?- set_prolog_flag(answer_write_options,[max_depth(0)]).
true.
然后:
?- bagof(X,ancestor(X,eve),Out).
Out = [muriel,aubin,jeanne,genevieve,irene,emilie,
colette,joseph,michel,xxx,marcel,alain].
这篇关于如何表达“祖先"?递归地的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
