如何用cut来解释这个Prolog目标，提高效率 [英] How to interpret this Prolog goal with a cut, and improve efficiency

问题描述

我一直在阅读

我阅读了树和代码如下:

在目标列表中 C :- P, Q, R, !, S, T, U. Prolog 会一一尝试实例化这些变量，像往常一样，最终达到 <代码>真..假设为 P 和 Q 找到一个值，并且第一次尝试 R 失败，那么 Prolog 可以回溯到以下情况P 和 Q 已找到，如果可用，请尝试 R 的另一个选项.然而，如果 R 也被找到(导致 P, Q, R = true.)，并且 ! 像往常一样成功，我们扔掉了任何选择点，从那一点开始就没有什么可追溯的了(甚至C :- V.).这意味着如果找不到 S 的结果，目标 C :- P, Q, R, !, S, T, U. 将立即失败.但是 Prolog 仍然可以回溯到 A :- B, C, D. 以找到 B 的其他值.如果为 B 找到另一个匹配项，将重新尝试 C.等等.

假设我的解释是正确的，如果目标 C :- P, Q, R, !, S, T, U. 成功或失败，无论 B<的值如何/code>，你会如何提高效率?我的猜测是将 A :- B, C, D. 重写为 A :- B, !, C, D.

我的解释正确吗?考虑到有关 C 的一些先验信息，我在效率方面的改进呢?

解决方案

是的，你的理解是正确的.为了更好地理解它，我们可以将谓词重写为

a = (b & c & d)c = (p & q & r) ~~>！(s & t & u) ;v

使用 & 表示 &&:，以及其他运算符，来自 这个答案(或者如果不清楚，请将其视为伪代码，~~>！ 不通过通过不止一种解决方案).当到达切割点时，c 被提交，但 a 仍然是可回溯的.

如果A :- B, C, D.中的C成功或失败，无论B的值如何，您也可以重新排序目标为

A :- C, B, D.

A :- B, !, C, D. 中的切割是一个红色切割，它只让 B 成功一次，但是如果你对它的第二个结果感兴趣呢?红色切割改变谓词的含义.

I have been reading through the answers and comments of my previous question and I have tried applying the given explanations on an example from Bratko (Prolog Programming for Artificial Intelligence, p. 130), but I am not sure I understand it completely. The example is described below:

I read the tree and the code as follows:

In the goal list C :- P, Q, R, !, S, T, U. Prolog will one by one try to instantiate the variables, as normal, to eventually get to true.. Let's say that a value is found for P and Q, and the first try on R fails, then Prolog can back track to the case where P and Q were found, and try another option for R if available. However, if R is found as well (leading to P, Q, R = true.), and ! succeeds as it always does, we throw away any choice points and there's nothing to back track to from that point on (not even C :- V.). What this means is that if no results can be found for S, the goal C :- P, Q, R, !, S, T, U. will fail immediately. But Prolog can still backtrack to A :- B, C, D. to find other values for B. If another match is found for B, C will be tried again anew. And so on.

Assuming that my interpretation is correct, if the goal C :- P, Q, R, !, S, T, U. succeeds or fails regardless of the value of B, how would you improve efficiency? My guess would be to re-write A :- B, C, D. as A :- B, !, C, D.

Is my interpretation correct? And what about my improvement in efficiency, given some a-priori information on C?

解决方案

Yes, your understanding is correct. To see it better, we can re-write the predicates as

a = (b & c & d)
c = (p & q & r) ~~>! (s & t & u) ; v

with & for &&:, and the rest of operators, from this answer (or if it isn't clear, see this as a pseudocode, with ~~>! passing no more than one solution through). When the cut is reached, c is committed, but a is still backtrackable.

If C in A :- B, C, D. succeeds or fails regardless of the value of B, you can also reorder the goals as

A :- C, B, D.

The cut in A :- B, !, C, D. is a red cut, it only lets B succeed once, but what if you're interested in its second result? Red cuts alter the meaning of a predicate.

这篇关于如何用cut来解释这个Prolog目标，提高效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！