動態遞推演算法

㈠ 遞推法的定義是什麼

遞推法的定義是一種用若干步可重復的簡運算規律來描述復雜問題的方法。遞推是序列計算機中的一種常用演算法。它是按照一定的規律來計算序列中的每個項，通常是通過計算機前面的一些項來得出序列中的指定象的值。

其思想是把一個復雜的龐大的計算過程轉化為簡單過程的多次重復，該演算法利用了計算機速度快和不知疲倦的機器特點。

遞推法的解釋

是指從已知的初始條件出發，依據某種遞推關系，逐次推出所要求的各中間結果及最後結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡後確定。遞推聯系法是指通過研究遞推數列當中相鄰的兩個或者三個數字之間的遞推關系而找到解題關鍵的方法。

通過一項推出下一項的遞推數列為一項遞推數列，在利用遞推聯系法解題時是研究相鄰的兩個數字之間的關系，俗稱圈兩數法。通過前兩項推出第三項的遞推數列為兩項遞推數列，在利用此法解題時是研究相鄰的三個數字之間的關系，俗稱圈三數法。

㈡ 動態規劃的推法 謝謝

DP是把一個很大的有階段性有最佳答案問題分割成許多子問題，每個子問題有自己的最優情況（最優子結構），也就是說，每個動態規劃的問題都是有許多最有子結構接和起來的，而推法就是要分割出最有子結構
然後對這個小問題得出最優的答案，並由此推出全局的最優解

1.最優子結構性質；

設Q[i,j]表示第i顆珠子到第j顆珠子合並所產生的能量。顯然Q[1,n]表示的是合並產生的總的能量。給定一種標號方法，maxQ[1,n]就是所要求的。設最後一次合並在k處進行，則有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。
證明：假設Q[1,k]不是最大，則必然存在一Q'[1,k]>Q[1,k]。那麼就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。這與Q[1,n]的最優性矛盾

能量項鏈其實就是石子合並

演算法分析
競賽中多數選手都不約而同地採用了盡可能逼近目標的貪心法來逐次合並：從最上面
的一堆開始，沿順時針方向排成一個序列。 第一次選得分最小（最大）的相鄰兩堆合並，
形成新的一堆；接下來，在N－1堆中選得分最小（最大）的相鄰兩堆合並……，依次類推，
直至所有石子經N－1次合並後形成一堆。

例如有6堆石子，每堆石子數（從最上面一堆數起，順時針數）依次為3 46 5
4 2

（圖6.2-5）
要求選擇一種合並石子的方案，使得做5次合並，得分的總和最小。
按照貪心法，合並的過程如下：
每次合並得分
第一次合並 3 4 6 5 4 2 5
第二次合並 5 4 6 5 4 9
第三次合並 9 6 5 4 9
第四次合並 9 6 9 15
第五次合並 15 9 24
24
總得分＝5＋9＋9＋15＋24＝62

但是當我們仔細琢磨後，可得出另一個合並石子的方案：
每次合並得分
第一次合並 3 4 6 5 4 2 7
第二次合並 7 6 5 4 2 13
第三次合並 13 5 4 2 6
第四次合並 13 5 6 11
第五次合並 13 11 24
24
總得分＝7＋6＋11＋13＋24＝61
顯然，後者比貪心法得出的合並方案更優。 題目中的示例故意造成一個貪心法解題的
假像，誘使讀者進入「陷阱」。為了幫助讀者從這個「陷阱」里走出來， 我們先來明確一
個問題：

