資源描述：
《算法分析與設(shè)計(jì)第4章ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、一、適用條件多階段決策過程實(shí)際問題中,常有這樣一類活動(dòng),它們的活動(dòng)過程可以分為若干個(gè)階段，而且在任一階段i后的行為都依賴于i階段的過程狀態(tài)，而與i階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。當(dāng)各個(gè)階段決策確定后，就組成了一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線。這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)的具有鏈狀結(jié)構(gòu)的多階段過程被稱為多階段決策過程.滿足最優(yōu)性原理第四章動(dòng)態(tài)規(guī)劃4．1方法概述狀態(tài)0決策1決策2……決策n狀態(tài)n狀態(tài)1狀態(tài)n-1狀態(tài)2最優(yōu)性原理：過程的最優(yōu)決策序列具有如下性質(zhì)：無論過程的初始狀態(tài)和
2、初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。如果所求解問題的最優(yōu)性原理成立，則說明用動(dòng)態(tài)規(guī)劃方法有可能解決該問題。因?yàn)橹挥袧M足最優(yōu)性原理，才能使用各階段的遞推公式求解。二、最優(yōu)性原理在多階段決策過程的每一階段，都可能有多種可供選擇的決策，但必須從中選取一種決策。一旦各個(gè)階段的決策選定之后，就構(gòu)成了解決這一問題的一個(gè)決策序列，決策序列不同，所導(dǎo)致的問題的結(jié)果也不同。動(dòng)態(tài)規(guī)劃的目標(biāo)就是要在所有容許選擇的決策序列中選取一個(gè)會(huì)獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。三、動(dòng)態(tài)規(guī)劃
3、方法的關(guān)鍵關(guān)鍵在于獲取各階段間的遞推關(guān)系式。四、可解決的問題最短路徑問題、設(shè)備更新問題、資源分配問題、貨物裝運(yùn)排序、生產(chǎn)計(jì)劃等。五、應(yīng)用實(shí)例分析例4.1[多段圖問題]多段圖G=（V，E）是一個(gè)有向圖。它具有如下特性：圖中的結(jié)點(diǎn)被劃分成k≥2個(gè)不相交的集合Vi,1≤i≤k，其中V1和Vk分別有一個(gè)結(jié)點(diǎn)s（源點(diǎn)）和t（匯點(diǎn)）。圖中所有的邊(u,v)均具有如下性質(zhì)：若u∈Vi，則v∈Vi+1，1≤i＜k-1,且每條邊(u,v)均附有成本c(u,v)。從s到t的一條路徑成本是這條路徑上邊的成本和。多段圖問題是求由s
4、到t的最小成本路徑。每個(gè)集合Vi定義圖中的一段。由于E的約束，每條從s到t的路徑都是從第1段開始，在第k段終止。圖4.1所示的就是一個(gè)5段圖。123456789101112ts97322271111815435642546對(duì)于每一條由s到t的路徑，可以把它看成在k-2個(gè)階段中作出的某個(gè)決策序列的相應(yīng)結(jié)果。第i次決策就是確定Vi+1中的哪個(gè)結(jié)點(diǎn)在這條路徑上，1≤i≤k-2。下面證明最優(yōu)性原理對(duì)多段圖成立。假設(shè)s,v2,v3,…,vk-1,t是一條由s到t的最短路徑，還假定從源點(diǎn)s（初始狀態(tài)）開始，已作出了到結(jié)
5、點(diǎn)v2的決策（初始決策），因此v2就是初始決策所產(chǎn)生的狀態(tài)。如果把v2看成是原問題的一個(gè)子問題的初始狀態(tài)，解這個(gè)子問題就是找出一條由v2到t的最短路徑。這條最短路徑顯然是v2,v3,…,vk-1,t，如若不然，設(shè)v2,q3,…,qk-1,t是一條由v2到t的更短路徑，則s,v2,q3,…,qk-1,t是一條比路徑s,v2,v3,…,vk-1,t更短的由s到t的路徑。與假設(shè)矛盾，故最優(yōu)性原理成立。因此它為使用動(dòng)態(tài)規(guī)劃方法來解決多段圖問題提供了可能。六、動(dòng)態(tài)規(guī)劃方法的形式化描述能用動(dòng)態(tài)規(guī)劃求解的問題的最優(yōu)化決策
6、序列可表示如下。設(shè)S0是問題的初始狀態(tài)。假定需要作n次決策xi,1≤i≤n。設(shè)X1={r1,1,r1,2,…,r1,p1}是X1的可能決策值的集合，而S1,1是在選取決策值r1,j1以后所產(chǎn)生的狀態(tài),1≤j1≤p1。又設(shè)是相應(yīng)于狀態(tài)S1,j1的最優(yōu)決策序列。那末，相應(yīng)于S0的最優(yōu)決策序列就是{
7、1≤j1≤p1}中最優(yōu)的序列，記為OPT{}=。如果已作了k-1次決策，1≤k-1＜n。設(shè)x1,…,xk-1的最優(yōu)決策值是r1,…,rk-1，它們所產(chǎn)生的狀態(tài)為S1,…,Sk-1。又設(shè)是xk的可能值的集合。是選取決策
8、值后所產(chǎn)生的狀態(tài)，1≤jk≤pk。是相應(yīng)于的最優(yōu)決策序列。因此，相應(yīng)于Sk-1的最優(yōu)決策序列是。于是相應(yīng)于S0的最優(yōu)決策序列為r1,…,rk-1，rk，。七、兩種求解方法（1）向前處理法：從最后階段開始，以逐步向前遞推的方式列出求前一階段決策值的遞推關(guān)系式，即根據(jù)xi+1,…,xn的那些最優(yōu)決策序列來列出求取xi決策值的關(guān)系式，即：xi=f(xi+1,xi+2,…,xn)例子：在k段圖問題中，設(shè)又設(shè)是由到t的最短路徑，則s到t的最短路徑是中最短的那條路徑。若設(shè)是s到t的一條最短路徑，是路徑上的中間結(jié)點(diǎn)，則就
9、應(yīng)分別是由s到vi和由vi到t的最短路徑。（2）向后處理法：根據(jù)x1,…,xi-1的那些最優(yōu)決策序列列出求xi的遞推關(guān)系式。即：xi=f(x1,x2,…,xi-1).下例是說明向前處理法在多段圖中的使用見黑板小結(jié)：無論是使用向前處理法還是使用向后處理法，都將所有子問題的最優(yōu)解保存下來。這樣做的目的是為了便于逐步遞推得到原問題的最優(yōu)解并避免對(duì)它們的重復(fù)計(jì)算。由枚舉法可知，不同決策序列的總數(shù)就其所取決策值而言是指數(shù)級(jí)
