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

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

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

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

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

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

6、nce),此題中的最短路算法本質(zhì)上也可以看做是以f(i)的值從小到大劃分階段的動(dòng)態(tài)規(guī)劃，因?yàn)閒(i)只能由比f(wàn)(i)的值小的狀態(tài)f(j)推出。,小結(jié),在上面一道題中，我們通過(guò)分析問(wèn)題，減少狀態(tài)總數(shù)，成功的解決了此題 下面我們來(lái)看一個(gè)通過(guò)減少?zèng)Q策總數(shù)來(lái)優(yōu)化動(dòng)態(tài)規(guī)劃的例子,序列劃分,給出一個(gè)正整數(shù)序列，a1,a2,aN，將序列分成若干段，每段有一個(gè)權(quán)值，如將ai,aj劃分成一段，則該段權(quán)值F=(a(i)+a(i+1)+a(j)*i+T，求一種劃分方案，使得每段的權(quán)值之和最小 數(shù)據(jù)范圍：1=N=1000000,序列劃分,我們可以很容易的得到一個(gè)O(N2)的動(dòng)態(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的范圍可以達(dá)到1000000，需要優(yōu)化算法,序列劃分,對(duì)于狀態(tài)fi的兩種決策k1,k2(k1k2)，我們來(lái)分析一下決策k1優(yōu)于k2的條件 決策k1優(yōu)于k2等價(jià)于 (sumi-sumk1)*i+T+fk1(sumi-sumk2)*i+T+fk2 將上式變形后得 i(fk2-fk1)/(sumk2-sumk1),序列劃分,我們?cè)O(shè)g(k1,k2)=(fk2-fk1)/(sumk2-sumk1),(k1i,序列劃分,對(duì)于任意三個(gè)決策k1g(k2,k3) 情況一

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