動態(tài)規(guī)劃概念、要素、步驟及范例

動態(tài)規(guī)劃CONTENTS概念基本要素步驟

范例動態(tài)規(guī)劃的基本思想

基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。補充

由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。動態(tài)規(guī)劃采用自底向上的方式遞推求值，并把中間結(jié)果存儲起來以便以后用來計算所需要求的解。（事實上是采用了空間換時間的算法）與分治法最大的差別

它不遞歸調(diào)用自身，但問題的基本解通常是用遞歸函數(shù)的形式來說明。而分治法是直接實現(xiàn)遞推的結(jié)果，往往會導(dǎo)致不止一次的遞歸調(diào)用適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上，進行進一步的求解）。動態(tài)規(guī)劃適用情況最優(yōu)化原理有重疊子問題無后效性如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢掌握動態(tài)規(guī)劃算法的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)重疊子問題性質(zhì)

求解的基本步驟

動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優(yōu)的活動路線)初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)

圖1動態(tài)規(guī)劃決策過程示意圖設(shè)計動態(tài)規(guī)劃算法的步驟劃分階段按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。確定狀態(tài)和狀態(tài)變量將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。確定決策并寫出狀態(tài)轉(zhuǎn)移方程因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實上常常是反過來做，根據(jù)相鄰兩個階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。尋找邊界條件給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。簡化設(shè)計動態(tài)規(guī)劃算法的步驟要素1(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。要素2(2)遞歸地定義最優(yōu)值。要素1(3)以自底向上的方式計算出最優(yōu)值。要素2(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。確定動態(tài)規(guī)劃三要素每個階段的狀態(tài)問題的階段從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化確定了動態(tài)規(guī)劃的這三要素，整個求解過程就可以用一個最優(yōu)決策表來描述，最優(yōu)決策表是一個二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某個階段某個狀態(tài)下的最優(yōu)值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運算求得問題的最優(yōu)解。動態(tài)規(guī)劃算法基本框架

for(j=1;j<=m;j=j+1)//第一個階段

xn[j]=初始值;for(i=n-1;i>=1;i=i-1)//其他n-1個階段

for(j=1;j>=f(i);j=j+1)//f(i)與i有關(guān)的表達式

xi[j]=j=max（或min）{g(xi-1[j1:j2]),......,g(xi-1[jk:jk+1])};t=g(x1[j1:j2]);//由子問題的最優(yōu)解求解整個問題的最優(yōu)解的方案print(x1[j1]);for(i=2;i<=n-1;i=i+1){t=t-xi-1[ji];for(j=1;j>=f(i);j=j+1)if(t=xi[ji])break;}范例二項式系數(shù)計算最短路徑問題最長公共子序列矩陣連乘問題流水作業(yè)調(diào)度流動推銷員問題背包問題整數(shù)規(guī)劃問題背包問題問題描述給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?問題解析對于一種物品，要么裝入背包，要么不裝。所以對于一種物品的裝入狀態(tài)可以取0和1.我們設(shè)物品i的裝入狀態(tài)為xi,xi∈(0,1)，此問題稱為0-11背包問題。背包問題問題描述給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?問題解析對于一種物品，要么裝入背包，要么不裝。所以對于一種物品的裝入狀態(tài)可以取0和1.我們設(shè)物品i的裝入狀態(tài)為xi,xi∈(0,1)，此問題稱為0/1背包問題。分析在0/1背包問題中，物體或者被裝入背包，或者不被裝入背包，只有兩種選擇。循環(huán)變量i，j意義：前i個物品能夠裝入載重量為j的背包中數(shù)組c意義：c[i][j]表示前i個物品能裝入載重量為j的背包中物品的最大價值若w[i]>j，第i個物品不裝入背包否則，若w[i]<=j且第i個物品裝入背包后的價值>c[i-1][j]，則記錄當(dāng)前最大價值（替換為第i個物品裝入背包后的價值）輸入輸入（已知）輸出（準備）intc[][];//背包價值數(shù)組，行表示第i件物品，列表示背包總重量intx[50];//存放裝入狀態(tài)的數(shù)組

物品重量數(shù)組w[]物品價值數(shù)組v[]背包總?cè)萘緾物品總個數(shù)nc[][]工作過程

物品重量數(shù)組w[]={22654}物品價值數(shù)組v[]={63546}背包總?cè)萘緾=10物品總個數(shù)n=5物品單量12345678910物品價值