第5章動(dòng)態(tài)規(guī)劃

2024/4/22第5章動(dòng)態(tài)規(guī)劃2024/4/221.多階段決策問題

多階段決策過程：問題的活動(dòng)過程分為若干相互聯(lián)系的階段，任一階段i以后的行為僅依賴于i階段的過程狀態(tài)，而與i階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。在每一個(gè)階段都要做出決策，這一系列的決策稱為多階段決策過程(multistepdecisionprocess)。

最優(yōu)化問題：問題的每一階段可能有多種可供選擇的決策，必須從中選擇一種決策。各階段的決策構(gòu)成一個(gè)決策序列。決策序列不同，所導(dǎo)致的問題的結(jié)果可能不同。

多階段決策的最優(yōu)化問題就是：求能夠獲得問題最優(yōu)解的決策序列——最優(yōu)決策序列。5.1一般方法2024/4/222.多階段決策過程的求解策略1）枚舉法：窮舉可能的決策序列，從中選取可以獲得最優(yōu)解的決策序列2）動(dòng)態(tài)規(guī)劃

20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。應(yīng)用領(lǐng)域：動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。2024/4/223.最優(yōu)性原理(PrincipleofOptimality)

過程的最優(yōu)決策序列具有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。利用動(dòng)態(tài)規(guī)劃求解問題的前提

1)證明問題滿足最優(yōu)性原理如果對(duì)所求解問題證明滿足最優(yōu)性原理，則說明用動(dòng)態(tài)規(guī)劃方法有可能解決該問題

2)獲得問題狀態(tài)的遞推關(guān)系式獲得各階段間的遞推關(guān)系式是解決問題的關(guān)鍵。2024/4/22例5.1[多段圖問題]多段圖G=(V,E)是一個(gè)有向圖，且具有特性:

結(jié)點(diǎn)：結(jié)點(diǎn)集V被分成k≥2個(gè)不相交的集合Vi，1≤i≤k，其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)s(源點(diǎn))和t(匯點(diǎn))

·每一集合Vi定義圖中的一段。

邊：所有的邊(u,v)均具有如下性質(zhì)：若<u,v>∈E，則該邊將是從某段i指向i+1段，即若u∈Vi，則v∈Vi＋1,1≤i≤k－1。

·每條邊(u,v)均附有成本c(u,v)。

s到t的路徑：從第1段開始，至第2段、第3段、…、最后在第k段終止。路徑的成本是這條路徑上邊的成本和。

多段圖問題：求由s到t的最小成本路徑。2024/4/2212345678910111297324227111181456356425V1V2V3V4V55段圖2024/4/22

多段圖問題的多階段決策過程：生成從s到t的最小成本路徑是在k-2個(gè)階段（除s和t外）進(jìn)行某種決策的過程：從s開始，第i次決策決定Vi+1(1≤i≤k-2)中的哪個(gè)結(jié)點(diǎn)在從s到t的最短路徑上。最優(yōu)性原理對(duì)多段圖問題成立假設(shè)s,v2,v3,…,vk-1,t是一條由s到t的最短路徑。

●初始狀態(tài)：s

●初始決策：(s,v2)，v2∈V2

●初始決策產(chǎn)生的狀態(tài)：v2

則，其余的決策：v3,...,vk-1相對(duì)于v2將構(gòu)成一個(gè)最優(yōu)決策序列——最優(yōu)性原理成立。

反證：若不然，設(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)性原理成立2024/4/22例5.2[0/1背包問題]KNAP(l,j,X)

目標(biāo)函數(shù)：

約束條件：

0/1背包問題：KNAP(1,n,M)

2024/4/22最優(yōu)性原理對(duì)0/1背包問題成立：設(shè)y1,y2,…,yn是x1,x2,…,xn的0/1值最優(yōu)序列。若y1＝0,KNAP(2,n,M)是初始決策產(chǎn)生的狀態(tài)。則y2,…,yn相對(duì)于KNAP(2,n,M)將構(gòu)成一個(gè)最優(yōu)序列。否則，y1,y2,…,yn將不是KNAP(1,n,M)的最優(yōu)解若y1＝1,KNAP(2,n,M－w1)是初始決策產(chǎn)生的狀態(tài)。則y2,…,yn相對(duì)于KNAP(2,n,M－w1)將構(gòu)成一個(gè)最優(yōu)序列。否則，設(shè)存在另一0/1序列z1,z2,…,zn,使得且則序列y1,z2,…,zn將是一個(gè)對(duì)于KNAP(1,n,M)具有更大效益值的序列,與假設(shè)矛盾故，最優(yōu)性原理成立2024/4/224.動(dòng)態(tài)規(guī)劃模型的基本要素一個(gè)多階段決策過程最優(yōu)化問題的動(dòng)態(tài)規(guī)劃模型通常包含以下要素：1)階段

階段(step)是對(duì)整個(gè)過程的自然劃分。通常根據(jù)時(shí)間順序或空間特征來劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用k=1,2,..,n表示。2024/4/222）狀態(tài)

