動態(tài)規(guī)劃_lyt.ppt

1、動態(tài)規(guī)劃,2009級信科1班 李遠韜,動態(tài)規(guī)劃的基本原理,將問題轉(zhuǎn)化為規(guī)模更小的問題解決。 動態(tài)規(guī)劃與搜索的區(qū)別在于動態(tài)規(guī)劃會將已經(jīng)解決過的子問題的解保存下來，下次需要時直接調(diào)用(以空間換時間)，而搜索則會將已經(jīng)計算過的問題再計算一遍。,狀態(tài)、階段與決策,狀態(tài)：用于描述一個子問題 階段：按照一定的順序計算所有子問題 決策：通過決策將一個問題轉(zhuǎn)化為更小的子問題,使用動態(tài)規(guī)劃的兩個基本條件,最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解只取決與子問題的最優(yōu)解，即局部最優(yōu)推出全局最優(yōu) 無后效性：問題只依賴于更小的子問題，即能夠按一定的順序計算每個子問題，使得每個子問題的解都只依賴于前面已經(jīng)計算過的問題的解,一個簡單的例子

2、：最長上升子序列,給出一個序列a1,a2,an,找到序列a的子序列a(i1),a(i2),.,a(il)，1=i1i2.il=n，a(i1)a(i2).a(il),使得l最大,一個簡單的例子：最長上升子序列,狀態(tài)：fi表示序列a1,a2,.,ai的包含ai的最長的子序列的長度 階段：按i從小到大劃分階段，即按照i從小到大的順序計算fi，計算f(i)時只依賴于前面計算過的f值 決策：枚舉f(i)對應(yīng)的子序列a(i1),a(i2),.,a(i(l-1),i中i(l-1)的值，設(shè)i(l-1)=j,則問題轉(zhuǎn)化為在a1,a2,.,aj中找最長上升子序列,一個簡單的例子：最長上升子序列,狀態(tài)轉(zhuǎn)移方程：f(

3、i)=maxf(j)+1,(1=ji,ajai) 時間復(fù)雜度：O(n2),動態(tài)規(guī)劃的兩種優(yōu)化方法,簡化狀態(tài)，減少狀態(tài)總數(shù) 減少可行的決策,牛場圍欄(fence),有N種木料，長度分別為L1,L2,.,LN,每種木料數(shù)量無限，每根木料最多可以削短M米，且只能削去整數(shù)米，用這些木料修建圍欄，問無法修建的最大圍欄的長度，如果這個值為無窮大或者任何長度的圍欄都可以修建，輸出-1 數(shù)據(jù)范圍：N=100,M=3000,1=Li=3000,簡化問題,預(yù)處理：將每根木料分別削去0,1,2,.,m，得到m根木料，再統(tǒng)計所有的木料長度，去除重復(fù) 問題簡化為有m根木料，長度分別為L1,L2,.,Lm(不能削短)，問

4、不能拼出的最長圍欄的長度（或輸出無解） 下面只討論簡化后的問題,牛場圍欄(fence),一個很自然的想法是通過動態(tài)規(guī)劃計算出對于每個長度L，能否通過現(xiàn)有的木料拼出，但是長度L是沒有限制的，即狀態(tài)的總數(shù)可以達到無限，必須減少狀態(tài)總數(shù),牛場圍欄(fence),如果存在長度為L的木料，注意到如果可以拼出長度為x的圍欄，那么長度為x+L,x+2L,x+3L,.,x+kL.,的圍欄都可以被拼出,牛場圍欄(fence),我們將狀態(tài)設(shè)為f(i)，(0=iL)表示最小的整數(shù)x,滿足x可以被拼出，且x mod L=i，如果x不存在，則f(i)為正無窮 為了減少狀態(tài)總數(shù)，加快速度，我們?nèi)=minL1,L2,.,

5、Lm 如果我們能計算出所有的f(i),則答案ans=maxf(i)-L,ans0時則所有長度的圍欄都可以被拼出,牛場圍欄(fence),狀態(tài)轉(zhuǎn)移方程： f(i)=minf(j)+Lk ,(j+Lk) mod L=i) 如何劃分階段？ 如果按照i從小到大劃分階段，不滿足無后效性,牛場圍欄(fence),仔細觀察狀態(tài)轉(zhuǎn)移方程 f(i)=minf(j)+Lk ,(j+Lk) mod L=i) 注意到f(0)=0,我們建立一個N個節(jié)點的圖，以0為源點，對所有滿足(j+Lk) mod L=i的點i,j，從i向j連一條長度為Lk的邊，則f(i)就等于從0到i的最短路 時間復(fù)雜度：O(L2),牛場圍欄(fe

6、nce),此題中的最短路算法本質(zhì)上也可以看做是以f(i)的值從小到大劃分階段的動態(tài)規(guī)劃，因為f(i)只能由比f(i)的值小的狀態(tài)f(j)推出。,小結(jié),在上面一道題中，我們通過分析問題，減少狀態(tài)總數(shù)，成功的解決了此題 下面我們來看一個通過減少決策總數(shù)來優(yōu)化動態(tài)規(guī)劃的例子,序列劃分,給出一個正整數(shù)序列，a1,a2,aN，將序列分成若干段，每段有一個權(quán)值，如將ai,aj劃分成一段，則該段權(quán)值F=(a(i)+a(i+1)+a(j)*i+T，求一種劃分方案，使得每段的權(quán)值之和最小 數(shù)據(jù)范圍：1=N=1000000,序列劃分,我們可以很容易的得到一個O(N2)的動態(tài)規(guī)劃 設(shè)狀態(tài)為fi,表示序列a1,a2,

7、ai的最優(yōu)劃分方案中每段的權(quán)值之和 狀態(tài)轉(zhuǎn)移方程為fi=min(sumi-sumk)*i+t+fk,其中sumi=a1+a2+ai 但是此題中N的范圍可以達到1000000，需要優(yōu)化算法,序列劃分,對于狀態(tài)fi的兩種決策k1,k2(k1k2)，我們來分析一下決策k1優(yōu)于k2的條件 決策k1優(yōu)于k2等價于 (sumi-sumk1)*i+T+fk1(sumi-sumk2)*i+T+fk2 將上式變形后得 i(fk2-fk1)/(sumk2-sumk1),序列劃分,我們設(shè)g(k1,k2)=(fk2-fk1)/(sumk2-sumk1),(k1i,序列劃分,對于任意三個決策k1g(k2,k3) 情況一

8、：如果g(k2,k3)i，則有g(shù)(k1,k2)i，決策k1優(yōu)于決策k2 所以決策k2無論如何都不可能成為最優(yōu)決策,序列劃分,對于任意兩個決策k1,k2(k1i，有g(shù)(k1,k2)j，即k1在以后的計算中也不可能成為最優(yōu)決策,序列劃分,我們用一個隊列k來維護所有可能成為最優(yōu)決策的決策 k1k2k3kn，那么k1,k2,kn應(yīng)該滿足：ig(k1,k2)g(k2,k3)g(kn-1,kn) 我們在計算fi的過程中維護此隊列，則計算fi時的最優(yōu)決策即為k1,如何維護隊列,（1）加入一個新決策k：如果g(kn-1,kn)g(kn,k)，則kn為無用決策，將kn從隊列中刪除，如此反復(fù)直到滿足g(kn-1,kn)g(kn,k)，將k插入隊列尾部 （2）刪除決策：如果g(k1,k2)i，