时间戳

首页 > 解决方案 > Prolog 中的回溯

prolog - Prolog 中的回溯

问题描述

我对 Prolog 很陌生，并且对回溯有疑问

我得到了事实

p(X, Y):- q(X, Y).
p(X, Y):- r(X, Y).

q(X, Y):- s(X), t(Y).
r(X, Y):- u(X, Y).

我得到了数据库

s(f(a)).
t(g(b)).
u(a, g(b)).

和目标

?- p(a, g(Y)).

我知道这个查询有一个解决方案

Y = b

但是，我不确定 Prolog 回溯了多少次。我相信答案是 3 次，因为 Prolog 从上到下工作并检查每个事实，以确保不能将以前的事实组合起来用于解决目标。任何帮助，将不胜感激。

最后一个 Q，具有嵌套事实的事实，IE

s(f(a))

其中 f 未定义，我可以假设这在语法上等于 s(a) 吗？

标签： prologlogicbacktracking

解决方案

但是，我不确定 Prolog 回溯了多少次。

不是一个很好的问题。从哪里回溯到哪里？

考虑 Prolog 构建一个搜索树（或“证明树”），这样：

  • 为每个谓词调用创建一个 OR 节点，其中子节点是谓词的可能子句之一。
  • 为每个子句创建一个 AND 节点，其中子节点是该子句所需的谓词调用之一。

如果证明具有以下形式，则可以找到有效证明：

  • 从根“目标”递归下树：
    • 每个 AND 节点的所有子节点都标记为“已证明”/“真”
    • 每个 OR 节点都有一个标记为“已验证”/“真实”的子节点
    • 叶节点是公理，定义为“证明”/“真实”：它们是事实。

当 Prolog 发现证明停止的情况时，就会发生“回溯”：

  • OR 节点的所有子节点都不能被证明。然后“回溯”到树的一层，可能到 AND 节点（将发生更多回溯）。
  • AND 节点的其中一个子节点无法被证明。然后“回溯”到无法证明的孩子的前一个兄弟姐妹，要求“重做”。如果没有先前的兄弟，则回溯到树的一层，可能到一个 OR 节点（它必须尝试它的另一个子节点）。

Prolog 程序作为搜索树执行的一个补充视图是“Byrd Box 模型”。如果收集了一些笔记。它们并不完美，但它们在这里：关于“Byrd Box 模型”。看一看。

无论如何，回到那个程序。

通过调试器运行它是有益的，但作为替代解决方案，我们可以添加一些打印语句：

p(X, Y) :-
   format("p(~q,~q) clause #1\n",[X,Y]),
   q(X, Y),
   format("In p/2, success with q(~q,~q)\n",[X,Y]).

p(X, Y) :-
   format("p(~q,~q) clause #2\n",[X,Y]),
   r(X, Y),
   format("In p/2, success with r(~q,~q)\n",[X,Y]).

q(X, Y) :-
   format("q(~q,~q)\n",[X,Y]),
   s(X),
   format("In q/2, success with s(~q)\n",[X]),
   t(Y),
   format("In q/2, success with t(~q)\n",[Y]).

r(X, Y) :-
   format("r(~q,~q)\n",[X,Y]),
   u(X, Y),
   format("In r/2, success with r(~q,~q)\n",[X,Y]).

s(f(a))     :- format("Fact s(f(a))\n").
t(g(b))     :- format("Fact t(g(b))\n").
u(a, g(b))  :- format("Fact u(a,g(b))\n").

运行它会带来：

?- p(a,g(Y)).

p(a,g(_1054)) clause #1
q(a,g(_1054))
p(a,g(_1054)) clause #2
r(a,g(_1054))
Fact u(a,g(b))
In r/2, success with r(a,g(b))
In p/2, success with r(a,g(b))

Y = b.

我们可以推导出搜索：

  • 从 p/2 开始
  • 转至q/2
  • 这里我们失败了，没有 s(X)，所以我们回溯到 p/2 并尝试另一个子句（OR 节点的下一个子节点）
  • 再次在 p/2
  • 转到 r/2
  • 我们正在触及树的底部：事实！
  • 剩下的就是执行执行打印输出的 AND 节点的子节点。

不知道这样是否能让事情更清楚？

最后一个 Q，具有嵌套事实的事实，IE

s(f(a))

其中 f 未定义，我可以假设这在语法上等于 s(a) 吗？

绝对不。s(f(a))是一种句法结构。其中没有任何内容需要“定义”，也没有任何内容将被评估。它不同于s(a)另一种句法结构。这可以在 Prolog 顶层看到：

?- s(f(a)) == s(a).
false.

推荐阅读