Prolog - 递归家谱

Question

我正在尝试编写一个Prolog程序,该程序将依次打印出英国版税的男性继承人.我到目前为止的尝试:

son(elizabeth, charles).
son(charles, william).
son(charles, henry).
son(elizabeth, andrew).
son(elizabeth, edward).
son(edward, severn).
successor(X, Y) :- son(X, Y).
successor(X, Y) :- son(X, C), successor(C, Y).

后继功能并不能完全符合我的要求:当前输出为:

successor(elizabeth, Y).
Y = charles ;
Y = andrew ;
Y = edward ;
Y = william ;
Y = henry ;
Y = severn ;
false.

第一个规则使所有三个直接子节点打印出来,然后第二个规则打印出所有后代.但是第一个孩子的后代应该来到第二个直系孩子面前,如下:

successor(elizabeth, Y).
Y = charles ;
Y = william ; % william and henry should come before andrew
Y = henry ;
Y = andrew ;
Y = edward ;
Y = severn ;
false.

这是我的第一个Prolog计划,我对如何表达正确的关系感到茫然.任何人都可以给我一个想法或指向对我有帮助的资源吗？

Answer 1

正如rati所述,Prolog查询通过选择规则,使用深度优先搜索递归评估,然后选择下一个规则并重复该过程来解决.但是,您开始使用的特定规则实际上会导致对系列树进行广度优先搜索,正如您所指出的那样,它不会提供与实际连续行匹配的输出.相反,你想要对王室树进行深度优先遍历.此版本提供您正在寻找的结果:

successor(X, Y) :- son(X, Z), (Y = Z; successor(Z, Y)).

使用此规则,Prolog successor(X, Y)大致如下解析查询:

• 对于每个Z谁是儿子X:
  • 绑定Y到Z,让Z作为解决方案.
  • 该;运营商充当逻辑OR,所以现在Y是松散的和successor/2被称为递归以获得谁是儿子的接班人Z.

是的,请尝试获取Prolog艺术的副本.这不是最容易阅读的编程书籍,但我发现它对我(正在)理解逻辑编程的尝试非常有帮助.似乎有一些廉价精装本的1994年版本在eBay附近漂浮.