狀態(tài)(state)表示每個(gè)階段開始時(shí)過程所處的自然狀況。它應(yīng)該能夠描述過程的特征并且具有無后向性，即當(dāng)某階段的狀態(tài)給定時(shí)，這個(gè)階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)，即每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。通常還要求狀態(tài)是直接或間接可以觀測(cè)的。描述狀態(tài)的變量稱狀態(tài)變量(statevariable)。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用xk表示第k階段的狀態(tài)變量，它可以是一個(gè)數(shù)或一個(gè)向量。用Xk表示第k階段的允許狀態(tài)集合。狀態(tài)變量簡稱為狀態(tài)2024/4/223）決策當(dāng)一個(gè)階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個(gè)狀態(tài)，這種選擇手段稱為決策(decision)。描述決策的變量稱決策變量(decisionvariable)。變量允許取值的范圍稱允許決策集合(setofadmissibledecisions)。用uk(xk)表示第k階段處于狀態(tài)xk時(shí)的決策變量，它是xk的函數(shù)，用Uk(xk)表示了xk的允許決策集合。決策變量簡稱決策。2024/4/224）策略決策組成的序列稱為策略(policy)。由初始狀態(tài)x1開始的全過程的策略記作p1,n(x1)，即p1,n(x1)={u1(x1),u2(x2),...，un(xn)}。由第k階段的狀態(tài)xk開始到終止?fàn)顟B(tài)的后部子過程的策略記作pk,n(xk)，即pk,n(xk)={uk(xk),uk+1(xk+1),...，un(xn)}。類似地，由第k到第j階段的子過程的策略記作

pk,j(xk)={uk(xk),uk+1(xk+1),...，uj(xj)}。對(duì)于每一個(gè)階段k的某一給定的狀態(tài)xk，可供選擇的策略pk,j(xk)有一定的范圍，稱為允許策略集合(setofadmissiblepolicies).2024/4/225)狀態(tài)轉(zhuǎn)移方程在確定性過程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程(equationofstate)表示這種演變規(guī)律，寫作2024/4/226)指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)(objectivefunction)是衡量過程優(yōu)劣的數(shù)量指標(biāo)，它是關(guān)于策略的數(shù)量函數(shù)，從階段k到階段n的指標(biāo)函數(shù)用Vk,n(xk,pk,n(xk))表示，k=1,2,...,n。能夠用動(dòng)態(tài)規(guī)劃解決的問題的指標(biāo)函數(shù)應(yīng)具有可分離性，即Vk,n可表為xk,uk,Vk+1,n

的函數(shù)，記為：2024/4/227.最優(yōu)策略和最優(yōu)軌線使指標(biāo)函數(shù)Vk,n達(dá)到最優(yōu)值的策略是從k開始的后部子過程的最優(yōu)策略，記作pk,n*={uk*,..un*},p1,n*又是全過程的最優(yōu)策略，簡稱最優(yōu)策略(optimalpolicy)。從初始狀態(tài)x1(=x1*)出發(fā)，過程按照p1,n*和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列{x1*,x2*,..,xn+1*}稱最優(yōu)軌線(optimaltrajectory)。2024/4/225.遞推策略1）向前處理法列出根據(jù)xi+1,…,xn的最優(yōu)決策序列求取xi決策值的關(guān)系式。從最后一個(gè)階段，逐步向前遞推求出各階段的決策值。決策序列x1,x2,…,xn就是問題的最優(yōu)解。

xn-1,1…xn-1,pn-1xn2024/4/22

例5.3利用向前處理法求解0/1背包問題設(shè)gi(x)是KNAP(i+1,n,X)的最優(yōu)解。

●g0(M)：KNAP(1,n,M)的最優(yōu)解。由于x1的取值等于1或0,可得：

g0(M)=max{g1(M),g1(M-w1)+p1}

●對(duì)于某個(gè)xi，xi等于1或0，則有：

gi(X)=max{gi+1(X),gi+1(X-wi+1)+pi+1}

初始值：

0X≥0gn(X)=-∞X＜02024/4/22

例5.4利用向前處理法求解k段圖問題設(shè)∈V2，1≤j2≤p2,|V2|=p2;

是由到t的最短路徑，則s到t的最短路徑是

{s|∈V2,1≤j2≤p2}中最短的那條路徑。若s,v2,v3,…,vi,…,vk-1,t是s到t的一條最短路徑，vi是其中的一個(gè)中間點(diǎn)，則s,v2,v3,…,vi和vi,…,vk-1,t分別是由s到vi和vi到t的最短路徑（最優(yōu)性原理）從Vi中的結(jié)點(diǎn)ji到t的最短路徑將是：

min({|∈Vi+1,1≤ji+1≤pi+1})2024/4/222）向后處理法列出根據(jù)x1,…,xi-1的最優(yōu)決策序列求取xi決策值的關(guān)系式。從第一個(gè)階段，逐步向后遞推求出各階段的決策值。決策序列x1,x2,…,xn就是問題的最優(yōu)解。

2024/4/22

例5.50/1背包問題（向后處理策略）設(shè)fi(x)是KNAP(1,i,X)的最優(yōu)解。則，fn(M)=KNAP(1,n,M)

向后遞推關(guān)系式：

fi(X)=max{fi-1(X),fi-1(X-wi)+pi}

初始值：

0X≥0f0(X)=-∞X＜02024/4/22

例5.6k段圖問題（向后處理策略）設(shè)∈Vk-1，1≤jk-1≤pk-1，|Vk-1|=pk-1;

是由s到的最短路徑，則s到t的最短路徑是{t|∈Vk-1,1≤jk-1≤pk-1}中最短的那條路徑。若s,v2,v3,…,vi,…,vk-1,t是s到t的一條最短路徑，vi是其中的一個(gè)中間點(diǎn)，則s,v2,v3,…,vi和vi,…,vk-1,t分別是由s到vi和vi到t的最短路徑（最優(yōu)性原理）從s到Vi中的結(jié)點(diǎn)ji的最短路徑將是：

