本文關(guān)鍵詞：動態(tài)規(guī)劃算法時間效率優(yōu)化策略研究

  更多相關(guān)文章： 動態(tài)規(guī)劃 時間效率優(yōu)化 狀態(tài) 狀態(tài)轉(zhuǎn)移

【摘要】：二十世紀(jì)五十年代,美國數(shù)學(xué)家理查德貝爾曼(R.E.Bellman)根據(jù)一類多階段決策優(yōu)化問題的特點(diǎn),提出了最優(yōu)化原理即無論問題的初始狀態(tài)如何,問題以后的決策相對于初始狀態(tài)都是最優(yōu)策略,最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)。動態(tài)規(guī)劃的基本思想就是將待求解的問題劃分成若干子問題,通過將子問題逐一解決從而解決整個問題。動態(tài)規(guī)劃思想可以有效地解決一類多階段決策優(yōu)化問題。動態(tài)規(guī)劃是一種算法設(shè)計思想。在過去的五十多年里,動態(tài)規(guī)劃在各個領(lǐng)域中得到了廣泛的應(yīng)用。例如最短路徑、項(xiàng)目群資源優(yōu)化、資產(chǎn)的投資決策、字符串匹配、設(shè)備更新、地圖導(dǎo)航、水資源的調(diào)度分配等問題。在適用的情況下,動態(tài)規(guī)劃可以高效率地解決一類動態(tài)決策問題,因此,無論是在理論還是在實(shí)踐上對動態(tài)規(guī)劃算法的研究都具有重要的意義。本文主要研究了動態(tài)規(guī)劃的理論基礎(chǔ),及其時間效率優(yōu)化等幾個方面的內(nèi)容。具體包括:(1)從動態(tài)規(guī)劃算法的基礎(chǔ)理論入手,概述了動態(tài)規(guī)劃中的術(shù)語,如階段、狀態(tài)、多階段決策、指標(biāo)函數(shù)、狀態(tài)的無后效、重疊子結(jié)構(gòu)等一些專有名詞,并歸納了動態(tài)規(guī)劃中常見的子問題模型。探討了動態(tài)規(guī)劃與常見算法的比較,通過與其它算法的比較凸顯了動態(tài)規(guī)劃在解決實(shí)際問題時空間消耗大,全局最優(yōu)以及時間效率高等特點(diǎn)。(2)探究動態(tài)規(guī)劃在時間效率上的優(yōu)化�，F(xiàn)有的研究一般針對具體問題的特點(diǎn)設(shè)計優(yōu)化措施,當(dāng)問題不同時,相應(yīng)的優(yōu)化措施就失去作用。論文從影響動態(tài)規(guī)劃算法時間復(fù)雜度的因素出發(fā),從影響其時間效率的三大方面:問題中需要計算的狀態(tài)個數(shù)、狀態(tài)轉(zhuǎn)移時涉及的狀態(tài)數(shù)、狀態(tài)轉(zhuǎn)移的時間進(jìn)行優(yōu)化。優(yōu)化時實(shí)現(xiàn)三者的平衡,從而在整體上提升算法的時間效率,使其能夠適用于數(shù)據(jù)規(guī)模更大的問題。(3)為了驗(yàn)證動態(tài)規(guī)劃算法時間效率優(yōu)化措施的有效性,將動態(tài)規(guī)劃方法運(yùn)用于經(jīng)典的組合優(yōu)化難題——背包問題。首先分析了解決0/1背包問題和完全背包問題的經(jīng)典動態(tài)規(guī)劃算法;接著利用動態(tài)規(guī)劃的優(yōu)化措施改進(jìn)原有的動態(tài)規(guī)劃算法;然后通過實(shí)驗(yàn)得出不同動態(tài)規(guī)劃算法在解決背包問題時的時間效率。實(shí)驗(yàn)結(jié)果表明本文提出的改進(jìn)算法在一定程度上降低了時間復(fù)雜度。
【關(guān)鍵詞】：動態(tài)規(guī)劃 時間效率優(yōu)化 狀態(tài) 狀態(tài)轉(zhuǎn)移
【學(xué)位授予單位】：中南民族大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O221.3
【目錄】：

