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

问题描述

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

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

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

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

在执行此查询时(在SICStus Prolog中)，找到了N的第一个(也是正确的)匹配项(而立即):

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

对于Prolog来说还很陌生，我尝试以各种方式使用Cut-Operator(!)，但是在第一个匹配项之后我找不到能阻止搜索的方法.鉴于以上规则，是否有可能?如果是，请让我知道如何:)

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.

首先是使用 call_semidet/1 这样可以确保只有一个答案.请参阅链接 SICStus的实现.万一有更多的可能性 除了一个答案，call_semidet/1会产生一个安全错误.注意 once/1和!/0只是简单地删除了已有的内容.

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.

但是，您不会对call_semidet/1感到非常满意.它 本质上执行两次目标.一次看看是否没有更多 多于一个答案，只有这样才能再次获得第一个答案.所以 您将在更晚的时候得到答案.

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.

另一部分是加快您的定义，以使上面的内容不会 太打扰你了. CapelliC建议的解决方案更改 特定于您的具体功能的算法 但不会扩展到任何其他功能.但这也描述了 不同的关系.

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.

您在这里所做的工作仍然不是许多Prolog所共有的 程序员.您对一般整数使用有限域约束 算术.也就是说，您正在使用CLPFD替代 在(is)/2，(>)/2和 喜欢.因此，您想扩展有限域范式，它假定 我们在有限的给定间隔内表达一切.实际上， 将此扩展称为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).

此扩展不适用于每个Prolog产品有限 域.实际上，只有SICStus，SWI和YAP可以正确地进行 处理无限间隔的情况.其他系统可能会失败或 当他们宁愿成功或失败时成功-主要是在整数时 变得太大了.

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.

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

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

这里有两种不终止的来源:一种是给定的 F F1和F2的值无穷多个.那可以是 观察F1 #> 0, F2 #>= 0即可轻松处理.

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.

另一个与Prolog的执行机制更相关.到 为了说明这一点，我将添加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).

所以实际的问题是目标可能包含0 被执行为时已晚.只需交换两个递归目标即可.并添加 冗余约束F2 #=< F1以提高效率.

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

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

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

取两者的总和即可获得call_semidet/1的运行时.

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

请注意，SWI的实现仅用Prolog编写，而 SICStus部分在C中，部分在Prolog中.因此，在将SWI(实际上是@mat)的clpfd移植到 SICStus，其速度可能相当.

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.

仍有许多要优化的地方.想一下索引，然后 计数器"，N，N1，N2的处理.

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

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

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

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