min({|∈Vi,1≤ji≤pi})2024/4/22動(dòng)態(tài)規(guī)劃的基本思想：（1）動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件。要做到這一點(diǎn)，必須將問題的過程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)選擇狀態(tài)變量，決策變量和定義最優(yōu)值函數(shù)，從而把一個(gè)大問題化成一簇同類型的子問題，然后逐個(gè)求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。（2）在多階段決策過程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來各段分開，又把當(dāng)前的效益和未來效益綜合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的。（3）在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)的各段狀態(tài)便可逐次變換得到，從而確定最優(yōu)路線。2024/4/22關(guān)于動(dòng)態(tài)規(guī)劃求解策略的進(jìn)一步說明采用枚舉法：若問題的決策序列由n次決策構(gòu)成，而每次決策有p種選擇，則可能的決策序列將有pn個(gè)。利用動(dòng)態(tài)規(guī)劃策略的求解過程中保存了所有子問題的最優(yōu)解，而舍去了所有不能導(dǎo)致問題最優(yōu)解的次優(yōu)決策序列動(dòng)態(tài)規(guī)劃：可能有多項(xiàng)式的計(jì)算復(fù)雜度。2024/4/22與非線性規(guī)劃相比，動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：（1）易于確定全局最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是一種逐步改善法，它把原問題化為一系列結(jié)構(gòu)相似的最優(yōu)化子問題，而每個(gè)子問題的變量個(gè)數(shù)比原問題少的多，約束集合也要簡單得多。（2）能得到一簇解，有利于分析結(jié)果（3）能利用經(jīng)驗(yàn)，提高求解的效率。動(dòng)態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系，較之非線性規(guī)劃與實(shí)際過程聯(lián)系得更緊密。不足之處：（1）沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)模型可供應(yīng)用。（2）應(yīng)用的局限性。要求狀態(tài)變量滿足“無后效性”條件，不少實(shí)際問題在取其自然特征作為狀態(tài)變量往往不能滿足這條件。（3）在數(shù)值求解中，存在“維數(shù)障礙”。在計(jì)算機(jī)中，每遞推一段，必須把前一段的最優(yōu)值函數(shù)在相應(yīng)的狀態(tài)集合上的全部值存入內(nèi)存中。當(dāng)維數(shù)增大時(shí)，所需的內(nèi)存量成指數(shù)倍增長。2024/4/225.2多段圖問題1.問題的描述

●在多段圖中求從s到t的一條最小成本的路徑，可以看作是在k-2個(gè)段作出某種決策的結(jié)果。

●第i次決策決定Vi+1中的哪個(gè)結(jié)點(diǎn)在這條路徑上，這里1≤i≤k-2；

●最優(yōu)性原理對(duì)多段圖問題成立2024/4/222.向前處理策略求解設(shè)P(i,j)是一條從Vi中的結(jié)點(diǎn)j到匯點(diǎn)t的最小成本路徑，

COST(i,j)是這條路徑的成本。

1)向前遞推式

2)遞推過程

★第k-1段

c(j,t)<j,t>∈ECOST(k-1,j)=

∞★j∈VK-2計(jì)算COST(k-2,j)=min{c(j,l)+cost(k-1,l)}

★COST(1,S)2024/4/22l1l2...lpi+1t…jViVi+12024/4/2212345678910111297324227111181456356425V1V2V3V4V55段圖2024/4/22★各遞推結(jié)果第4段COST(4,9)=c(9,12)=4

COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=5第3段COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7第2段COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=9COST(2,4)=18COST(2,5)=15第1段COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16S到t的最小成本路徑的成本＝162024/4/22★最小路徑的求取記D(i,j)＝每一COST(i,j)的決策即，使c(j,L)+COST(i+1,L)取得最小值的L值。例：D(3,6)=10,D(3,7)=10D(3,8)=10D(2,2)=7,D(2,3)=6,D(2,4)=8,D(2,5)=8D(1,1)=2

根據(jù)D(1,1)的決策值向后遞推求取最小成本路徑：●v2=D(1,1)=2●v3=D(2,D(1,1))=7●v4=D(3,D(2,D(1,1)))=D(3,7)=10

故由s到t的最小成本路徑是：1→2→7→10→122024/4/223)算法描述★結(jié)點(diǎn)的編號(hào)規(guī)則源點(diǎn)s編號(hào)為1,然后依次對(duì)V2、V3…Vk-1中的結(jié)點(diǎn)編號(hào)，匯點(diǎn)t編號(hào)為n。目的：使對(duì)COST和D的計(jì)算僅按n-1,n-2,…,1的次序計(jì)算即可，無需考慮標(biāo)示結(jié)點(diǎn)所在段的第一個(gè)下標(biāo)?！锼惴枋?024/4/22算法5.1多段圖的向前處理算法

procedureFGRAPH(E,k,n,P)//輸入是按段的順序給結(jié)點(diǎn)編號(hào)的，有n個(gè)結(jié)點(diǎn)的k段圖。E是邊集，c(i,j)是邊<i,j>的成本。P(1:k)存儲(chǔ)最小成本路徑//realCOST(n)←0;integerD(n-1),P(k),r,j,k,nforj←n-1to1by-1do//計(jì)算COST(j)//

設(shè)r是具有性質(zhì)：<j,r>∈E且使c(j,r)+COST(r)取最小值的結(jié)點(diǎn)

