Prolog - 向下递归家庭树 [英] Prolog - recursing down family tree

问题描述

我正在尝试编写一个 Prolog 程序，该程序将按顺序打印出英国皇室的男性继任者.我到目前为止的尝试:

I am trying to write a Prolog program that will print out the male successors of British Royalty in order. My attempt so far:

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

后继函数不是我想要的:当前输出是这样的:

The successor function doesn't quite do what I want: the current output is this:

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

第一条规则打印出所有三个直接的孩子，然后第二条规则打印出所有的后代.但是第一个孩子的后代应该在第二个直接孩子之前，就像这样:

The first rule makes all three immediate children print out, then the second rule prints out all the descendants. But the descendants of the first child should come before the second immediate child, like this:

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

这是我的第一个 Prolog 程序，我不知道如何表达正确的关系.任何人都可以给我一个想法或指向对我有帮助的资源的指针吗?

This is my first Prolog program, and I am at a loss for how to express the right relationship. Can anyone give me an idea or pointers to resources that would be helpful to me?

推荐答案

如上所述，Prolog 查询通过选择规则来解决，使用 深度优先搜索，然后选择下一个规则并重复该过程.但是，您开始使用的特定规则实际上会导致广度优先搜索家谱的，正如您所指出的，它没有给出与实际继承线相匹配的输出.相反，您想要对王室树进行深度优先遍历.此版本提供了您正在寻找的结果:

As rati noted above, Prolog queries are resolved by choosing a rule, recursively evaluating it using depth-first search, then choosing the next rule and repeating the process. However, the particular rules you're starting with actually result in a breadth-first search of the family tree, which, as you noted, does not give output that matches the actual line of succession. Instead, you want to do a depth-first traversal of the royal family tree. This version gives the result you're looking for:

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

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

Using this rule, Prolog resolves the query successor(X, Y) roughly as follows:

• 对于每个 X 的儿子 Z:
  • 将 Y 绑定到 Z，给出 Z 作为解决方案.
  • ; 运算符用作逻辑 OR，所以现在 Y 是未绑定的，并且 successor/2 被递归调用以获取后继者是 Z 的儿子.
  • For each Z who is a son of X:
    • Bind Y to Z, giving Z as a solution.
    • The ; operator functions as a logical OR, so now Y is unbound and successor/2 is called recursively to get the successors who are sons of Z.

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

    And yes, please do try to get a copy of the Art of Prolog. It's not the easiest programming book to read, but I found it extremely helpful in my (ongoing) attempt to understand logic programming. There seem to have been some cheap hardcover copies of the 1994 edition floating around eBay lately.

    这篇关于Prolog - 向下递归家庭树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！