http://www.cnblogs.com/chinazhangjie/archive/2010/11/16/1878400.html

動態(tài)規(guī)劃

動態(tài)規(guī)劃?

算法總體思想?

動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。

但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級。在用分治法求解時，有些子問題被重復(fù)計(jì)算了許多次。

如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時間算法。

動態(tài)規(guī)劃基本步驟:

(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。

(2)遞歸地定義最優(yōu)值。

(3)以自底向上的方式計(jì)算出最優(yōu)值。

(4)根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。

實(shí)例一、完全加括號的矩陣連乘積?

問題可遞歸定義：?

（1）單個矩陣是完全加括號的；

（2）矩陣連乘積A是完全加括號的 ，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即 A = （BC）。

設(shè)有四個矩陣A,B,C,D它們的維數(shù)分別是: A = 50*10 , B = 10*40 , C = 40*30 , D = 30*5

總共有五中完全加括號的方式：

?

例如：((A(BC))D): 10 * 40 * 30 + 10 * 30 * 50 + 50 * 30 * 5 = 34500

??? 給定矩陣{A1, A2, A3,..., An}，其中Ai與A(i+1)是可乘的。i = 1,2,3, ..., n - 1。考察這n個矩陣的連乘積A1*A2*A3...An.

由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號的方式來確定。

若一個矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。

矩陣連乘問題?

??? 給定矩陣{A1, A2, A3,..., An}，其中Ai與A(i+1)是可乘的。i = 1,2,3, ..., n - 1。考察這n個矩陣的連乘積A1*A2*A3...An. 如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少.

窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。

算法復(fù)雜度分析：

對于n個矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)

由于每種加括號方式都可以分解為兩個子矩陣的加括號問題

(A1...Ak)(A(k+1)…An)可以得到關(guān)于P(n)的遞推式如下：

動態(tài)規(guī)劃：將矩陣連乘積A(i)A(i+1)…A(j)簡記為A[i:j]，這里 i <= j。

考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個計(jì)算次序在矩陣A(k)和A(k+1)之間將矩陣鏈斷開，i <= k < j, 則其相應(yīng)完全加括號方式為(A(i)A(i+1)...A(k)) * (A(k+1)A(k+2)...A(j))。

計(jì)算量：A[i:k]的計(jì)算量加上A[k+1,j]，再加上A[i:k] * A[k+1][j]的計(jì)算量。

分析最優(yōu)解的結(jié)構(gòu)?

特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈 A[i:k]和A[k+1:j]的次序也是最優(yōu)的。

矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。

建立遞歸關(guān)系?

設(shè)計(jì)算A[i:j]，1 <= i <= j <= n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]

當(dāng)i = j時，A[i:j]=Ai，因此，m[i,i] = 0，i = 1,2,…,n

當(dāng)i < j時，m[i,j] = m[i,k] + m[k+1,j] + p(i-1)p(k)p(j)

這里A(i)的維數(shù)為p(i-1)*(i)(注：p(i-1)為矩陣A(i)的行數(shù)，p(i)為矩陣A[i]的列數(shù))

可以遞歸地定義m[i,j]為：

k的位置只有j - i種。

計(jì)算最優(yōu)值?

對于1 <= i <= j <= n不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個數(shù)最多只有：

（大括號表示C(n,2)，組合的意思。后面的符號表示 “緊漸近界記號”）

但是，在遞歸計(jì)算時，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。

用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個子問題只計(jì)算一次，而在后面需要時只要簡單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時間的算法。

用動態(tài)規(guī)劃法求最優(yōu)解?

連乘矩陣假如為：

計(jì)算過程為：

從m可知最小連乘次數(shù)為m[1][6] = 15125

從s可知計(jì)算順序?yàn)?(A1(A2A3))((A4A5))A6))

實(shí)現(xiàn)：

?

代碼

?

?

算法復(fù)雜度分析：?

算法matrixChain的主要計(jì)算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n^3)。因此算法的計(jì)算時間上界為O(n^3)。算法所占用的空間顯然為O(n^2)。

動態(tài)規(guī)劃算法的基本要素?

一、最優(yōu)子結(jié)構(gòu)?

矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。

在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。

利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。

同一個問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低）

二、重疊子問題

?遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。

?動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。

通常不同的子問題個數(shù)隨問題的大小呈多項(xiàng)式增長。因此用動態(tài)規(guī)劃算法只需要多項(xiàng)式時間，從而獲得較高的解題效率。

三、備忘錄方法

備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復(fù)求解。

實(shí)現(xiàn)（見矩陣連乘源碼）

實(shí)例二、最長公共子序列?

??? 若給定的序列X = {x1,x2,…,xm},則另一序列Z = {z1,z2,…,zk}，是X的子序列是指存在一個嚴(yán)格下表序列{i1,i2,…,ik}使得對于所有的j = 1,2,…k有zj = xij。例如，序列Z = {B,C,D,B}是序列X = {A,B,C,B,D,A,B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2,3,5,7}。

給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。