COST(j)←c(j,r)+COST(r)D(j)←r//記錄決策值//repeatP(1)←1;P(k)←nforj←2tok-1do//找路徑上的第j個(gè)結(jié)點(diǎn)//P(j)←D(P(j-1))//回溯求出該路徑//repeatendFGRAPH2024/4/22算法的時(shí)間復(fù)雜度若G采用鄰接表表示，總計(jì)算時(shí)間為：2024/4/223.向后處理策略求解設(shè)BP(i,j)是一條從源點(diǎn)s到Vi中的結(jié)點(diǎn)j的最小成本路徑，

BCOST(i,j)是這條路徑的成本。

1)向后遞推式

2)遞推過程

★第2段

c(1,j)<1,j>∈EBCOST(2,j)=

∞2024/4/2212345678910111297324227111181456356425V1V2V3V4V55段圖2024/4/22★各遞推結(jié)果第2段BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2第3段BCOST(3,6)=min{BCOST(2,2)+4,BCOST(2,3)+2}=9BCOST(3,7)=min{BCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11}=11BCOST(3,8)=min{BCOST(2,4)+11,BCOST(2,5)+8}=10第4段BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15BCOST(4,10)=min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14BCOST(4,11)=min{BCOST(3,8)+6}=16第5段BCOST(5,12)=min{BCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5}=16S到t的最小成本路徑的成本＝162024/4/22★最小路徑的求取記BD(i,j)＝每一COST(i,j)的決策即，使COST(i-1,l)+c(l,j)取得最小值的l值。例：BD(3,6)=3,BD(3,7)=2,BD(3,8)=5BD(4,9)=6,BD(4,10)=7,BD(4,11)=8BD(5,12)=10

根據(jù)D(5,12)的決策值向前遞推求取最小成本路徑：●v4=BD(5,12)=10●v3=BD(4,BD(5,12))=7●v2=BD(3,BD(4,BD(5,12)))=BD(3,7)=2

故由s到t的最小成本路徑是：1→2→7→10→12

2024/4/2212345678910111297324227111181456356425V1V2V3V4V55段圖2024/4/22算法4.2多段圖的向后處理算法

procedureBGRAPH(E,k,n,P)//輸入是按段的順序給結(jié)點(diǎn)編號(hào)的，有n個(gè)結(jié)點(diǎn)的k段圖。E是邊集，c(i,j)是邊<i,j>的成本。P(1:k)帶出最小成本路徑//realBCOST(n);integerBD(n-1),P(k),r,j,k,n,BCOST(1)←0forj←2tondo//計(jì)算BCOST(j)//

設(shè)r是具有<r,j>∈E且使BCOST(r)+c(r,j)取最小值性質(zhì)的結(jié)點(diǎn)

BCOST(j)←BCOST(r)+c(r,j)BD(j)←r//記錄決策值//repeatP(1)←1;P(k)←nforj←k-1to2by-1do//找路徑上的第j個(gè)結(jié)點(diǎn)//P(j)←D(P(j+1))//回溯求出該路徑//repeatendBGRAPH2024/4/224.多段圖問題的應(yīng)用實(shí)例將n個(gè)資源分配給r個(gè)項(xiàng)目的問題：如果把j個(gè)資源，0≤j≤n，分配給項(xiàng)目i，可以獲得N(i,j)的凈利。問題：如何將這n個(gè)資源分配給r個(gè)項(xiàng)目才能獲得最大可能的凈利。轉(zhuǎn)換成一個(gè)多段圖問題。2024/4/22

用r＋1段圖描述該問題：

段：1到r之間的段i表示項(xiàng)目i。

結(jié)點(diǎn)：

i=1時(shí)，只有一個(gè)結(jié)點(diǎn)——源點(diǎn)s=V(1,0)

當(dāng)2≤i≤r時(shí)，每段有n+1個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)具有形式

V(i,j)：表示到項(xiàng)目i之前為止，共把j個(gè)資源分配給了項(xiàng)目1,2,…,i-1

匯點(diǎn)t=V(r+1,n)

邊的一般形式：<V(i,j),V(i+1,L)>,j≤L,1≤i≤r

成本：★當(dāng)j≤L且1≤i≤r時(shí)，邊<V(i,j),V(i+1,l)>賦予成本

N(i,l-j),表示給項(xiàng)目i分配l-j個(gè)資源所可能獲得的凈利?！锂?dāng)j≤n且i=r時(shí)，此時(shí)的邊為：<V(r,j),V(r+1,n)>,該邊賦予成本：2024/4/22實(shí)例：將4個(gè)資源分配給3個(gè)項(xiàng)目。構(gòu)成一個(gè)4段圖。問題的解：資源的最優(yōu)分配方案是由s到t的一條最大成本的路徑給出——改變邊成本的符號(hào)，從而將問題轉(zhuǎn)換成為求取最小成本路徑問題。2024/4/225.3每對(duì)結(jié)點(diǎn)之間的最短路徑1.問題描述設(shè)G=(V,E)是一個(gè)有n個(gè)結(jié)點(diǎn)的有向圖，無負(fù)環(huán)，C是G的成本鄰接矩陣，C中元素有：

0，i＝j(luò)c(i,j)=邊<i,j>的成本，i≠j且<i,j>∈E(G)∞，i≠j且其中，1≤i，j≤n

每對(duì)結(jié)點(diǎn)之間的最短路徑問題：求滿足下述條件的矩陣A，A中的任一元素A(i,j)代表結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長度。2024/4/22分析：利用單源最短路徑算法求解

●計(jì)算n個(gè)結(jié)點(diǎn)的單源最短路徑。

●時(shí)間復(fù)雜度：Ο(n3)利用動(dòng)態(tài)規(guī)劃策略求解將求解G中每對(duì)結(jié)點(diǎn)之間的最短路徑問題轉(zhuǎn)化成一個(gè)多階段決策過程。

