在首次解决Fibonacci对之后防止回溯

Question

术语fib(N,F)当是真的F是N个Fibonacci数.

以下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(),但是在第一场比赛后我找不到阻止搜索的方法.根据上述规则,它是否可能？如果是的话,请告诉我如何:)

Answer 1

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

首先是使用 call_semidet/1 它确保只有一个答案.请参阅SICStus实现的链接.如果有多个答案,则call_semidet/1产生安全错误.请注意, once/1并且!/0只是简单地切掉了所有的东西.

但是,你一个人不会很开心call_semidet/1.它基本上执行两次目标.一旦看到是否有不止一个答案,只有再次获得第一个答案.所以你会在以后得到你的答案.

另一部分是加快你的定义,以便上面对你不会太令人不安.CapelliC建议的解决方案完全改变了算法,该算法特定于您的具体功能,但不会扩展到任何其他功能.但它也描述了一种不同的关系.

基本上,你已经找到了典型的部分,你只需要稍微组合它们就可以使它们工作.但是,让我们从基础开始.

CLPFD为CLP(Z)

你在这里做的事情对许多Prolog程序员来说仍然不常见.您将有限域约束用于一般整数算术.也就是说,您正在使用CLPFD作为一个纯粹的替补中找到的moded表达式求值(is)/2,(>)/2等等.因此,您希望扩展有限域范例,假设我们在有限的给定间隔内表达所有内容.实际上,将此扩展称为CLP(Z)更合适.

此扩展在每个提供有限域的Prolog中都不起作用.实际上,只有SICStus,SWI和YAP才能正确处理无限区间的情况.当其他系统成功或失败时,其他系统可能会失败或成功 - 主要是当整数变得过大时.

了解不终止

第一个问题是了解原始程序未终止的实际原因.为此,我将使用故障片.也就是说,我false在你的程序中添加目标.关键是:如果结果程序没有终止,那么原始程序也不会终止.因此,(假定的)原始程序的最小故障片段是:

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

有两种来源未结束的位置:一个是,对于给定 F有对无穷多的价值观F1和F2.通过观察可以很容易地解决这个问题F1 #> 0, F2 #>= 0.

另一个与Prolog的执行机制更相关.为了说明这一点,我将补充一下F2 #= 0.同样,因为生成的程序没有终止,原始程序也会循环.

fiborig(0,0) :- false.
fiborig(1,1) :- false.
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以提高效率.

fibmin(0,0).
fibmin(1,1).
fibmin(N,F) :-
   N #> 1,
   N1 #= N-1,
   N2 #= N-2,
   F1 #> 0,
   F2 #>= 0,
   F1 #>= F2,
   F #= F1+F2,
   fibmin(N2,F2),
   fibmin(N1,F1).

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

               SICStus                  SWI
             answer/total
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-1三次约束!

Answer 2

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

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

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