3

我正在使用 SWI Prolog 学习 Prolog，我对斐波那契数计算程序的以下两种解决方案有疑问：

第一个是这样的：

fib(1,1).   
fib(2,1).   


fib(N,F) :- N > 2,      
            N1 is N-1,      
        fib(N1,F1),     
            N2 is N-2,      
            fib(N2,F2),     
            F is F1+F2.

对我来说很清楚它的工作原理，它非常简单。

然后我有第二个版本，在阅读代码时，它似乎与前一个版本一样工作，但之后它计算了 N 的斐波那契数，通过asserta/2谓词将其保存在 Prolog 数据库中，以便之后重用。

因此，例如，如果我计算 10 和 11 的斐波那契数，当我计算 12 的斐波那契数时，我将考虑使用前 2 次计算的结果。

所以我的代码是：

:-dynamic fibDyn/2.

fibDyn(1,1).
fibDyn(2,1).

fibDyn(N,F) :- N > 2,
               N1 is N-1,
               fibDyn(N1,F1),
               N2 is N-2,
               fibDyn(N2,F2),
               F is F1+F2,
               asserta(fibDyn(N,F)).

在我看来，逻辑与前一个相同：

如果 N>2，F 是 N 的斐波那契数，并使用递归来计算 N 的斐波那契数（如前面的示例中所示）

如果我要求计算我已经计算的数字的斐波那契数的数量并将其放入其前身（或其中一些）的斐波那契数的数据库中，我希望该程序更快，但在我看来它可以工作一种奇怪的方式：它太快了，并且能够直接计算非常大的整数的斐波那契数（其他版本在这么大的数字上出错）

另一个奇怪的事情是，如果我对查询进行跟踪，我会得到如下信息：

[trace]  ?- fibDyn(200,Fib).
   Call: (6) fibDyn(200, _G1158) ? creep
   Exit: (6) fibDyn(200, 280571172992510140037611932413038677189525) ? creep
Fib = 280571172992510140037611932413038677189525 .

如您所见，似乎不执行斐波那契谓词的代码，而是直接获取结果（从哪里？！？！）

如果我执行这个查询（使用第一个版本），我会得到程序将计算它：

[trace]  ?- fib(3,Fib).
   Call: (6) fib(3, _G1158) ? creep
^  Call: (7) 3>2 ? creep
^  Exit: (7) 3>2 ? creep
^  Call: (7) _G1233 is 3+ -1 ? creep
^  Exit: (7) 2 is 3+ -1 ? creep
   Call: (7) fib(2, _G1231) ? creep
   Exit: (7) fib(2, 1) ? creep
^  Call: (7) _G1236 is 3+ -2 ? creep
^  Exit: (7) 1 is 3+ -2 ? creep
   Call: (7) fib(1, _G1234) ? creep
   Exit: (7) fib(1, 1) ? creep
^  Call: (7) _G1158 is 1+1 ? creep
^  Exit: (7) 2 is 1+1 ? creep
   Exit: (6) fib(3, 2) ? creep
Fib = 2 .

为什么？我希望第二个版本（使用asserta谓词的版本）将计算两个数字的斐波那契数，并使用这些值生成下一个的解决方案。

例如，我可能有以下情况：我还没有计算任何斐波那契数，我要求计算 N=4 的斐波那契数，所以它计算它（如在第二个发布的堆栈跟踪中）。

所以我要求计算 N=5 的斐波那契数，他使用 N=4 的斐波那契数来保存它。然后我要求它计算 N=6 的斐波那契数，它最终可以使用保存的 4 和 5 的斐波那契数

我错过了什么？你能帮我理解吗？

4

3 回答 3

3

TL;DR：用于retractall从内存中擦除所有先前断言的事实。

将您的定义更改为

:- dynamic fibDyn/2.
:- retractall( fibDyn(_,_) ).  %% without this, you'll retain all the previous 
                               %% facts even if you reload the program
fibDyn(1,1).
fibDyn(2,1).

fibDyn(N,F) :- N > 2,
               N1 is N-1,
               fibDyn(N1,F1),
               N2 is N-2,
               fibDyn(N2,F2),
               F is F1+F2,
               asserta( (fibDyn(N,F):-!) ).

注意断言规则内的切口。还要注意声明。retractall没有它，即使您重新加载程序，所有先前断言的事实都将保留在内存中。这可能就是您立即获得结果的原因。

运行?- fibDyn(10,X)一次后，您可以在数据库中看到所有断言的事实：

12 ?- listing(fibDyn).
:- dynamic fibDyn/2.

fibDyn(10, 55) :- !.
fibDyn(9, 34) :- !.
fibDyn(8, 21) :- !.
fibDyn(7, 13) :- !.
fibDyn(6, 8) :- !.
fibDyn(5, 5) :- !.
fibDyn(4, 3) :- !.
fibDyn(3, 2) :- !.
fibDyn(1, 1).
fibDyn(2, 1).
fibDyn(A, D) :-
        A>2,
        B is A+ -1,
        fibDyn(B, E),
        C is A+ -2,
        fibDyn(C, F),
        D is E+F,
        asserta((fibDyn(A, D):-!)).

true.

这就是为什么它运行得如此之快。您看到的速度差异是指数和线性时间复杂度算法之间的差异。

