動態(tài)規(guī)劃入門(論文)-文庫吧資料
2024-08-16 00:55本頁面
【正文】 =n=30，1=m=30）。兩種傳球的方法被視作不同的方法，當(dāng)且僅當(dāng)這兩種方法中，接到球的同學(xué)按接球順序組成的序列是不同的。游戲規(guī)則是這樣的：n個同學(xué)站成一個圓圈，其中的一個同學(xué)手里拿著一個球，當(dāng)老師吹哨子時開始傳球，每個同學(xué)可以把球傳給自己左右的兩個同學(xué)中的一個（左右任意），當(dāng)老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學(xué)就是敗者，要給大家表演一個節(jié)目。例2：傳球游戲（NOIP2008普及組第三題）【問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。} }由此我們出了最大攔截數(shù)的第一枚導(dǎo)彈的順序號 xh，即d(xh)為問題的解從而避免了有些子問題被重復(fù)計算的情況發(fā)生,提高了程序的效率.在實際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段反而麻煩。 d(i)=d(j)+1dmax) {dmax=d(i)。j++) if (x(j)=x(i) amp。i) for(j=i+1。i++) d(i)=1 for(i=n1。for( i=1。 } }從這個程序的遞歸模型中可以看出， D(1) 的時候,可能需要先計算 D(5) 的值。j++) if(x[j]=x[i]) if(D(j)+1max) max=D(j)+1。 else { for(j=i+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) 的值,然后將它們進行比較,：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。在當(dāng)前狀態(tài)下,序列 Y 1 ={y 2 ,…,y k } 也應(yīng)該是序列 X 1 ={x 2 ,…,x n } 的最長非遞增子序列(用反證法很容易證明).也就是說,在當(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 。下面通過對具體實例的分析
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1