問題表述：給定2個序列X={x1,x2,…,xm}和Y = {y1,y2,…,yn}，找出X和Y的最長公共子序列。

最長公共子序列的結(jié)構(gòu)?

設(shè)序列X = {x1,x2,…,xm}和Y = {y1,y2,…,yn}的最長公共子序列為Z = {z1,z2,…,zk} ，則

(1)若xm = yn，則zk = xm = yn，且z(k-1)是x(m-1)和y(n-1)的最長公共子序列。

(2)若xm != yn且zk != xm，則Z是x(m-1)和Y的最長公共子序列。

(3)若xm != yn且zk != yn，則Z是X和y(n-1)的最長公共子序列。

由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

子問題的遞歸結(jié)構(gòu)?

由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列Xi和Yi的最長公共子序列的長度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i = 0或j = 0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j] = 0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：

由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率

計(jì)算最優(yōu)值和構(gòu)造最長公共子序列（見源碼）?

實(shí)現(xiàn)：?

? 代碼

?

?

算法的改進(jìn)

在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個數(shù)組元素的值所確定。對于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在時間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個值所確定的。

如果只需要計(jì)算最長公共子序列的長度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算c[i][j]時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長公共子序列的長度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。

實(shí)例三、最大子段和?

問題表述?

n個數(shù)(可能是負(fù)數(shù)）組成的序列a1,a2,…an.求該序列

例如:? 序列(-2,11,-4,13,-5,-2) ，最大子段和：

?????? 11 - 4 + 13＝20。

（1）窮舉算法： O(n3), O(n2)

（2）分治法：

將序列a[1:n]從n/2處截成兩段：a[1:n/2], a[n/2+1:n]

實(shí)例三、最大子段和

問題表述

n個數(shù)(可能是負(fù)數(shù)）組成的序列a1,a2,…an.求該序列?子序列的最大值。

也就是

?

例如:? 序列(-2,11,-4,13,-5,-2) ，最大子段和：

?????11 - 4 + 13＝20。

（1）窮舉算法： O(n3), O(n2)

（2）分治法：

將序列a[1:n]從n/2處截成兩段：a[1:n/2], a[n/2+1:n]

一共存在三種情況：

a.最大子段和出現(xiàn)在左邊一段

b.最大子段和出現(xiàn)在右邊一段

c.最大子段和跨越中間的斷點(diǎn)

對于前兩種情況，只需繼續(xù)遞歸調(diào)用，而對于第三種情況：

那么S1+S2是第三種情況的最優(yōu)值。

（3）動態(tài)規(guī)劃法：

定義b[j]：

含義：從元素i開始，到元素j為止的所有的元素構(gòu)成的子段有多個，這些子段中的子段和最大的那個。

那么：

如果：b[j-1] > 0, 那么b[j] = b[j-1] + a[j]

如果：b[j-1] <= 0,那么b[j] = a[j]

這樣，顯然，我們要求的最大子段和，是b[j]數(shù)組中最大的那個元素。

實(shí)現(xiàn)：

? 代碼

?

?

實(shí)例四、多邊形游戲

多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點(diǎn)構(gòu)成的多邊形。每個頂點(diǎn)被賦予一個整數(shù)值，每條邊被賦予一個運(yùn)算符”+”或”*”。所有邊依次用整數(shù)從1到n編號。

游戲第1步，將一條邊刪除。

隨后n-1步按以下方式操作：

(1)選擇一條邊E以及由E連接著的2個頂點(diǎn)V1和V2；

(2)用一個新的頂點(diǎn)取代邊E以及由E連接著的2個頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)值通過邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。

最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。

問題:?對于給定的多邊形，計(jì)算最高得分。

最優(yōu)子結(jié)構(gòu)性質(zhì)

按照順時針順序，多邊形和頂點(diǎn)的順序可以寫成：

????op[1], v[1], op[2], v[2],?…, op[n], v[n]

在所給多邊形中，從頂點(diǎn)i(1 <= i <= n)開始，長度為j(鏈中有j個頂點(diǎn))的順時針鏈p(i，j)?可表示為

v[i], op[i+1], v[i+1],…, op[i+j-1], v[i+j-1]

如果這條鏈在op[i + s]處進(jìn)行最后一次合并運(yùn)算(1 <= s <= j-1)，則可在op[i+s]處將鏈分割為2個子鏈：

從i開始長度為s的鏈：??p(i，s)

從i + s開始，長度為j - s的鏈：p(i + s，j-s)。

設(shè):

m1是對子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。

m2是p(i+s，j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。

依此定義有a <= m1 <= b，c <= m2 <= d

(1)當(dāng)op[i+s] = ‘+’時，顯然有a + c <= m <= b + d

(2)當(dāng)op[i+s] = ’*’時，有

min {ac，ad，bc，bd} <= m <= max {ac，ad，bc，bd}

換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。

實(shí)現(xiàn)：

代碼

?

分類:?Data structure and Algorithm

總結(jié)

以上是生活随笔為你收集整理的动态规划基本问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。