●決策什么？

●最優(yōu)性原理對(duì)于該問題是否成立？2024/4/222.動(dòng)態(tài)規(guī)劃求解策略1）最優(yōu)性原理對(duì)于每對(duì)結(jié)點(diǎn)之間的最短路徑問題成立對(duì)G的一條由i到j(luò)的最短路徑（假設(shè)該路徑中不包含環(huán)），設(shè)k是該路徑上的一個(gè)中間結(jié)點(diǎn)：

i,...,k,…,j

由i到k的最短路徑k是中間結(jié)點(diǎn)由k到i的最短路徑則，由i到k和k到j(luò)的兩條子路徑將分別是由i到k和由k到j(luò)的最短路徑。否則i,...,k,…,j也將不是由i到j(luò)的最短路徑。故，最優(yōu)性原理對(duì)于該問題成立。2024/4/222）多階段決策過程設(shè)k是由i到j(luò)的最短路徑上編號(hào)（假設(shè)所有n個(gè)結(jié)點(diǎn)依次有從1到n的編號(hào)）最高的中間結(jié)點(diǎn)：

i,...,k,…,j

k是編號(hào)最高的中間結(jié)點(diǎn)

則由i到k的子路徑上將不會(huì)有比編號(hào)k-1更大的結(jié)點(diǎn)；同理，由k到i的子路徑上也將不會(huì)有比編號(hào)k-1更大的結(jié)點(diǎn)。構(gòu)造多階段決策過程：對(duì)由i到j(luò)的最短路徑，首先決策哪一個(gè)結(jié)點(diǎn)是該路徑上具有最大編號(hào)的中間結(jié)點(diǎn)k，然后再去求取由i到k和由k到j(luò)的最短路徑——其中應(yīng)不包含比k-1還大的中間結(jié)點(diǎn)。2024/4/223）遞推關(guān)系式記Ak(i,j)表示從i到j(luò)并且不經(jīng)過比k還大的結(jié)點(diǎn)的最短路徑長度。則，

A(i,j)=An(i,j)

即，由i到j(luò)的最短路徑不通過比編號(hào)n還大的結(jié)點(diǎn)。注：該路徑可以經(jīng)過結(jié)點(diǎn)n，也可以不經(jīng)過結(jié)點(diǎn)n。

★

若該路徑經(jīng)過結(jié)點(diǎn)n，則

An(i,j)＝An-1(i,n)+An-1(n,j)

★

若該路徑不經(jīng)過結(jié)點(diǎn)n，則

An(i,j)＝An-1(i,j)

故可得，

An(i,j)=min{An-1(i,j)，An-1(i,n)+An-1(n,j)}

不經(jīng)過n結(jié)點(diǎn)經(jīng)過n結(jié)點(diǎn)2024/4/22

對(duì)任意的k，k≥1，有，

Ak(i,j)=min{Ak-1(i,j)，Ak-1(i,k)+Ak-1(k,j)}

不經(jīng)過結(jié)點(diǎn)k剛好經(jīng)過結(jié)點(diǎn)k

初值：

A0(i,j)=C(i,j)，1≤i≤n，1≤j≤n遞推計(jì)算：A1(i,j),A2(i,j),…,An(i,j)=A

(i,j)2024/4/223.算法描述算法5.3每對(duì)結(jié)點(diǎn)之間的最短路徑長度

procedureALL-PATHS(COST,A,n)//COST(n,n)是n結(jié)點(diǎn)圖的成本鄰接矩陣；A(i,j)是結(jié)點(diǎn)vi到vj的最短路徑的成本；COST(i,i)=0,1≤i≤n//integerI,j,k,n;realCOST(n,n),A(n,n)fori←1tondoforj←1tondoA(i,j)←COST(i,j)//用COST(i,j)對(duì)A0賦初值//repeatrepeatfork←1tondofori←1tondoforj←1tondo

A

(i,j)←min{A

(i,j)，A

(i,k)+A

(k,j)}repeatrepeatrepeatendALL-PATHS2024/4/22算法的設(shè)計(jì)說明1）

∵

⑴Ak(i,k)=Ak-1(i,k)Ak(k,j)=Ak-1(k,j)⑵Ak(i,j)←min{Ak-1(i,j),Ak(i,k)+Ak-1(k,j)}

≡Ak(i,j)←min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)}∴在算法的計(jì)算過程中取消了A的上標(biāo)，并保證了每次計(jì)算的

Ak(i,j)即為

min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)}2）如何求每對(duì)結(jié)點(diǎn)之間的路徑？2024/4/22例5.8有向圖如圖所示A012310411260233∞0A11231041126023370A2123104626023370A3123104625023370642113v1v2v312310411260233∞0求圖中所有結(jié)點(diǎn)間的最短路徑矩陣A：注：A(i,j)=∞表明G中從i到j(luò)沒有有向路徑2024/4/22性能分析計(jì)算時(shí)間＝注：該時(shí)間與A的值無關(guān)：

fork←1tondo迭代n次

fori←1tondo迭代n次

forj←1tondo迭代n次

A(i,j)←min{A(i,j)，A(i,k)+A(k,j)}repeatrepeatrepeat

2024/4/22∞的處理設(shè)M是E中最大成本的一條邊的成本，則An(i,j)<=(n-1)*M。因此，對(duì)于成本鄰接矩陣中的∞用一個(gè)大于(n-1)*M的值代替。如果在算法結(jié)束時(shí)，A(I,j)>(n-1)*M，則表明G中沒有由i到j(luò)的有向路徑。2024/4/224.4最優(yōu)二分檢索樹1.問題的描述1）二分檢索樹定義二分檢索樹Ｔ是一棵二元樹，它或者為空，或者其每個(gè)結(jié)點(diǎn)含有一個(gè)可以比較大小的數(shù)據(jù)元素，且有：

