版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、IOI2000集訓(xùn)隊論文動態(tài)規(guī)劃的特點及其應(yīng)用張辰第1頁共30頁動態(tài)規(guī)劃的特點及其應(yīng)用安徽張辰目錄(點擊進入)【關(guān)鍵詞】【摘要】【正文】1動態(tài)規(guī)劃的本質(zhì)1.1多階段決策問題1.2階段與狀態(tài)1.3決策和策略1.4最優(yōu)化原理與無后效性1.5最優(yōu)指標(biāo)函數(shù)和規(guī)劃方程2動態(tài)規(guī)劃的設(shè)計與實現(xiàn)2.1動態(tài)規(guī)劃的多樣性2.2動態(tài)規(guī)劃的模式性2.3動態(tài)規(guī)劃的技巧性3動態(tài)規(guī)劃與一些算法的比較3.1動態(tài)規(guī)劃與遞推3.2動態(tài)規(guī)劃與搜索3.3動態(tài)規(guī)劃與網(wǎng)絡(luò)流4結(jié)語
2、【附錄:部分試題與源程序】1.“花店櫥窗布置問題”試題2.“釘子與小球”試題3.例2“花店櫥窗布置問題”方法1的源程序4.例2“花店櫥窗布置問題”方法2的源程序5.例3“街道問題”的擴展6.例4“mod4最優(yōu)路徑問題”的源程序7.例5“釘子與小球”的源程序8.例6的源程序“N個人的街道問題”【參考文獻】IOI2000集訓(xùn)隊論文動態(tài)規(guī)劃的特點及其應(yīng)用張辰第3頁共30頁[例1]多段圖中的最短路徑問題:在下圖中找出從A1到D1的最短路徑。仔細
3、觀察這個圖不難發(fā)現(xiàn),它有一個特點。我們將圖中的點分為四類(圖中的A、B、C、D),那么圖中所有的邊都處于相鄰的兩類點之間,并且都從前一類點指向后一類點。這樣,圖中的邊就被分成了三類(A?B、B?C、C?D)。我們需要從每一類中選出一條邊來,組成從A1到D1的一條路徑,并且這條路徑是所有這樣的路徑中的最短者。從上面的這個例子中,我們可以大概地了解到什么是多階段決策問題。更精確的定義如下:多階段決策過程,是指這樣的一類特殊的活動過程,問題可
4、以按時間順序分解成若干相互聯(lián)系的階段,在每一個階段都要做出決策,全部過程的決策是一個決策序列[1]。要使整個活動的總體效果達到最優(yōu)的問題,稱為多階段決策問題多階段決策問題。從上述的定義中,我們可以明顯地看出,這類問題有兩個要素。一個是階段,一個是決策。1.2階段與狀態(tài)階段:階段:將所給問題的過程,按時間或空間特征分解成若干相互聯(lián)系的階段,以便按次序去求每階段的解。常用字母k表示階段變量。[1]階段是問題的屬性。多階段決策問題中通常存在著
5、若干個階段,如上面的例子,就有A、B、C、D這四個階段。在一般情況下,階段是和時間有關(guān)的;但是在很多問題(我的感覺,特別是信息學(xué)問題)中,階段和時間是無關(guān)的。從階段的定義中,可以看出階段的兩個特點,一是“相互聯(lián)系”,二是“次序”。階段之間是怎樣相互聯(lián)系的?就是通過狀態(tài)和狀態(tài)轉(zhuǎn)移。狀態(tài):狀態(tài):各階段開始時的客觀條件叫做狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量,常用sk表示第k階段的狀態(tài)變量,狀態(tài)變量sk的取值集合稱為狀態(tài)集合,用Sk表示。[
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 動態(tài)規(guī)劃方法的matlab實現(xiàn)及其應(yīng)用
- 自適應(yīng)動態(tài)規(guī)劃的研究及其應(yīng)用.pdf
- 近似動態(tài)規(guī)劃方法及其在交通中的應(yīng)用.pdf
- 動態(tài)規(guī)劃研究及其在電力市場動態(tài)分區(qū)定價問題中的應(yīng)用.pdf
- 動態(tài)規(guī)劃算法應(yīng)用及其優(yōu)化---畢業(yè)論文
- 典型水域船舶航路動態(tài)規(guī)劃模型及其應(yīng)用研究.pdf
- 動態(tài)規(guī)劃方法及其在資源分配問題中的應(yīng)用【畢業(yè)論文】
- 動態(tài)規(guī)劃算法應(yīng)用及其在時間效率上的優(yōu)化.pdf
- 遺傳算法的特點及其應(yīng)用
- 應(yīng)用文的特點及其作用
- 遺傳算法的特點及其應(yīng)用
- 職能組織結(jié)構(gòu)的特點及其應(yīng)用
- 迭代動態(tài)規(guī)劃方法及其間歇過程最優(yōu)控制應(yīng)用.pdf
- 基于神經(jīng)網(wǎng)絡(luò)的近似動態(tài)規(guī)劃理論及其應(yīng)用研究.pdf
- 非線性編輯系統(tǒng)的特點及其應(yīng)用
- 慢性腎臟病患者中糖代謝特點及其動態(tài)血糖監(jiān)測應(yīng)用.pdf
- 商務(wù)英語的詞匯特點及其應(yīng)用
- 分析常用模板的類型及其工程應(yīng)用特點
- Spark并行動態(tài)規(guī)劃及其在水庫群發(fā)電優(yōu)化調(diào)度中的應(yīng)用.pdf
- 動態(tài)規(guī)劃
評論
0/150
提交評論