0

我在 Prolog 中实现了以下电源程序：

puissance(_,0,1).
puissance(X,N,P) :- N>0,A is N-1, puissance(X,A,Z), P is Z*X.

代码做了应该做的事情，但是在正确答案之后它会打印“假”。我不明白为什么。我正在使用 swi-prolog。

4

3 回答 3

3

可以这样做：

puissance(X,N,P) :-
  ( N > 0 ->
    A is N-1,
    puissance(X,A,Z),
    P is Z*X
  ; P = 1 ).

然后它只会打印一个答案。

（您的代码在每次递归调用时都会留下一个“选择点”，因为您有两个析取项且没有剪切。在某处使用 if-then-else 或剪切会删除这些。然后取决于解释器会发生什么。Sicstus 仍然会询问您是否想要（（试图找到））更多答案。）

于 2017-02-07T06:05:22.513 回答
2

语义差异

目前，有 3 个不同的版本puissance/3，我想展示其中一些之间的显着语义差异。

作为测试用例，我考虑以下查询：

?- puissance(X, Y, Z),假的。

这个查询是什么意思？声明式地，它显然等同于 false。尽管如此，这个查询还是很有趣的，因为它终止了iff puissance/3 普遍终止。

现在，让我们尝试对程序的不同变体进行查询：

  1. 原始定义（来自问题）：

    ?- puissance(X, Y, Z), false.
ERROR: puissance/3: Arguments are not sufficiently instantiated

  2. 接受的答案：

    ?- puissance(X, Y, Z), false.
false.

  3. 其他答案：

    ?- puissance(X, Y, Z), false.
ERROR: puissance/3: Arguments are not sufficiently instantiated

显然，接受的答案中显示的解决方案会产生不同的结果，值得进一步考虑。

这是程序：

puissance(_,0,1) :- !.
puissance(X,N,P) :- N>0,A 是 N-1, puissance(X,A,Z), P 是 Z*X。

让我们先问一个简单的问题：到底有哪些解决方案？这被称为最一般的查询，因为它的参数都是新鲜的变量：

?- puissance（X，Y，Z）。
Y = 0,
Z = 1。

程序回答：只有一个解决方案：Y=0, Z=1.

这是不正确的（要看到这一点，请尝试成功?- puissance(0, 1, _)的查询，与声称只能是的同一程序相反），并且与问题中显示的程序有显着差异。为了比较，原始程序产生：Y0

?- puissance（X，Y，Z）。
Y = 0,
Z = 1 ;
错误：puissance/3：参数没有充分实例化

没关系：在回溯时，程序会抛出一个实例化错误，表明此时无法进行进一步的推理。但至关重要的是，它不会简单地失败！

提高确定性

所以，让我们坚持原来的程序，并考虑查询：

?- puissance(1, 1, Z)。
Z = 1 ;
错误的。

我们想摆脱false这种情况，因为程序不是确定性的。

解决此问题的一种方法是使用zcompare/3from library(clpfd)。这使您可以具体化比较，并使结果可用于索引，同时保留谓词的一般性。

这是一种可能的解决方案：

puissance(X, N, P) :-
        zcompare(C, 0, N),
        puissance_(C, X, N, P)。

puissance_(=, _, 0, 1)。
puissance_(<, X, N, P) :-
        一个#= N-1，
        puissance(X, A, Z),
        P #= Z*X。

使用这个版本，我们得到：

?- puissance(1, 1, Z)。
Z = 1。

正如预期的那样，这现在是确定性的。

现在，让我们从上面考虑这个版本的测试用例：

?- puissance(X, Y, Z),假的。
不终止

啊哈！所以这个查询既不会引发实例化错误也不会终止，因此与迄今为止发布的所有版本都不同。

让我们考虑这个程序最一般的查询：

?- puissance（X，Y，Z）。
Y = 0,
Z = 1 ;
X = Z，
Y = 1,
Z inf..sup ;
Y = 2,
X^2#=Z,
Z in 0..sup ;
Y = 3，
_G3136*X#=Z,
X^2#=_G3136,
_G3136 在 0..sup ;
等等

啊哈！所以我们得到了满足这个关系的所有整数的符号表示。

这很酷，因此我建议您在 Prolog 中对整数进行推理时使用 CLP(FD) 约束。这将使您的程序更通用，也可以让您更轻松地提高其效率。

于 2017-02-11T09:27:50.200 回答
0

您可以在解决方案中添加一个剪切运算符（即!），这意味着在第一次成功统一达到该点之后，prolog 不应尝试回溯并找到更多解决方案。（即您正在修剪解决方案树）。

puissance(_,0,1) :- !.
puissance(X,N,P) :- N>0,A is N-1, puissance(X,A,Z), P is Z*X.

外行的解释：

prolog 尝试查看是否有更多解决方案的原因是：

puissance在递归的最后一次调用中，第一个 puissance子句自 P=1 以来成功，并且您一直返回到顶部调用以执行与 P 的统一，并使用该选择产生的最终值。

但是，对于最后一次调用puissance，Prolog 没有机会检查第二个 puissance子句是否也可以满足并可能导致不同的解决方案，因此除非您告诉它不要检查进一步的解决方案（通过使用 cut on成功后的第一个子句），它有义务回到那个点，并检查第二个子句。

一旦这样做，它就会发现第二个子句不能满足，因为 N = 0，因此该特定尝试失败。

所以“假”实际上意味着序言也检查了其他选择点，并且无法以任何其他方式统一 P 以满足它们，即 P 没有更多有效的统一。

事实上，您首先可以选择寻找其他解决方案，这恰恰意味着还有其他路线，其中可能存在尚未探索的可满足子句。

于 2017-02-07T13:00:42.863 回答