·Ｔ的左子樹的所有元素比根結(jié)點(diǎn)中的元素?。?/p>

·Ｔ的右子樹的所有元素比根結(jié)點(diǎn)中的元素大；

·Ｔ的左子樹和右子樹也是二分檢索樹。注：

·二分檢索樹要求樹中所有結(jié)點(diǎn)的元素值互異2024/4/22ifforwhilerepeatloopifforrepeatloopwhile

對(duì)于一個(gè)給定的標(biāo)識(shí)符集合，可能有若干棵不同的二分檢索樹:不同形態(tài)的二分檢索樹對(duì)標(biāo)識(shí)符的檢索性能是不同的。2024/4/222）二分檢索樹的檢索算法5.4SEARCH(T,X,i)//為X檢索二分檢索樹T，如果X不在T中，則置i=0；否則i有IDENT(i)=X//i←Twhilei≠0docase:X＜IDENT(i):i←LCHILD(i)//若X小于IDENT(i)，則在左子樹中繼續(xù)查找//:X＝IDENT(i):return//X等于IDENT(i)，則返回//:X＞IDENT(i):i←RCHILD(i)//若X大于IDENT(i)，則在右子樹中繼續(xù)查找//endcaserepeatendSEARCH2024/4/22二分檢索樹的性能特征①例圖(a)：最壞情況下查找標(biāo)識(shí)符loop需要做4次比較；成功檢索平均需要做12/5次比較;圖(b):最壞情況下查找標(biāo)識(shí)符loop/while需要做3次比較；成功檢索平均需要做11/5次比較②查找概率可以期望不同標(biāo)識(shí)符的檢索頻率是不同的。如

Pfor＞Pwhile＞

Ploop③不成功檢索可以期望不成功檢索出現(xiàn)的頻率也是不同的。2024/4/22ifforwhilerepeatloopifforrepeatloopwhile2024/4/223）最優(yōu)二分檢索樹問題設(shè)給定的標(biāo)識(shí)符集合是{a1,a2,…,an}，并假定a1＜a2＜…＜an。設(shè)，P(i)是對(duì)ai檢索的概率，Q(i)是正被檢索的標(biāo)識(shí)符X恰好滿足：ai＜

X＜ai+1，0≤i≤n（設(shè)a0=-∞,an+1=+∞)時(shí)的概率，即一種不成功檢索情況下的概率。則表示所有成功檢索的概率表示所有不成功檢索的概率考慮所有可能的成功和不成功檢索情況，共2n+1種可能的情況，有

2024/4/22二分檢索樹

內(nèi)結(jié)點(diǎn)：代表成功檢索情況，剛好有n個(gè)

外結(jié)點(diǎn)：代表不成功檢索情況，剛好有n＋1個(gè)關(guān)于{a1,a2,…,an}的最優(yōu)二分檢索樹含義如下：2024/4/22二分檢索樹的預(yù)期成本

預(yù)期成本：算法對(duì)于所有可能的成功檢索情況和不成功檢索情況，平均所要做的比較次數(shù)。根據(jù)期望值計(jì)算方法，

平均檢索成本＝Σ每種情況出現(xiàn)的概率×該情況下所需的比較次數(shù)平均檢索成本的構(gòu)成：成功檢索成分＋不成功檢索成分

●成功檢索：在l級(jí)內(nèi)結(jié)點(diǎn)終止的成功檢索，需要做l次比較運(yùn)算（基于二分檢索樹結(jié)構(gòu)）。該級(jí)上的任意結(jié)點(diǎn)ai的檢索的成本為：

P(i)*level(ai)；其中，level(ai)=結(jié)點(diǎn)ai

的級(jí)數(shù)=l2024/4/22

●不成功檢索：不成功檢索的等價(jià)類：每種不成功檢索情況定義了一個(gè)等價(jià)類，共有n+1個(gè)等價(jià)類Ei(0≤i≤n)。其中，

E0={X|X＜a1}Ei={X|ai＜X＜ai+1(1≤i＜n)}En={X|X＞an}

若Ei處于l級(jí)，則算法需作l-1次迭代。則，l級(jí)上的外部結(jié)點(diǎn)的不成功檢索的成本分擔(dān)額為：

Q(i)*(level(Ei)-1)

則預(yù)期總的成本公式表示如下：2024/4/22最優(yōu)二分檢索樹問題：求一棵使得預(yù)期成本最小的二分檢索樹例5.9標(biāo)識(shí)符集合（a1,a2,a3）=（do,if,stop）?？赡艿亩謾z索樹如下所示。成功檢索：3種不成功情況：4種2024/4/22stopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e)2024/4/221)等概率：P(i)=Q(i)=1/7cost(a)=15/7cost(b)=13/7

cost(c)=15/7cost(d)=15/7cost(e)=15/72）不等概率：

P(1)=0.5P(2)=0.1P(3)=0.05Q(0)=0.15Q(1)=0.1Q(2)=0.05Q(3)=0.05cost(a)=2.65cost(b)=1.9cost(c)=1.5

