動(dòng)態(tài)規(guī)劃模型建立與優(yōu)化方法ppt課件.ppt

《動(dòng)態(tài)規(guī)劃模型建立與優(yōu)化方法ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、動(dòng)態(tài)規(guī)劃(三)模型構(gòu)建與優(yōu)化方法動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。動(dòng)態(tài)規(guī)劃活躍在各種信息學(xué)競(jìng)賽，是因?yàn)槠鋸?qiáng)大的實(shí)用性，可擴(kuò)展性。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑、一種方法、一中思維方式，而不是一種明確算法。動(dòng)態(tài)規(guī)劃的核心——記憶化動(dòng)態(tài)規(guī)劃算法通過(guò)將待求解的問(wèn)題分解成若干個(gè)相互聯(lián)系的子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解的方法得到原問(wèn)題的解。對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到的時(shí)候?qū)λM(jìn)行求解，并把答案保存起來(lái)，讓以后再次遇到時(shí)直接引用答案，不必重新求解。例題一最長(zhǎng)非降子序列問(wèn)題。給

2、你一字排開(kāi)的n個(gè)數(shù)，按從左往右的順序選擇m個(gè)滿足這m個(gè)數(shù)保持非降。用F[i]表示以第i個(gè)數(shù)結(jié)尾的序列最長(zhǎng)能有多長(zhǎng)。F[i]:=max(F[j])+1;j

3、X[i]個(gè)石子，兩人輪流從中取出石子，規(guī)定每次只能從最左邊或最右邊取出一堆石子，直至石子被全部取出，每個(gè)人所取的石子的總個(gè)數(shù)為個(gè)人的最后得分，得分多的人獲勝。若兩人得分相同，則規(guī)定首先取的人獲勝。如果游戲開(kāi)始時(shí)N為偶數(shù)，則對(duì)首先取的人來(lái)說(shuō)，存在一種必勝的策略。請(qǐng)你編一個(gè)程序，作為首先取石子的人，尋找一種必勝的策略和計(jì)算機(jī)玩這個(gè)游戲，并讓你自己保持不敗。分析對(duì)于這道題，第一感覺(jué)便是貪心，但貪心存在反例：6,10,4,5。便也只能采用動(dòng)態(tài)規(guī)劃的方法。因?yàn)镹是偶數(shù)，所以可將問(wèn)題劃分成N/2個(gè)階段，第i個(gè)階段處理所有相鄰的2i堆石

4、子，相當(dāng)于雙方的第N/2-i+1個(gè)回合。對(duì)每一種狀態(tài)，作出取左邊還是取右邊的決策，同時(shí)，還需要考慮計(jì)算機(jī)作出決策后，人也要作出相應(yīng)的最佳決策?？雌饋?lái)對(duì)于人的兩種決策，似乎有些難以考慮，但只要將人作出最佳決策轉(zhuǎn)化為計(jì)算機(jī)作出較差決策，問(wèn)題便迎刃而解。分析設(shè)b[i,j]表示第i到第j堆石子中，計(jì)算機(jī)最多可獲得的得分，且總堆數(shù)j-i+1為偶數(shù)動(dòng)態(tài)轉(zhuǎn)移方程為：b[i,j]=max(a[i]+min(b[i+2,j],b[i+1,j-1]),a[j]+min(b[i,j-2],b[i+1,j-1]))初始條件為？序列壓縮給出一個(gè)N個(gè)

5、正整數(shù)的序列A=[A1,A2,……,AN],我們可以對(duì)其進(jìn)行壓縮操作.所謂壓縮操作是指:將兩個(gè)相鄰的元素AI和AI+1的差(AI-AI+1)去替代第I個(gè)元素,同時(shí)刪去第I+1個(gè)元素,嚴(yán)格地可以定義如下:CON(A,I)=[A1,,A2,….,AI-1,AI-AI+1,AI+2,…….AN]經(jīng)過(guò)一次序列壓縮之后,我們可以得到一個(gè)N-1個(gè)元素的序列,如此進(jìn)行下去,我們可以僅得到單一的一個(gè)整數(shù)?，F(xiàn)給定一個(gè)正整數(shù)序列和一個(gè)目標(biāo)整數(shù)T，求解并輸出壓縮順序。1〈=N〈=100，-10000〈=T〈=10000示例：con（[12，10

6、，4，3，5]，2）=[12，6，3，5]con（[12，6，3，5]，3）=[12，6，-2]con（[12，6，-2]，2）=[12，8]con（[12，8]，1）=[4]算法一看了題目最容易想到動(dòng)態(tài)規(guī)劃算法是石子合并問(wèn)題與骨牌問(wèn)題相結(jié)合的方法。其算法如下：設(shè)F[I，J，K]表示將第I個(gè)數(shù)到第J個(gè)數(shù)按規(guī)則壓縮，最后能否壓縮成數(shù)K。不難得出動(dòng)態(tài)轉(zhuǎn)移方程為：F[I,J,K]=Falseor(F[I,M,K1]andF[M+1,J,K1-K])其中I<=M

7、RUE如果F[1，N，T]的值為真，該問(wèn)題有解，否則無(wú)解。至于求具體方案，可以用一個(gè)父結(jié)點(diǎn)數(shù)組記下推出F[I，J，K]的M、K1值。也可在最后用一個(gè)反向的動(dòng)態(tài)規(guī)劃找最優(yōu)方案。從上面的動(dòng)態(tài)規(guī)劃方程可以看出，該算法在最壞的情況下時(shí)間復(fù)雜度將接近于10000^2*100^3，由于最后要輸出最優(yōu)方案，不可用滾動(dòng)數(shù)組，因此它的空間復(fù)雜度為o(10000*100^2)，無(wú)論從時(shí)間還是空間上來(lái)看，該算法都不適合于該問(wèn)題。算法二只要仔細(xì)分析問(wèn)題不難看出，該問(wèn)題是要我們?cè)谳斎氲牡?至第N-1個(gè)數(shù)前面加減號(hào)，并且在這個(gè)式子中添入N-1個(gè)括號(hào)，

8、使得式子最終的計(jì)算結(jié)果為給定的數(shù)T。我們不妨將所有的括號(hào)都拆掉，最后該式子將會(huì)成為一個(gè)沒(méi)有括號(hào)的加減式。注意：只要稍加分析即可發(fā)現(xiàn)，該加減式的第二個(gè)數(shù)前面肯定是減號(hào)。反過(guò)來(lái)考慮，如果一個(gè)加減式的第二個(gè)數(shù)前面為減號(hào)，其余的數(shù)前面為“+”號(hào)或“-”號(hào)（第一個(gè)前面沒(méi)有符號(hào)），那么該式子能否變?yōu)橐粋€(gè)由N-1個(gè)括