5

当th 斐波那契数为时，该术语fib(N,F)为真。FN

以下 Prolog 代码通常对我有用：

:-use_module(library(clpfd)).
fib(0,0).
fib(1,1).
fib(N,F) :- 
  N #> 1, 
  N #=< F + 1, 
  F #>= N - 1,
  F #> 0, 
  N1 #= N - 1, 
  N2 #= N - 2, 
  F1 #=< F, 
  F2 #=< F,
  F #= F1 + F2, 
  fib(N1,F1),
  fib(N2,F2).

执行此查询时（在 SICStus Prolog 中），找到 N 的第一个（也是正确的）匹配项（相当立即）：

| ?- fib(X,377).
X = 14 ?

当继续（通过输入“;”）查看是否有任何进一步的匹配（根据定义这是不可能的）时，总是需要大量的时间（与第一个匹配相比）才能始终回复“否”：

| ?- fib(X,377).
X = 14 ? ;
no

作为 Prolog 的新手，我尝试以!各种方式使用 Cut-Operator ( )，但我找不到阻止第一次匹配后搜索的方法。考虑到上述规则，它甚至可能吗？如果是，请告诉我如何:)

4

3 回答 3

7

有两个部分可以得到你想要的。

第一个是使用 call_semidet/1 它确保只有一个答案。也可以查看 SICStus 实现的链接。万一有多个答案，call_semidet/1会产生一个安全错误。请注意， once/1仅此而已，!/0就可以简单地删除所有存在的东西。

但是，你不会很高兴call_semidet/1独自一人。它基本上执行了两次目标。一次看是否只有一个答案，然后才能再次获得第一个答案。所以你会在很久以后得到你的答案。

另一部分是加快你的定义，这样上面就不会对你造成太大的干扰。CapelliC 建议的解决方案完全改变了特定于您的具体功能但不扩展到任何其他功能的算法。但它也描述了一种不同的关系。

本质上，你已经找到了典型的部分，你只需要稍微不同地组装它们就可以使它们工作。但是，让我们从基础开始。

CLPFD 作为 CLP(Z)

对于许多 Prolog 程序员来说，你在这里所做的仍然不是那么常见。您将有限域约束用于一般整数算术。也就是说，您使用 CLPFD 作为在 等中找到的调制表达式求值的纯粹替代(is)/2品(>)/2。所以你想扩展有限域范式，它假设我们在有限的给定区间内表达一切。事实上，将这个扩展称为 CLP(Z) 会更合适。

此扩展不适用于每个提供有限域的 Prolog。事实上，只有 SICStus、SWI 和 YAP 能够正确处理无限区间的情况。其他系统在应该成功或失败时可能会失败或成功 - 主要是在整数变得太大时。

了解不终止

第一个问题是了解您的原始程序没有终止的实际原因。为此，我将使用失败切片。也就是说，我将false目标添加到您的程序中。关键是：如果结果程序没有终止，那么原始程序也不会终止。因此，您的（假定的）原始程序的最小失败部分是：

fiborig(0,0) :-假的。
fiborig(1,1) :-假的。
fiborig(N,F) :-
   N#> 1,
   N1 #= N-1,
   N2 #= N-2,
   F #= F1+F2,
   fiborig（N1，F1），假，
    fiborig（N2，F2）。

这里有两个不终止的来源：一个是对于给定 的和F有无限多个值。这可以通过观察很容易处理。F1F2F1 #> 0, F2 #>= 0

另一个与Prolog的执行机制有关。为了说明这一点，我将添加F2 #= 0. 同样，因为生成的程序不会终止，所以原始程序也会循环。

fiborig(0,0) :-假的。
fiborig(1,1) :-假的。
fiborig(N,F) :-
   N#> 1,
   N1 #= N-1,
   N2 #= N-2,
   F #= F1+F2,
   F1 #> 0,
   F2 #>= 0,
   F2 #= 0, 
   fiborig(N1,F1), false ,
    fiborig(N2,F2)。

所以实际的问题是，可能0作为结果的目标执行得太晚了。只需交换两个递归目标。并添加冗余约束F2 #=< F1以提高效率。

纤细（0,0）。
纤维蛋白（1,1）。
纤维蛋白（N，F）：-
   N#> 1,
   N1 #= N-1,
   N2 #= N-2,
   F1 #> 0,
   F2 #>= 0,
   F1 #>= F2 ,
   F #= F1+F2,
   纤维蛋白（N2，F2），
   纤维蛋白（N1，F1）。

在我蹩脚的笔记本电脑上，我得到了以下运行时fib(N, 377)：

               SICStus SWI
             答案/总数
fiborig: 0.090s/27.220s 1.332s/1071.380s
fibmin: 0.080s/ 0.110s 1.201s/ 1.506s

取两者的总和以获得call_semidet/1.

请注意，SWI 的实现仅用 Prolog 编写，而 SICStus 部分用 C 语言编写，部分用 Prolog 编写。因此，当将 SWI（实际上是 @mat 的）clpfd 移植到 SICStus 时，它的速度可能相当。

还有很多东西需要优化。想想索引和“计数器”的处理，N, N1, N2。

您的原始程序也可以改进很多。例如，您不必要地发布了F #>= N-13 次约束！

于 2014-01-21T18:03:22.230 回答
4

如果您只对第一个解决方案感兴趣或知道最多有一个解决方案，您可以使用once/1来提交该解决方案：

?- once(fib(X, 377)).

+1 用于使用 CLP(FD) 作为低级算术的声明性替代方案。您的版本可以在所有方向使用，而基于原始整数算术的版本不能。

于 2014-01-19T13:19:38.680 回答
3

我对另一个定义进行了一些尝试，我用标准算术编写并为这个问题故意翻译成 CLP(FD)。

我简单的 Prolog 定义是

fibo(1, 1,0).
fibo(2, 2,1).
fibo(N, F,A) :- N > 2, M is N -1, fibo(M, A,B), F is A+B.

翻译后，由于在反向模式下花费太长时间（或不终止，不知道），我尝试添加更多约束（并移动它们）以查看“向后”计算终止的位置：

fibo(1, 1,0).
fibo(2, 2,1).
fibo(N, F,A) :-
  N #> 2,
  M #= N -1,
  M #>= 0,  % added
  A #>= 0,  % added
  B #< A,   % added - this is key
  F #= A+B,
  fibo(M, A,B). % moved - this is key

在最后一次调用中添加B #< A和移动递归之后，现在它可以工作了。

?- time(fibo(U,377,Y)).
% 77,005 inferences, 0.032 CPU in 0.033 seconds (99% CPU, 2371149 Lips)
U = 13,
Y = 233 ;
% 37,389 inferences, 0.023 CPU in 0.023 seconds (100% CPU, 1651757 Lips)
false.

编辑要考虑基于 0 的序列，请添加一个事实

fibo(0,0,_).

也许这解释了最后一个论点的作用：它是一个累加器。

于 2014-01-19T17:12:56.383 回答