1．最佳合並過程符合最佳原理
使用貪心法至所以可能出錯， 是因為每一次選擇得分最小（最大）的相鄰兩堆合並，
不一定保證餘下的合並過程能導致最優解。聰明的讀者馬上會想到一種理想的假設：如果N
－1次合並的全局最優解包含了每一次合並的子問題的最優解，那麼經這樣的N－1次合並後
的得分總和必然是最優的。
例如上例中第五次合並石子數分別為13和11的相鄰兩堆。 這兩堆石頭分別由最初
的第1，2，3堆（石頭數分別為3，4，6）和第4，5，6堆（石頭數分別為5，4，
2）經4次合並後形成的。於是問題又歸結為如何使得這兩個子序列的N－2 次合並的得分
總和最優。為了實現這一目標，我們將第1個序列又一分為二：第1、2堆構成子序列1，
第3堆為子序列2。第一次合並子序列1中的兩堆，得分7； 第二次再將之與子序列2的
一堆合並，得分13。顯然對於第1個子序列來說，這樣的合並方案是最優的。同樣，我
們將第2個子序列也一分為二；第4堆為子序列1，第5，6堆構成子序列2。第三次合
並子序列2中的2堆，得分6；第四次再將之與子序列1中的一堆合並，得分13。顯然
對於第二個子序列來說，這樣的合並方案也是最優的。 由此得出一個結論——6堆石子經
過這樣的5次合並後，得分的總和最小。
我們把每一次合並劃分為階段，當前階段中計算出的得分和作為狀態， 如何在前一次
合並的基礎上定義一個能使目前得分總和最大的合並方案作為一次決策。很顯然，某階段
的狀態給定後，則以後各階段的決策不受這階段以前各段狀態的影響。 這種無後效性的性
質符最佳原理，因此可以用動態規劃的演算法求解。

2．動態規劃的方向和初值的設定
採用動態規劃求解的關鍵是確定所有石子堆子序列的最佳合並方案。 這些石子堆子序
列包括：
｛第1堆、第2堆｝、｛第2堆、第3堆｝、……、｛第N堆、第1堆｝；
｛第1堆、第2堆、第3堆｝、｛第2堆、第3堆、第4堆｝、……、｛第N堆、第1
堆、第2堆｝；
……
｛第1堆、……、第N堆｝｛第1堆、……、第N堆、第1堆｝……｛第N堆、第1堆、
……、第N－1堆｝

為了便於運算，我們用〔i，j〕表示一個從第i堆數起，順時針數j堆時的子序列
｛第i堆、第i＋1堆、……、第（i＋j－1）mod n堆｝
它的最佳合並方案包括兩個信息：
①在該子序列的各堆石子合並成一堆的過程中，各次合並得分的總和；
②形成最佳得分和的子序列1和子序列2。由於兩個子序列是相鄰的， 因此只需記住
子序列1的堆數；
設
f〔i，j〕——將子序列〔i，j〕中的j堆石子合並成一堆的最佳得分和；
c〔i，j〕——將〔i，j〕一分為二，其中子序列1的堆數；
（1≤i≤N，1≤j≤N）
顯然，對每一堆石子來說，它的
f〔i，1〕＝0 c〔i，1〕＝0 （1≤i≤N）
對於子序列〔i，j〕來說，若求最小得分總和，f〔i，j〕的初始值為∞； 若求最大得
分總和，f〔i，j〕的初始值為0。（1≤i≤N，2≤j≤N）。
規劃的方向是順推。先考慮含二堆石子的N個子序列（各子序列分別從第1堆、第2堆、
……、第N堆數起，順時針數2堆）的合並方案
f〔1，2〕，f〔2，2〕，……，f〔N，2〕
c〔1，2〕，c〔2，2〕，……，c〔N，2〕

然後考慮含三堆石子的N個子序列（各子序列分別從第1堆、第2堆、……、第N堆
數起，順時針數3堆）的合並方案
f〔1，3〕，f〔2，3〕，……，f〔N，3〕
c〔1，3〕，c〔2，3〕，……，c〔N，3〕
……

依次類推，直至考慮了含N堆石子的N個子序列（各子序列分別從第1堆、第2堆、 …
…、第N堆數起，順時針數N堆）的合並方案
f〔1，N〕，f〔2，N〕，……，f〔N，N〕
c〔1，N〕，c〔2，N〕，……，c〔N，N〕

