資源描述：
《動態(tài)規(guī)劃算法和貪心算法的比較與分析》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、動態(tài)規(guī)劃算法和貪心算法的比較與分析1、最優(yōu)化原理根據(jù)一類多階段問題的特點(diǎn),把多階段決策問題變換為一系列互相聯(lián)系的單階段問題,然后逐個加以解決。解決這類問題的最優(yōu)化原理:一個過程的最優(yōu)決策具有這樣的性質(zhì),即無論其初始狀態(tài)和初始決策如何,其今后諸策略對以第一個決策所形成的狀態(tài)作為初始狀態(tài)的過程而言,必須構(gòu)成最優(yōu)策略。簡而言之,一個最優(yōu)策略的子策略,對于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。2、動態(tài)規(guī)劃2.1動態(tài)規(guī)劃算法動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個分支，與其說它是一種算法，不如說它是一種思維方法更貼切。因?yàn)閯討B(tài)規(guī)劃沒有固定的框架，即便是應(yīng)用到同一道題上，也可以建立多種形式的求解算法。許
2、多隱式圖上的算法，例如求單源最短路徑的Dijkstra算法、廣度優(yōu)先搜索算法，都滲透著動態(tài)規(guī)劃的思想。還有許多數(shù)學(xué)問題，表面上看起來與動態(tài)規(guī)劃風(fēng)馬牛不相及，但是其求解思想與動態(tài)規(guī)劃是完全一致的。因此，動態(tài)規(guī)劃不像深度或廣度優(yōu)先那樣可以提供一套模式，需要的時候，取來就可以使用。它必須對具體問題進(jìn)行具體分析、處理，需要豐富的想象力去建立模型，需要創(chuàng)造性的思想去求解。動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。值得注意的是，用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨(dú)立的。最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)。
3、任何一個問題，如果失去了這個最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。能采用動態(tài)規(guī)劃求解的問題都要滿足兩個條件:①問題中的狀態(tài)必須滿足最優(yōu)化原理;②問題中的狀態(tài)必須滿足無后效性。所謂無后效性是指下一時刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無關(guān)，當(dāng)前的狀態(tài)是對以往決策的總結(jié)。2.2動態(tài)規(guī)劃算法的基本要素(1)最優(yōu)子結(jié)構(gòu)。設(shè)計動態(tài)規(guī)劃算法的第一步通常是刻畫最優(yōu)解的結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)提供了該問題可用動態(tài)規(guī)劃算法求解的重要線索。在動態(tài)規(guī)劃算法中，利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式
4、遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。(2)重疊子問題。在用遞歸方法自頂向下求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時只是簡單地用常數(shù)時間查看一下結(jié)果。2.3動態(tài)規(guī)劃適于解決的問題適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。(1)狀態(tài)必須滿足最優(yōu)化原理。作為整個過程的最優(yōu)策略具有如下性質(zhì):無論過去的狀態(tài)和決策如何，對前面的決策所形成的當(dāng)前狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?？梢酝ㄋ椎乩斫鉃樽訂栴}的局部最優(yōu)將
5、導(dǎo)致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，非最優(yōu)解對問題的求解沒有影響。(2)狀態(tài)必須滿足無后效性。所謂無后效性是指:“過去的決策只能通過當(dāng)前狀態(tài)影響未來的發(fā)展，當(dāng)前的狀態(tài)是對以往決策的總結(jié)”。它說明動態(tài)規(guī)劃適于解決當(dāng)前決策和過去狀態(tài)無關(guān)的問題。狀態(tài)出現(xiàn)在策略的任何一個位置，它的地位都是相同的，都可以實(shí)施同樣的決策，這就是無后效性的內(nèi)涵。2.4問題求解模式動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一
6、條活動路線(通常是求最優(yōu)的活動路線)。如下所示:初始狀態(tài)→決策1→決策2→決策n→結(jié)束狀態(tài)動態(tài)規(guī)劃的設(shè)計有一定的模式，一般要經(jīng)歷以下4個步驟:(1)劃分階段。按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。(2)確定狀態(tài)和狀態(tài)變量。將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程。因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出
7、。但事實(shí)上常常是反過來做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來確定決策。(4)尋找邊界條件。給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。用動態(tài)規(guī)劃算法解決一個問題關(guān)鍵就是確定以上4個步驟。3、貪心算法3.1貪心算法的定義貪心算法是一種改進(jìn)的分級處理方法。用貪心法設(shè)計算法的特點(diǎn)是一步一步地進(jìn)行,根據(jù)某個優(yōu)化測度,每一步都要保證能獲得局部最優(yōu)解。每步只考慮一個數(shù)據(jù),它的選取應(yīng)滿足局部優(yōu)化條件。若下一個數(shù)據(jù)與部分最優(yōu)解連在一起不再是可行解時,就不把該數(shù)據(jù)添加到部分解中,直到把所有數(shù)據(jù)枚舉完，或不能再添加為止。這種能夠得到某種度量意義下的最優(yōu)
