在第一次解决斐波那契对后防止回溯 [英] Prevent backtracking after first solution to Fibonacci pair

问题描述

当 F 是第 N 个斐波那契数时，术语 fib(N,F) 为真.

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

:-use_module(library(clpfd)).纤维(0,0).纤维(1,1).纤维(N，F):-N#>1、N#=＜F + 1,F#＞= N-1，F#>0,N1 #= N - 1,N2 #= N - 2,F1 #=

在执行此查询时(在 SICStus Prolog 中)，找到 N 的第一个(正确的)匹配项(相当迅速):

<代码>|?-fib(X,377).X = 14 ?

当继续(通过输入;")查看是否有任何进一步的匹配项(根据定义这是不可能的)时，需要花费大量时间(与第一个匹配项相比)才能始终回复否":

<代码>|?-fib(X,377).X = 14 ?;不

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

解决方案

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

首先是使用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 正确处理无限区间的情况.其他系统可能会失败或当他们宁愿成功或失败时成功 - 主要是在整数时变得太大了.

了解不终止

第一个问题是了解你原来的真正原因程序没有终止.为此，我将使用 failure切片.那是，我将 false 目标添加到您的程序中.重点是:如果结果程序不会终止，那么原始程序也不会终止不终止.所以你的(假定的)最小的失败部分原程序是:

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

这里有两个不终止的来源:一个是给定的F F1 和 F2 有无数个值.那可以是通过观察 F1 #> 很容易处理.0, F2 #>= 0.

另一个与Prolog的执行机制有关.到说明一下，我将添加 F2 #= 0.再次，因为结果程序不会终止，原程序也会循环.

fiborig(0,0) :- false.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), 假,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.380sfibmin: 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 三次！

The term fib(N,F) is true when F is the Nth Fibonacci number.

The following Prolog code is generally working for me:

:-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).

When executing this query (in SICStus Prolog), the first (and correct) match is found for N (rather instantly):

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

When proceeding (by entering ";") to see if there are any further matches (which is impossible by definition), it takes an enormous amount of time (compared to the first match) just to always reply with no:

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

Being rather new to Prolog, I tried to use the Cut-Operator (!) in various ways, but I cannot find a way to prevent the search after the first match. Is it even possible given the above rules? If yes, please let me know how :)

解决方案

There are two parts to get what you want.

The first is to use call_semidet/1 which ensures that there is exactly one answer. See links for an implementation for SICStus, too. In the unlikely event of having more than one answer, call_semidet/1 produces a safe error. Note that once/1 and !/0 alone simply cut away whatever there has been.

However, you will not be very happy with call_semidet/1 alone. It essentially executes a goal twice. Once to see if there is no more than one answer, and only then again to obtain the first answer. So you will get your answer much later.

The other part is to speed up your definition such that above will not be too disturbing to you. The solution suggested by CapelliC changes the algorithm altogether which is specific to your concrete function but does not extend to any other function. But it also describes a different relation.

Essentially, you found the quintessential parts already, you only need to assemble them a bit differently to make them work. But, let's start with the basics.

CLPFD as CLP(Z)

What you are doing here is still not that common to many Prolog programmers. You use finite domain constraints for general integer arithmetics. That is, you are using CLPFD as a pure substitute to the moded expression evaluation found in (is)/2, (>)/2 and the like. So you want to extend the finite domain paradigm which assumes that we express everything within finite given intervals. In fact, it would be more appropriate to call this extension CLP(Z).

This extension does not work in every Prolog offering finite domains. In fact, there is only SICStus, SWI and YAP that correctly handle the case of infinite intervals. Other systems might fail or succeed when they rather should succeed or fail - mostly when integers are getting too large.

Understanding non-termination

The first issue is to understand the actual reason why your original program did not terminate. To this end, I will use a failure slice. That is, I add false goals into your program. The point being: if the resulting program does not terminate then also the original program does not terminate. So the minimal failure slice of your (presumed) original program is:

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).

There are two sources for non-termination here: One is that for a given F there are infinitely many values for F1 and F2. That can be easily handled by observing that F1 #> 0, F2 #>= 0.

The other is more related to Prolog's execution mechanism. To illustrate it, I will add F2 #= 0. Again, because the resulting program does not terminate, also the original program will loop.

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).

So the actual problem is that the goal that might have 0 as result is executed too late. Simply exchange the two recursive goals. And add the redundant constraint F2 #=< F1 for efficiency.

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).

On my lame laptop I got the following runtimes for 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

Take the sum of both to get the runtime for call_semidet/1.

Note that SWI's implementation is written in Prolog only, whereas SICStus is partly in C, partly in Prolog. So when porting SWI's (actually @mat's) clpfd to SICStus, it might be comparable in speed.

There are still many things to optimize. Think of indexing, and the handling of the "counters", N, N1, N2.

---

Also your original program can be improved quite a bit. For example, you are unnecessarily posting the constraint F #>= N-1 three times!

这篇关于在第一次解决斐波那契对后防止回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！