cost(d)=2.15cost(e)=1.6ifdostopdostopif(b)(c)最優(yōu)最優(yōu)2024/4/222.多階段決策過程把構(gòu)造二分檢索樹的過程看成一系列決策的結(jié)果。決策的策略：決策樹根，如果{a1,a2,…,an}存在一棵二分檢索樹，ak是該樹的根，則內(nèi)結(jié)點(diǎn)a1,a2,…,ak-1和外部結(jié)點(diǎn)E0,E1,…,Ek-1將位于根ak的左子樹中，而其余的結(jié)點(diǎn)將位于右子樹中。ak由ak＋1,ak+2,…,an及Ek,Ek+1,…,En構(gòu)成的二分檢索樹由a1,a2,…,ak-1及E0,E1,…,Ek-1構(gòu)成的二分檢索樹2024/4/22定義：含義：

●左、右子樹的預(yù)期成本——左、右子樹的根處于第一級(jí)

●左、右子樹中所有結(jié)點(diǎn)的級(jí)數(shù)相對(duì)于子樹的根測(cè)定，而相對(duì)于原樹的根少12024/4/22記：則，原二分檢索樹的預(yù)期成本可表示為：

COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)

最優(yōu)二分檢索樹：COST(T)有最小值最優(yōu)性原理成立若T最優(yōu)二分檢索樹，則COST(L)和COST(R)將分別是包含a1,a2,…,ak-1和E0,E1,…,Ek-1、及ak＋1,ak+2,…,an和Ek,Ek+1,…,En的最優(yōu)二分檢索(子)樹。記由ai+1,ai+2,…,aj和Ei,Ei+!,…,Ej構(gòu)成的二分檢索樹的成本為C(i,j)，則對(duì)于最優(yōu)二分檢索樹T有，

COST(L)=C(0,k-1)COST(R)=C(k,n)2024/4/22則，對(duì)任何C(i,j)有，向前遞推過程：

★首先計(jì)算所有j-i=1的C(i,j)

★然后依次計(jì)算j-i=2,3,…,n的C(i,j)。

★C(0,n)=最優(yōu)二分檢索樹的成本。

初始值

C(i,i)=0W(i,i)=Q(i)，0≤i≤n2024/4/22最優(yōu)二分檢索樹的構(gòu)造

●在計(jì)算C(i,j)的過程中，記下使之取得最小值的k值，即樹Tij的根，記為R(i,j)。

●依據(jù)R(0,n)…，推導(dǎo)樹的形態(tài)例４.10設(shè)n=4,且(a1,a2,a3,a4)=(do,if,read,while)。設(shè)P(1:4)=(3,3,1,1)，Q(0:4)=(2,3,1,1,1)(概率值“擴(kuò)大”了16倍)初始：W(i,i)=Q(i)C(i,i)=0R(i,i)=0且有，W(i,j)=P(j)+Q(j)+W(i,j-1)2024/4/22且有，W(i,j)=P(j)+Q(j)+W(i,j-1)j-i=1階段的計(jì)算：

W(0,1)=P(1)+Q(1)+W(0,0)=8C(0,1)=W(0,1)+min{C(0,0)+C(1,1)}=8R(0,1)=1W(1,2)=P(2)+Q(2)+W(1,1)=7C(1,2)=W(1,2)+min{C(1,1)+C(2,2)}=7R(1,2)=2W(2,3)=P(3)+Q(3)+W(2,2)=3C(2,3)=W(2,3)+min{C(2,2)+C(3,3)}=3R(2,3)=3W(3,4)=P(4)+Q(4)+W(3,3)=3C(3,4)=W(3,4)+min{C(3,3)+C(4,4)}=3R(3,4)=4①②③④2024/4/22j-i=2w(0,2)=p(2)+q(2)+w(0,1)=12c(0,2)=w(0,2)+min{c(0,1)+c(2,2),c(0,0)+c(1,2)}=19r(0,2)=1w(1,3)=p(3)+q(3)+w(1,2)=9c(1,3)=w(1,3)+min{c(1,1)+c(2,3),c(1,2)+c(3,3)}=12r(1,3)=2w(2,4)=p(4)+q(4)+w(2,3)=5c(2,4)=w(1,4)+min{c(2,2)+c(3,4),c(2,3)+c(4,4)}=8r(2,4)=3/4且有，W(i,j)=P(j)+Q(j)+W(i,j-1)2024/4/22j-i=3w(0,3)=P(3)+q(3)+w(0,2)=14c(0,3)=w(0,3)+min{c(0,0)+c(1,3),c(0,1)+c(2,3),c(0,2)+c(3,3)}=25r(0,3)=2w(1,4)=P(4)+q(4)+w(1,3)=11c(1,4)=w(1,4)+min{c(1,1)+c(2,4),c(1,2)+c(3,4),c(1,3)+c(4,4)}=19r(1,4)=2j-i=4w(0,4)=P(4)+q(4)+w(0,3)=16c(0,4)=w(0,4)+min{c(0,0)+c(1,4),c(0,1)+c(2,4),c(0,2)+c(3,4),c(0,3)+c(4,4)}=32r(0,4)=22024/4/22C(i,j),W(i,j),R(i,j)計(jì)算結(jié)果則，C(0,4)=32二分檢索樹：

