Prolog 中的回溯

在回溯过程中，我们将返回到之前的目标，之后，我们将尝试找到另一种方法来满足目标。在本节中，我们将给出两种详细的方法，使用回溯和统一的过程来满足一系列的目标。

例如

以下示例显示了一组人之间的家庭关系。在以下子句中，mother/2 谓词定义了 10 个事实，father/2 谓词定义了 9 个事实，而 parent/2 谓词定义了 6 个子句。

事实如下

上述事实分别表示“杰西卡是克里斯的母亲”和“乔什是克里斯的父亲”。在上面的例子中，我们添加了 [M1] 标签仅供参考。这些标签不是子句的一部分。

下图显示了以下示例的事实。在这里，f 代表父亲。

示例

给定查询

?- parent(josh, Child), write('孩子是 '), write(Child), nl.

在此查询中，Prolog 试图满足所有的一系列目标。首先，对于变量 Child，Prolog 找到一个或多个可能的值。它从第一个目标 parent(josh, Child) 开始。 Prolog 尝试将第一个目标与每个子句的头部进行统一，依次定义谓词 parent/2。 为了实现这一点，Prolog 从上到下工作。 子句 [P1] 和 [P2] 首先搜索，但 Prolog 无法将目标与其中任何一个匹配。 现在，Prolog 搜索子句 [P3]，这次 Prolog 成功地将目标与子句的头部统一，其中 A 绑定到 josh，变量 B 绑定到变量 Child。

在规则 [P3] 的主体中，Prolog 遍历目标并尝试依次成功目标。 目标 write('mother?') 和 nl 由 Prolog 成功评估，然后生成以下文本行作为输出

mother?

现在 Prolog 来到第三个目标，即 mother(josh, B)。 但是，此第三个目标未与定义谓词 mother/2 的任何子句 [M1] 到 [M10] 的头部统一。 因此，第三个目标失败。

现在 Prolog 系统回溯。在子句 [P3] 的主体中，Prolog 回到最近满足的目标。它从右向左工作。最近满足的目标是 nl，我们将尝试满足它。

n1/0 内置谓词是不可满足的，这意味着当我们回溯时评估它时，它总是失败。

现在在 [P3] 的主体中，Prolog 向左移动并找到目标 write('mother?')。 但是，此目标始终失败，因为 write/1 谓词也无法满足。

在规则 [P3] 的主体中，没有可用的目标，从左到右工作。 因此，规则 [P3] 被 Prolog 系统拒绝。 现在我们有以下内容

在这种情况下，最近评估的目标是 parent(josh, Child)，我们将尝试满足此目标。

现在 Prolog 回到最近评估的先前目标，即 parent(josh, Child)，然后我们尝试满足此目标。 为了找到定义谓词 parent/2 的子句，Prolog 从先前到达的点（即 [P3] 子句）搜索数据库。 首先，它检查 [P4] 子句，并成功地将目标与其头部统一。 变量 X 绑定到 josh，变量 Y 绑定到变量 Child。

在规则 [P4] 的主体中，Prolog 遍历目标并尝试依次成功目标。规则 [P4] 的前两个目标由 Prolog 成功，并生成以下文本行作为输出

father?

现在 Prolog 尝试满足第三个目标，即 father(josh, Y)。 Prolog 搜索子句并找到依次定义 father/2 谓词的子句。 搜索从上到下进行。

系统找到第一个子句 [F2]，这是一个事实。 现在，变量 Y 绑定到 haley。 变量 Y 绑定到变量 Child，因此，变量 Child 也绑定到原子 haley。

在规则 [P4] 的主体中，还有两个目标，即 write('father!') 和 nl。 它们都成功并生成以下文本行作为输出

father!

现在在规则 [P4] 的主体中，所有目标都已成功，因此子句的头部，即 parent(josh, haley) 成功。 因此，在用户的查询中，目标 parent(josh, Child) 成功。

在序列中，第一个目标已满足，该目标由用户输入。 在序列中，还有三个目标，即 write('孩子是 ')、write(Child) 和 nl。 它们都成功并生成以下文本行作为输出

The child is haley

在用户的查询中，所有目标都已成功满足。 Prolog 系统输出用于查询的所有变量的值。

?- parent(josh, Child), write('The child is '), write(Child), nl.
mother?
father?
father!
The child is haley
Child = haley