動態(tài)規(guī)劃入門(論文)(編輯修改稿)
2024-08-30 00:55 本頁面
【文章內(nèi)容簡介】 也就是說,在當(dāng)前狀態(tài) s≤x 1 下,問題的最優(yōu)解 Y 所包含的子問題(序列 X 1 )的解(序列 Y 1 ).D(i)=1 (i=n或者xi=min{xi……Xn})Max{D(j)+1} (ji且j=n且xj=xi)根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)推出狀態(tài)轉(zhuǎn)移方程：設(shè) D(i) 為第 i 枚導(dǎo)彈被攔截之后,這套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù)(包含被攔截的第 i 枚).我們可以設(shè)想,當(dāng)系統(tǒng)攔截了第 k 枚導(dǎo)彈 x k ,而 x k 又是序列 X={xk ,…,xn } 中的最小值,即第 k 枚導(dǎo)彈之后飛來的導(dǎo)彈高度都比它高,則有 D(k)=1 。當(dāng)系統(tǒng)攔截了最后一枚導(dǎo)彈 x n ,那么,系統(tǒng)最多也只能攔截這一枚導(dǎo)彈了,即 D(n)=1 。其它情況下,也應(yīng)該有 D(i)≥1 .根據(jù)以上分析,可歸納出問題的動態(tài)規(guī)劃遞歸方程為:假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為 dmax (即問題的最優(yōu)值),則dmax ( i 為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號)所以,要計算問題的最優(yōu)值 dmax ,需要分別計算出 D(1) , D(2) ,…… D(n) 的值,然后將它們進(jìn)行比較,：dmax=max{D(i)}(1=i且i=n)分析子問題重疊，解決冗余根據(jù)上面分析出來的遞歸方程,我們完全可以設(shè)計一個遞歸函數(shù),采用自頂向下的方法計算 D(i) ,對 i 從 1 到 n 分別調(diào)用這個遞歸函數(shù),就可以計算出 D(1) , D(2) ,…… D(n) .程序如下：int D(int i){ int j,max=0。if((i==n)||(min(x,i,n)==x[i]))//min(x,i,n) 返回數(shù)組x在下標(biāo)i—n之間的最小值 return 1。 else { for(j=i+1。j=n。j++) if(x[j]=x[i]) if(D(j)+1max) max=D(j)+1。 return max。 } }從這個程序的遞歸模型中可以看出， D(1) 的時候,可能需要先計算 D(5) 的值。之后在分別調(diào)用遞歸函數(shù)計算 D(2) , D(3) , D(4) 的時候,都有可能需要先計算 D(5) ,在整個問題的求解過程中, D(5) 可能會被重復(fù)計算很多次,從而造成了冗余,降低了程序的效率.其實,通過以上分析,我們已經(jīng)知道: D(n)=1 .如果將 n 作為階段對問題進(jìn)行劃分,根據(jù)問題的動態(tài)規(guī)劃遞歸方程,我們可以采用自底向上的方法依次計算出 D(n1) , D(n2) ,…… D(1) ,每個 D(i) 的值只計算一次,并在計算的同時把計算結(jié)果保存下來,程序如下：void D(){ int i,j。for( i=1。i=n。i++) d(i)=1 for(i=n1。i=1。i) for(j=i+1。j=n。j++) if (x(j)=x(i) amp。amp。 d(i)=d(j)+1dmax) {dmax=d(i)。 x
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1