7

我正在阅读Learn Prolog Now！的关于削减的章节以及 Bratko 的人工智能 Prolog 编程，第 5 章：控制回溯。起初，cut 似乎是模仿其他编程语言中已知的 if-else 子句的直接方式，例如

# Find the largest number
max(X,Y,Y):- X =< Y,!. 
max(X,Y,X).

然而，正如下面所述，如果所有变量都被实例化，即使我们期望，该代码也会失败false，例如

?- max(2,3,2).
true.

原因很清楚：第一个规则失败，第二个规则不再有任何条件与之相关，所以它会成功。我明白这一点，但随后提出了一个解决方案（这里是嗖嗖声）：

max(X,Y,Z):- X =< Y,!, Y = Z. 
max(X,Y,X).

我很困惑我应该如何阅读这个。我!的意思是：'如果在此之前的所有内容!都是真实的，请停止终止，包括具有相同谓词的任何其他规则'。但是，这不可能是正确的，因为这意味着实例化Y = Z仅在失败的情况下发生，这对于该规则是无用的。

那么应该如何以“人类”的方式阅读剪辑呢？而且，作为扩展，我应该如何阅读上述建议的解决方案max/3？

4

2 回答 2

6

另请参阅此答案和此问题。

我应该如何阅读上面提出的 max/3 解决方案？

max(X,Y,Z):- X =< Y, !, Y = Z. 
max(X,Y,X).

您可以按如下方式阅读：

when X =< Y，忘记谓词的第二个从句，统一Yand Z。

削减丢弃选择点。选择点是证明树中的标记，它告诉 Prolog 在找到解决方案后在哪里继续搜索更多解决方案。因此，cut 切掉了证明树的一部分。上面的第一个链接（这里又是）详细讨论了削减，但该答案的很大一部分只是引用了其他人对其他地方削减的看法。

我想带回家的信息是，一旦您在 Prolog 程序中进行了剪辑，您就会强迫自己以操作方式而不是声明方式阅读它。为了了解证明树的哪些部分将被删除，您（程序员）必须经历这些动作，考虑子句的顺序，考虑哪些子目标可以创建选择点，考虑哪些解决方案会丢失。您需要构建证明树（而不是让 Prolog 来做）。

您可以使用许多技术来避免创建您知道不需要的选择点。然而，这是一个有点大的话题。您应该阅读可用材料并提出具体问题。

于 2016-12-02T15:05:35.910 回答
2

您的代码的问题是在评估您的查询时永远不会达到削减。

尝试使用规则评估目标的第一步是模式匹配。

目标max(2,3,2)与模式不匹配max(X,Y,Y)，因为模式中的第二个和第三个参数相同，并且 3 和 2 彼此不匹配。因此，该规则在模式匹配阶段已经失败，因此评估者没有达到 testing X =< Y，更不用说达到!.

但是你对削减的理解是非常正确的。鉴于此代码

a(X) :- b(X).
a(X) :- c(X).
b(X) :- d(X), !.
b(X) :- e(X).
c(3).
d(4).
d(5).
e(6).

和目标

?- a(X).

解释器将从第一条规则开始，尝试满足b(X). 在此过程中，它发现d(4)提供了一个解决方案，因此将值绑定4到X. 然后切入，丢弃 上的回溯b(X)，因此找不到进一步的解决方案b(X)。但是，它不会删除 上的回溯a(X)，因此如果您要求 Prolog 找到另一个解决方案，那么它将X = 3通过a(X) :- c(X).规则找到。如果您将第一条规则更改为a(X) :- b(X), !.then 它将无法找到X = 3.

虽然切割意味着没有X = 5找到解决方案，但如果您的查询是

?- a(5).

然后解释器将返回 true。这是因为a(5)calls b(5)，which callsd(5)被定义为 true。该d(4)事实使模式匹配失败，因此它不会像查询时那样触发剪切a(X)。

这是一个红色切割的例子（请参阅我对 user1812457 答案的评论）。除了破坏逻辑纯度之外，避免红色切割的一个很好的理由可能是避免这种行为导致的错误。

于 2020-12-19T20:54:18.573 回答