常見動態(tài)規(guī)劃算法問題策略

1、常見動態(tài)規(guī)劃算法問題策略分析 2目錄一、動態(tài)規(guī)劃策略11.動態(tài)規(guī)劃介紹12.求解動態(tài)規(guī)劃問題步驟1二、幾種動態(tài)規(guī)劃算法的策略分析11.裝配線調(diào)度問題12.矩陣鏈乘問題23.最長公共子序列（LCS）34.最大字段和45.0-1背包問題4三、兩種解決策略51.自底向上策略52.自頂向上（備忘錄）策略53.優(yōu)缺點分析5四、總結(jié)6一、 動態(tài)規(guī)劃策略1. 動態(tài)規(guī)劃介紹動態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃?；舅枷肱c分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子

2、階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。與分治法最大的差別是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。2. 求解動態(tài)規(guī)劃問題步驟（1） 確定最優(yōu)解結(jié)構(gòu)（2） 遞歸定義最優(yōu)解的值（3） 自底向上計算最

3、優(yōu)解的值（4） 重構(gòu)最優(yōu)解二、 幾種動態(tài)規(guī)劃算法的策略分析1. 裝配線調(diào)度問題分析：首先確定最優(yōu)解結(jié)構(gòu)，分析問題可知大致分為兩種情況：從第一個站出站（j=1）和從第j個站出站（j=2）。當(dāng)j=1：貨物上線后只經(jīng)過一個站，f1j=e1+a1,1當(dāng)j=2，又可分為跳線和不跳線兩種情況：不跳線：f1j=f1j-1+a1,j跳線：當(dāng)貨物從f2跳到f1，有一個跳轉(zhuǎn)時間t2,j-1，則：f1j=f2j-1+t2,j-1+a1,j由對稱關(guān)系，f2j可同理得出，最后： f1,j=e1+ a1,1 j=1minf1,j-1+a1,j,f2,j-1+ t2,j-1+a1,j j2 f2,j=e2+ a2,1 j=

4、1minf2,j-1+a2,j,f1,j-1+ t1,j-1+a2,j j2傳輸完后，加上自動下線時間x1,x2,總裝配時間：f*=minf1,j+x1,f2,j+x2最后采用自底向上的方法求解算法并遞歸的輸出最優(yōu)解的值。2. 矩陣鏈乘問題分析：若只有一個矩陣，無最優(yōu)解。若大于一個矩陣：對于A1,A2,An， 我們得在Ak和Ak+1之間加上一個括號使得分開的兩個子矩陣鏈乘積最小，再分別對兩個子問題找到最優(yōu)的劃分結(jié)果：設(shè)mi,j 為計算矩陣鏈Ai.j 的乘積所需的最少標(biāo)量乘法次數(shù)。若：i=j，不需任何計算，即mi,j=0，否則：mi,j =mi,k+ mk+1,j+pi-1pkpj則最終公式為：

5、f1,j=0 i=jmin(mi,k+ mk+1,j+pi-1pkpj) i0 and xi=yj max(Ci-1,j,Ci,j-1) i,j0 and xi yj6根據(jù)遞歸式，我們能寫出一個遞歸算法來計算最長公共子序列，由于LCS的子問題過多，所以我們采用自底向上的計算。在這個過程中，我們需要借組一個數(shù)組bi,j來記錄最優(yōu)解得構(gòu)造過程，利用bi,j所記錄的元素來輸出最優(yōu)解。4. 最大字段和分析:求給定的n個整數(shù)（可能但不全為負(fù)）a1,a2,an, 的i跟j，使 ai 到 aj 的和最大。我們定義bj=max(sum(i:j)，為從i到j(luò)子段的最大子段和。我們比較bj-1+aj和aj的大小,

6、如果bj-10,顯然bj-1不是最大子段，此時bj=aj。反之，我們令bj-1 + aj = bj,找出最大的子段和。則：bj=max( bj-1+aj, aj ), 1=jsum，更新sum中的值，反之，繼續(xù)求解。直到程序進(jìn)行完畢，輸入sum中的最大子段和。5. 0-1背包問題分析：分?jǐn)?shù)背包問題可以采用貪心策略解決，但我們在求解0-1背包問題時，我們只能采用動態(tài)規(guī)劃策略。同樣地：首先構(gòu)造最優(yōu)子結(jié)構(gòu)。令ci,j表示利用前i個物品裝容量為j的背包所能獲得的最大價值，可分兩種情況：含物品n：去掉第n個物品，用W-wn容量的背包裝物品1,2，,n-1：ci,j=ci-1,j-wi+vi不含物品n：用

7、W容量背包裝物品1,2,n-1：ci,j=ci-1,j當(dāng)然，沒有物品或沒有容量，ci,j=0則總的遞歸式：Ci,j=0 i=0 or j=0Ci-1,j wijmax(Ci-1,j- wi+ vi,Ci-1,j) i0 and wij有上述遞歸方程，就可寫出相應(yīng)遞歸算法，但該遞歸算法復(fù)雜度太高，可用V0.n,0.W來保存子問題(i,j)的最大值。b1.n,1.W用來保存所做出的最優(yōu)選擇，以便構(gòu)造最優(yōu)解。在計算最優(yōu)解的時候，保存所做出的最優(yōu)決策，便可得到最優(yōu)解。三、 兩種解決策略1. 自底向上策略一般動態(tài)規(guī)劃問題都是基于此策略。在用這種方法時一般需要恰當(dāng)?shù)亩x子問題的規(guī)模，使得任何子問題都只依賴

8、于更小的子問題的求解。我們可以將問題的規(guī)模按照由大到小排列依次求解。每個子問題都只求解一次。2. 自頂向上（備忘錄）策略動態(tài)規(guī)劃有一個性質(zhì)為子問題重疊性質(zhì)，就是對于子問題在遞歸過程中不斷求解，雖然問題規(guī)模很小，但是求解次數(shù)會非常多，造成程序運行非常慢。在使用自頂向下的求解過程中，我們一般要設(shè)計一個備忘錄，在遞歸求解過程中對于已經(jīng)求解過的問題保存在備忘錄中，當(dāng)下次要使用時直接拿出來，不用再次求解。3. 優(yōu)缺點分析自頂向下只需要求解問題需要的解，不需要對所有子問題都去求解。但是它需要額外的遞歸開銷。自底向上必須對所有子問題進(jìn)行求解但是可有效減少計算時間和所需的存儲空間。四、 總結(jié)動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。解決動態(tài)規(guī)劃問題的關(guān)鍵是找到最最優(yōu)子結(jié)構(gòu)并定義出遞歸式，根據(jù)經(jīng)驗，通常會分為若干種情況分開討論，尤其注意容易遺漏的特殊情況（0、1、相等）。在求解計算時，如果我們能夠保存已解決的子問題的