最後，在子序列〔1，N〕，〔2，N〕，……，〔N，N〕中，選擇得分總和（f值）最
小（或最大）的一個子序列〔i，N〕（1≤i≤N），由此出發倒推合並過程。

3．動態規劃方程和倒推合並過程
對子序列〔i，j〕最後一次合並，其得分為第i堆數起，順時針數j堆的石子總數t。被
合並的兩堆石子是由子序列〔i，k〕和〔（i＋k－1）modn＋1，j－k〕（1≤k≤j－1）
經有限次合並形成的。為了求出最佳合並方案中的k值，我們定義一個動態規劃方程：
當求最大得分總和時
f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）

當求最小得分總和時
f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）
其中x＝（i＋k－1）modn＋1，即第i堆數起，順時針數k＋1堆的堆序號。

例如對（圖6．2－4）中的6堆石子，按動態規劃方程順推最小得分和。 依次得出含
二堆石子的6個子序列的合並方案
f〔1，2〕＝7 f〔2，2〕＝10 f〔3 ，2〕＝11
c〔1，2〕＝1 c〔2，2〕＝1 c〔3，2〕＝1
f〔4，2〕＝9 f〔5，2〕＝6 f〔6，2〕＝5
c〔4，2〕＝1 c〔5， 2〕＝1 c〔6，2〕＝1

含三堆石子的6個子序列的合並方案
f〔1，3〕＝20 f〔2，3〕＝25 f〔3，3〕＝24
c〔1，3〕＝2 c〔2，3〕＝2 c〔3，3〕＝1
f〔4，3〕＝17 f〔5，3〕＝14 f〔6，3〕＝14
c〔4，3〕＝1 c〔5，3〕＝1 c〔6，3〕＝2

含四堆石子的6個子序列的合並方案
f〔1，4〕＝36 f〔2，4〕＝38 f〔3，4〕＝34
c〔1，4〕＝2 c〔2，4〕＝2 c〔3，4〕＝1
f〔4，4〕＝28 f〔5，4〕＝26 f〔6，4〕＝29
c〔4，4〕＝1 c〔5，4〕＝2 c〔6，4〕＝3

含五堆石子的6個子序列的合並方案
f〔1，5〕＝51 f〔2，5〕＝48 f〔3，5〕＝45
c〔1，5〕＝3 c〔2，5〕＝2 c〔3，5〕＝2
f〔4，5〕＝41 f〔5，5〕＝43 f〔6，5〕＝45
c〔4，5〕＝2 c〔5，5〕＝3 c〔6，5〕＝3

含六堆石子的6個子序列的合並方案
f〔1，6〕＝61 f〔2，6〕＝62 f〔3，6〕＝61
c〔1，6〕＝3 c〔2，6〕＝2 c〔3，6〕＝2
f〔4，6〕＝61 f〔5，6〕＝61 f〔6，6〕＝62
c〔4，6〕＝3 c〔5，6〕＝4 c〔6，6〕＝3

f〔1，6〕是f〔1，6〕，f〔2，6〕，……f〔6，6〕中的最小值，表明最小
得分和是由序列〔1，6〕經5次合並得出的。我們從這個序列出發， 按下述方法倒推合
並過程：
由c〔1，6〕＝3可知，第5次合並的兩堆石子分別由子序列〔1，3〕和子序列〔
4，3〕經4次合並後得出。其中
c〔1，3〕＝2可知由子序列〔1，3〕合並成的一堆石子是由子序列〔1，2〕和
第三堆合並而來的。而c〔1，2〕＝1，以表明了子序列〔1，2〕的合並方案是第1堆
合並第2堆。
由此倒推回去，得出第1，第2次合並的方案
每次合並得分
第一次合並 3 4 6…… 7
第二次合並 7 6…… 13
13……
子序列〔1，3〕經2次合並後合並成1堆， 2次合並的得分和＝7＋13＝20。
c〔4，3〕＝1，可知由子序列〔4，3〕合並成的一堆石子是由第4堆和子序列〔5，
2〕合並而來的。而c〔5，2〕＝1，又表明了子序列〔5，2〕的合並方案是第5堆合
並第6堆。由此倒推回去，得出第3、第4次合並的方案
每次合並得分
第三次合並 ……54 2 6
第四次合並 ……5 6 11
……11
子序列〔4，3〕經2次合並後合並成1堆，2次合並的得分和＝6＋11＝17。
第五次合並是將最後兩堆合並成1堆，該次合並的得分為24。
顯然，上述5次合並的得分總和為最小
20＋17＋24＝61