下次调用它时，它可以访问所有先前计算的结果：

[trace] 15 ?- fibDyn(10,X).
   Call: (6) fibDyn(10, _G1068) ? creep
   Exit: (6) fibDyn(10, 55) ? creep
X = 55.

[trace] 16 ?-

这解释了您的fibDyn(200,X)呼叫跟踪输出。您可能在之前已经计算过一次或两次之后尝试过它。

以下是我下一次请求第 11 个号码时发生的情况：

[trace] 35 ?- fibDyn(11,X).
   Call: (6) fibDyn(11, _G1068) ? creep
   Call: (7) 11>2 ? creep
   Exit: (7) 11>2 ? creep
   Call: (7) _G1143 is 11+ -1 ? creep
   Exit: (7) 10 is 11+ -1 ? creep
   Call: (7) fibDyn(10, _G1144) ? creep
   Exit: (7) fibDyn(10, 55) ? creep
   Call: (7) _G1146 is 11+ -2 ? creep
   Exit: (7) 9 is 11+ -2 ? creep
   Call: (7) fibDyn(9, _G1147) ? creep
   Exit: (7) fibDyn(9, 34) ? creep
   Call: (7) _G1068 is 55+34 ? creep
   Exit: (7) 89 is 55+34 ? creep
^  Call: (7) asserta((fibDyn(11, 89):-!)) ? creep
^  Exit: (7) asserta((fibDyn(11, 89):-!)) ? creep
   Exit: (6) fibDyn(11, 89) ? creep
X = 89.

[trace] 36 ?-

然后再次：

[trace] 36 ?- fibDyn(11,X).
   Call: (6) fibDyn(11, _G1068) ? creep
   Exit: (6) fibDyn(11, 89) ? creep
X = 89.
于 2013-05-03T12:34:16.053 回答
3

您的第一个解决方案

fib(1,1).   
fib(2,1).   
fib(N,F) :-
  N > 2 ,      
  N1 is N-1 ,      
  fib(N1,F1) ,     
  N2 is N-2 ,      
  fib(N2,F2) ,     
  F is F1+F2
  .

效率不是很高。对于初学者来说，它不是尾递归的，它以指数时间运行（如前所述）。我敢打赌，这个应该在线性时间内运行的递归实现将至少与您的动态解决方案一样快（如果不是更快）：

fibonacci( 1 , 1 ) .
fibonacci( 2 , 1 ) .
fibonacci( N , V ) :- N>2, fibonacci( 1 , 1 , 3 , N , V ) .

fibonacci( X , Y , N , N , V ) :-
  V is X+Y
  .
fibonacci( X , Y , T , N , V ) :-
  Z  is X + Y ,
  T1 is T + 1 ,
  fibonacci( Y , Z , T1 , N , V )
  .

需要注意的重要一点是，斐波那契数列只需要跟踪序列中的前两个元素。为什么要在每次迭代中重新计算它们中的每一个？只需保持如上的滑动窗口即可。

斐波那契数列更有趣的特性之一是，当您进一步进入数列时，任何两个相邻值的比率越来越接近phi，即黄金均值。更有趣的是，无论使用哪两个值来播种序列，只要它们是非负的并且其中至少一个为零，这都是正确的。

一个更通用的解决方案可以让您使用所需的任何值来为序列播种，可能是这样的：

fibonacci( Seed1 , Seed2 , Limit , N , Value ) :-
  Seed1 >= 0       ,
  Seed2 >= 0       ,
  X is Seed1+Seed2 ,
  X > 0            ,
  Limit >= 0        ,
  fibonacci( Seed1 , Seed2 , 3 , Limit , N , Value )
  .

fibonacci( S1 , _  , _ , L , 1 , S1 ) :- 1 =< L .
fibonacci( _  , S2 , _ , L , 2 , S2 ) :- 2 =< L .
fibonacci( S1 , S2 , T , L , T , V  ) :-          % T > 2,
  T =< L ,
  V is S1+S2
  .
fibonacci( S1 , S2 , T , L , N , V ) :- N > T,    % T > 2,
  T =< L        ,
  S3 is S1 + S2 ,
  T1 is T  + 1  ,
  fibonnaci( S2 , S3 , T1 , L , N , V )
  .
于 2013-05-03T17:33:14.983 回答
1

这实际上不是关于 Prolog，而是关于算法。朴素的递归解决方案需要 O(2**n) 步来计算，而第二个版本使用 memoization 将其减少到 O(n)。

要了解这意味着什么，请尝试在纸上计算 fib(4)，而无需查找您之前计算的内容。然后，再做一次，但要记好笔记并尽可能查找。

之后，如果您尝试以第一种方式计算 fib(5)，则首先必须计算 fib(4) 和 fib(3)。这就是你的第一个算法所做的。请注意，为了计算 fib(4)，您需要再次计算 fib(3)。所以你最终会一遍又一遍地做同样的计算。

另一方面，您可以查看这两个值并立即获得结果。这就是你的第二个算法所做的。

使用 O(2**n)，每个后续值都需要两倍的工作量，而使用 O(n)，您只需要做与前一个值一样多的工作。

于 2013-05-03T13:42:00.170 回答