T04=2=>T01(左子樹），T24(右子樹）

T01=1=>T00(左子樹），T11(右子樹）

T24=3=>T22(左子樹），T34(右子樹）0123402,0,03,0,01,0,01,0,01,0,018,8,17,7,23,3,33,3,4212,19,19,12,25,8,3314,25,211,19,2416,32,2W(j,j+i),C(j,j+i),R(j,j+i)2024/4/22樹的形態(tài)ifdoreadwhile2024/4/223.計(jì)算時(shí)間

●當(dāng)j-i=m時(shí)，有n-m+1個(gè)C(i,j)要計(jì)算

●C(i,j)的計(jì)算：Ｏ(m)

每個(gè)C(i,j)要求找出m個(gè)量中的最小值。則，n-m+1個(gè)C(i,j)的計(jì)算時(shí)間：

Ｏ(nm-m2)

對(duì)所有可能的m，總計(jì)算時(shí)間為：一種改進(jìn)措施（克努特）：最優(yōu)的k∈[R(i,j-1),R(i+1,j)]2024/4/224.算法描述

procedureOBST(P,Q,n)//給定n個(gè)標(biāo)識(shí)符a1＜a2＜…＜an。已知成功檢索的概率P(i),不成功檢索概率Q(i),0≤i≤n。算法對(duì)于標(biāo)識(shí)符ai+1,…,aj計(jì)算最優(yōu)二分檢索樹Tij的成本C(i,j)、根R(i,j)、權(quán)W(i,j)//realP(1:n),Q(1:n),C(0:n,0:n),W(0:n,0:n);integerR(0:n,0:n)fori←0ton-1do(W(i,i),R(i,i),C(i,i))←(Q(i),0,0)//置初值//(W(i,i+1),R(i,i+1),C(i,i+1))←(Q(i)+Q(i+1)+P(i+1),i+1,Q(i)+Q(i+1)+P(i+1))repeat//含有一個(gè)結(jié)點(diǎn)的最優(yōu)樹//(W(n,n),R(n,n),C(n,n))←(Q(n),0,0)form←2tondo//找有m個(gè)結(jié)點(diǎn)的最優(yōu)樹//fori←0ton-mdoj←i+mW(i,j)←W(i,j-1)+P(j)+Q(j)k←區(qū)間[R(i,j-1),R(i+1,j)]中使{C(i,l-1)+C(l,j)}取最小值的l值//Knuth結(jié)論

C(i,j)←W(i,j)+C(i,k-1)+C(k,j)R(i,j)←krepeatrepeatendOBST2024/4/22OBST算法的計(jì)算時(shí)間:Ｏ(n2)2024/4/221.問題描述

1)KNAP(1,j,X)

目標(biāo)函數(shù)：

約束條件：

0/1背包問題：KNAP(1,n,M)

最優(yōu)性原理對(duì)于0/1背包問題成立求解策略：向前遞推、向后遞推

4.50/1背包問題2024/4/222)向后遞推關(guān)系式記fj(X)是KNAP(1,j,X)的最優(yōu)解，則fn(M)有

fn(M)=max{fn-1(M),fn-1(M-wn)+pn}

對(duì)于任意的fi(X)，i＞0,有

fi(X)=max{fi-1(X),fi-1(X-wi)+pi}

遞推過程：

★初始值

0X≥0f0=

－∞X＜0

★求出所有可能的X對(duì)應(yīng)的fi值。

★

fn(M)=KNAP(1,n,M)2024/4/22例4.11背包問題

n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6

遞推計(jì)算過程－∞ X＜0f0(X)=0 X≥0

－∞ X＜0f1(X)=max{0,－∞+1}=0 0≤X＜2max{0,0+1}=1 X≥2

－∞ X＜00 0≤X＜2f2(X)=1 2≤X＜3max{1,0+2}=23≤X＜5max{1,1+2}=3X≥5

f3(M)=max{3,1+5}=6fi(X)=max{fi-1(X),fi-1(X-wi)+pi}2024/4/22解向量的推導(dǎo)

f3(M)=6x3=1

ΔP=6-p3=1X=(1,0,1)

ΔM=6-w3=2

f2(ΔM)=1x2=0f1(ΔM)=1x1=1

2024/4/22f1,f2,f3計(jì)算過程（圖解）i:fi-1(x-wi)+pii=0:函數(shù)不存在1234567012i＝1:f0(x-w1)+p1x1234567012i＝2:f1(x-w2)+p23x1234567012f1(x)x1234567012f0(x)=0x12345670123xf2(x)2024/4/2212345670678x1234589i＝3:f2(x-w3)+p312345670678x1234589f3(x)10注：●fi-1(X-wi)+pi曲線的構(gòu)造：將fi-1(X)的曲線在X軸上右移wi個(gè)單位，然后上移pi個(gè)單位而得到；●fi(X)曲線的構(gòu)造：由fi-1(X)

和fi-1(X-wi)+pi的曲線按X相同時(shí)取大值的規(guī)則歸并而成2024/4/222.序偶表示記fi的序偶集合為

Si={(Pj,Wj)|Wj是fi曲線中使得fi產(chǎn)生一次階躍的X值，0≤j＜r}即Pj=fi(Wj)

●(P0,W0)=(0,0)●共有r個(gè)階躍值，分別對(duì)應(yīng)r個(gè)(Pj,Wj)序偶，1≤j≤r●若Wj＜Wj+1,則Pj＜Pj+1，0≤j＜r●若Wj≤X＜Wj+1，fi(X)=fi(Wj)●若X≥Wr，fi(X)=fi(Wr)2024/4/22●Si的構(gòu)造記是fi-1(X-wi)+pi的所有序偶的集合，則其中，Si-1是fi-1的所有序偶的集合

Si的構(gòu)造：由Si-1和按照支配規(guī)則合并而成。

支配規(guī)則：如果Si-1和之一有序偶(Pj,Wj),另一有(Pk,Wk)，且有Wj≥Wk,Pj≤Pk，

則序偶(Pj,Wj)將被舍棄。（即取最大值規(guī)則）。注