上述倒推過程，可由一個print（〔子序列〕）的遞歸演算法描述
procere print （〔i，j〕）
begin
if j〈〉1 then ｛繼續倒推合並過程
begin
print（〔i，c〔i，j〕）；｛倒推子序列1的合並過程｝
print（〔i＋c〔i，j〕－1）mod n＋1，j－c〔i，j〕）
｛倒推子序列2的合並過程｝
for K：＝1 to N do｛輸出當前被合並的兩堆石子｝
if （第K堆石子未從圈內去除）
then begin
if（K＝i）or（K＝X）then置第K堆石子待合並標志
else第K堆石子未被合並；
end；｛then｝
第i堆石子數←第i堆石子數＋第X堆石子數；
將第X堆石子從圈內去除；
end；｛then｝
end；｛print｝
例如，調用print（〔1，6〕）後的結果如下：
print（〔1，6〕）⑤
│
┌——————┴——————┐
│ │
print（〔1，3〕）② print（〔4，3〕）④
│ │
print（〔1，2〕）① ┌—————┴—————┐
│ │ │
│
┌—————┴—————┐ print（〔4，1〕） print（〔5，2〕）③
│ │ │
print（〔1，1〕） print（〔2，1〕） │
┌——————┴——————┐
│ │
print（〔5，1〕） print（〔6，1〕）
（圖6.2-5）
其中回溯至
① 顯示 3 46 5 4
② 顯示 7 65 4 2
③ 顯示 13 54 2
④ 顯示 135 6
⑤ 顯示 13 11
注:調用print過程後，應顯示6堆石子的總數作為第5次合並的得分

㈢ 遞推演算法是怎麼回事

遞推定義
遞推演算法是一種簡單的演算法，即通過已知條件，利用特定關系得出中間推論，直至得到結果的演算法。

遞推演算法分為順推和逆推兩種。

順推法
所謂順推法是從已知條件出發，逐步推算出要解決的問題的方法叫順推。

如斐波拉契數列，設它的函數為f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。則我們通過順推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我們要求的解。

逆推法
所謂逆推法從已知問題的結果出發，用迭代表達式逐步推算出問題的開始的條件，即順推法的逆過程，稱為逆推。

遞推與遞歸的比較
相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.

比如階乘函數：f(n)=n*f(n-1)

在f(3)的運算過程中,遞歸的數據流動過程如下:

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

而遞推如下:

f(0)-->f(1)-->f(2)-->f(3)

由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.

㈣ 遞推估計演算法的概述

遞推估計演算法recursive estimation algorithm
利用時刻t上的參數估計、存儲向量與時刻 t+1上測量的輸入和輸出值u(t+1)和y(t+1)計算新參數值(t+1),再根據(t+1)計算出新參數值(t+2)，直到獲得滿意的參數值為止。這種演算法的每一步計算量都比較小，能夠使用小型計算機進行離線或在線參數估計，可以估計時變參數，也可以實時估計適應控制器的參數（見適應控制系統）。20世紀60年代，遞推估計演算法得到迅速發展，到了70年代產生了許多不同的方法，例如，有離線方法的各種變形、卡爾曼濾波法、隨機逼近方法和模型參考適應參數遞推估計法等。
遞推估計演算法的各種方法可以用一個統一的公式來描述：