• 摘要7-8
• Abstract8-10
• 第1章 緒論10-14
• 1.1 選題的背景與研究的意義10-11
• 1.2 國內(nèi)外研究現(xiàn)狀11-12
• 1.3 本文的研究內(nèi)容12
• 1.4 本文的組織安排12-14
• 第2章 動態(tài)規(guī)劃算法思想14-25
• 2.1 動態(tài)規(guī)劃算法的本質(zhì)14-20
• 2.1.1 多階段決策問題14-15
• 2.1.2 動態(tài)規(guī)劃算法的術(shù)語15-16
• 2.1.3 動態(tài)規(guī)劃算法適用的條件16-19
• 2.1.4 動態(tài)規(guī)劃算法設(shè)計的模式性19
• 2.1.5 常見的子問題模型19-20
• 2.2 動態(tài)規(guī)劃與其它算法的比較20-23
• 2.2.1 動態(tài)規(guī)劃與分治的比較20-21
• 2.2.2 動態(tài)規(guī)劃與貪心的比較21-22
• 2.2.3 動態(tài)規(guī)劃與搜索的比較22-23
• 2.3 本章小結(jié)23-25
• 第3章 動態(tài)規(guī)劃算法在時間效率上的優(yōu)化25-36
• 3.1 動態(tài)規(guī)劃算法在時間復(fù)雜度上優(yōu)化的必要性25
• 3.2 動態(tài)規(guī)劃算法的時間效率分析25-26
• 3.3 狀態(tài)總數(shù)的優(yōu)化26-27
• 3.3.1 雙向動態(tài)規(guī)劃26-27
• 3.3.2 改進(jìn)狀態(tài)的表示27
• 3.4 每次狀態(tài)轉(zhuǎn)移所涉及的狀態(tài)數(shù)的優(yōu)化27-34
• 3.4.1 四邊形不等式與決策量的優(yōu)化27-30
• 3.4.2 合理組織已求解的狀態(tài)30-32
• 3.4.3 運(yùn)用貪心思想優(yōu)化動態(tài)規(guī)劃算法32-34
• 3.5 狀態(tài)轉(zhuǎn)移時間的優(yōu)化34-35
• 3.6 本章小結(jié)35-36
• 第4章 動態(tài)規(guī)劃優(yōu)化措施在背包問題中的應(yīng)用研究36-55
• 4.1 0/1 背包問題36-45
• 4.1.1 問題描述36
• 4.1.2 問題的動態(tài)規(guī)劃算法36-38
• 4.1.3 動態(tài)規(guī)劃算法改進(jìn)38-41
• 4.1.4 實(shí)驗(yàn)與分析41-45
• 4.2 完全背包問題45-54
• 4.2.1 問題描述45
• 4.2.2 問題的動態(tài)規(guī)劃算法設(shè)計45-46
• 4.2.3 動態(tài)規(guī)劃算法改進(jìn)46-49
• 4.2.4 實(shí)驗(yàn)與分析49-54
• 4.3 本章小結(jié)54-55
• 第5章 總結(jié)與展望55-57
• 5.1 總結(jié)55
• 5.2 展望55-57
• 參考文獻(xiàn)57-60
• 致謝60-61
• 附錄A 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文61

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 李菲;肖洪祥;;基于神經(jīng)動態(tài)規(guī)劃算法的最優(yōu)路徑選擇[J];桂林工學(xué)院學(xué)報;2009年01期

2 羅宗俊;;高維0-1瓶頸問題的動態(tài)規(guī)劃算法[J];數(shù)值計算與計算機(jī)應(yīng)用;2013年01期

3 周靜;;運(yùn)用動態(tài)規(guī)劃算法解決最大價值路線圖問題[J];硅谷;2013年15期

4 李樂園;林詒勛;;電力網(wǎng)調(diào)度時間表問題的動態(tài)規(guī)劃算法[J];河南科學(xué);1988年02期

5 徐緒松;工序問題的動態(tài)規(guī)劃算法[J];武漢大學(xué)學(xué)報(自然科學(xué)版);1994年05期

6 趙鈺;徐濤;陳紅軍;;炮兵營火力分配的二階動態(tài)規(guī)劃算法[J];四川兵工學(xué)報;2009年09期

7 陳捷;;基于動態(tài)規(guī)劃算法的最值問題分析[J];電腦與信息技術(shù);2013年06期

8 廖慧芬;邵小兵;;動態(tài)規(guī)劃算法的原理及應(yīng)用[J];中國科技信息;2005年21期

9 劉瑩;;改進(jìn)的動態(tài)規(guī)劃算法在最優(yōu)航線選擇中的應(yīng)用[J];邵陽學(xué)院學(xué)報(自然科學(xué)版);2007年01期

10 王雪瑞;秦勤;李建;;Possible Winner問題參數(shù)算法研究及核心化[J];湘潭大學(xué)自然科學(xué)學(xué)報;2012年04期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 顧文彬;高梅國;;基于改進(jìn)動態(tài)規(guī)劃算法的雷達(dá)微弱目標(biāo)檢測[A];中國航空學(xué)會信號與信息處理專業(yè)全國第八屆學(xué)術(shù)會議論文集[C];2004年

2 唐玲娜;唐雪飛;葉昌偉;;動態(tài)規(guī)劃算法正序?qū)崿F(xiàn)及其改進(jìn)[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（二）[C];2008年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 PALADIN;動態(tài)規(guī)劃算法設(shè)計[N];電腦報;2003年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 許虎;基于動態(tài)規(guī)劃算法的網(wǎng)癮戒除輔助活動規(guī)劃系統(tǒng)的研究與實(shí)現(xiàn)[D];東北大學(xué);2013年

2 劉昭;基于DP算法插電式柴電混合動力汽車控制策略研究[D];重慶交通大學(xué);2015年

3 李強(qiáng);動態(tài)規(guī)劃算法時間效率優(yōu)化策略研究[D];中南民族大學(xué);2015年

4 丁偉軍;結(jié)合近似動態(tài)規(guī)劃算法的串行生產(chǎn)系統(tǒng)風(fēng)險管理研究[D];清華大學(xué);2011年

5 張玉斌;迭代動態(tài)規(guī)劃算法及并行化研究[D];中國石油大學(xué);2008年

6 吳濤;動態(tài)規(guī)劃算法應(yīng)用及其在時間效率上的優(yōu)化[D];南京理工大學(xué);2008年

7 李前興;工業(yè)過程迭代動態(tài)規(guī)劃算法研究[D];浙江大學(xué);2011年

8 農(nóng)健恒;同尺寸物品裝箱的動態(tài)規(guī)劃算法[D];廣西大學(xué);2014年

9 杜君;MPP環(huán)境中面向動態(tài)規(guī)劃算法的混合并行系統(tǒng)的研究[D];天津大學(xué);2014年

10 楊再新;高頻雷達(dá)運(yùn)動目標(biāo)多幀檢測技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2014年

，

本文編號：703041