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

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

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

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

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

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

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

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

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

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

·每一集合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個階段（除s和t外）進行某種決策的過程：從s開始，第i次決策決定Vi+1(1≤i≤k-2)中的哪個結(jié)點在從s到t的最短路徑上。最優(yōu)性原理對多段圖問題成立假設(shè)s,v2,v3,…,vk-1,t是一條由s到t的最短路徑。

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

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

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

則，其余的決策：v3,...,vk-1相對于v2將構(gòu)成一個最優(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)

目標函數(shù)：

約束條件：

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

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

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

狀態(tài)(state)表示每個階段開始時過程所處的自然狀況。它應(yīng)該能夠描述過程的特征并且具有無后向性，即當某階段的狀態(tài)給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)，即每個狀態(tài)都是過去歷史的一個完整總結(jié)。通常還要求狀態(tài)是直接或間接可以觀測的。描述狀態(tài)的變量稱狀態(tài)變量(statevariable)。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用xk表示第k階段的狀態(tài)變量，它可以是一個數(shù)或一個向量。用Xk表示第k階段的允許狀態(tài)集合。狀態(tài)變量簡稱為狀態(tài)2024/4/223）決策當一個階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策(decision)。描述決策的變量稱決策變量(decisionvariable)。變量允許取值的范圍稱允許決策集合(setofadmissibledecisions)。用uk(xk)表示第k階段處于狀態(tài)xk時的決策變量，它是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開始到終止狀態(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)}。對于每一個階段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)指標函數(shù)和最優(yōu)值函數(shù)指標函數(shù)(objectivefunction)是衡量過程優(yōu)劣的數(shù)量指標，它是關(guān)于策略的數(shù)量函數(shù)，從階段k到階段n的指標函數(shù)用Vk,n(xk,pk,n(xk))表示，k=1,2,...,n。能夠用動態(tài)規(guī)劃解決的問題的指標函數(shù)應(yīng)具有可分離性，即Vk,n可表為xk,uk,Vk+1,n

的函數(shù)，記為：2024/4/227.最優(yōu)策略和最優(yōu)軌線使指標函數(shù)Vk,n達到最優(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)系式。從最后一個階段，逐步向前遞推求出各階段的決策值。決策序列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}

●對于某個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是其中的一個中間點，則s,v2,v3,…,vi和vi,…,vk-1,t分別是由s到vi和vi到t的最短路徑（最優(yōu)性原理）從Vi中的結(jié)點ji到t的最短路徑將是：

min({|∈Vi+1,1≤ji+1≤pi+1})2024/4/222）向后處理法列出根據(jù)x1,…,xi-1的最優(yōu)決策序列求取xi決策值的關(guān)系式。從第一個階段，逐步向后遞推求出各階段的決策值。決策序列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是其中的一個中間點，則s,v2,v3,…,vi和vi,…,vk-1,t分別是由s到vi和vi到t的最短路徑（最優(yōu)性原理）從s到Vi中的結(jié)點ji的最短路徑將是：

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

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

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

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

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

1)向前遞推式

2)遞推過程

★第k-1段

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

∞★j∈VK-2計算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é)點的編號規(guī)則源點s編號為1,然后依次對V2、V3…Vk-1中的結(jié)點編號，匯點t編號為n。目的：使對COST和D的計算僅按n-1,n-2,…,1的次序計算即可，無需考慮標示結(jié)點所在段的第一個下標?！锼惴枋?024/4/22算法5.1多段圖的向前處理算法

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

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

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

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

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

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

段：1到r之間的段i表示項目i。

結(jié)點：

i=1時，只有一個結(jié)點——源點s=V(1,0)

當2≤i≤r時，每段有n+1個結(jié)點，每個結(jié)點具有形式

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

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

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

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

N(i,l-j),表示給項目i分配l-j個資源所可能獲得的凈利。★當j≤n且i=r時，此時的邊為：<V(r,j),V(r+1,n)>,該邊賦予成本：2024/4/22實例：將4個資源分配給3個項目。構(gòu)成一個4段圖。問題的解：資源的最優(yōu)分配方案是由s到t的一條最大成本的路徑給出——改變邊成本的符號，從而將問題轉(zhuǎn)換成為求取最小成本路徑問題。2024/4/225.3每對結(jié)點之間的最短路徑1.問題描述設(shè)G=(V,E)是一個有n個結(jié)點的有向圖，無負環(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

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

●計算n個結(jié)點的單源最短路徑。

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

●決策什么？

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

i,...,k,…,j

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

i,...,k,…,j

k是編號最高的中間結(jié)點

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

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

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

★

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

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

★

若該路徑不經(jīng)過結(jié)點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é)點經(jīng)過n結(jié)點2024/4/22

對任意的k，k≥1，有，

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

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

初值：

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

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

procedureALL-PATHS(COST,A,n)//COST(n,n)是n結(jié)點圖的成本鄰接矩陣；A(i,j)是結(jié)點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)對A0賦初值//repeatrepeatfork←1tondofori←1tondoforj←1tondo

A

(i,j)←min{A

(i,j)，A

(i,k)+A

(k,j)}repeatrepeatrepeatendALL-PATHS2024/4/22算法的設(shè)計說明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)}∴在算法的計算過程中取消了A的上標，并保證了每次計算的

Ak(i,j)即為

min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)}2）如何求每對結(jié)點之間的路徑？2024/4/22例5.8有向圖如圖所示A012310411260233∞0A11231041126023370A2123104626023370A3123104625023370642113v1v2v312310411260233∞0求圖中所有結(jié)點間的最短路徑矩陣A：注：A(i,j)=∞表明G中從i到j(luò)沒有有向路徑2024/4/22性能分析計算時間＝注：該時間與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。因此，對于成本鄰接矩陣中的∞用一個大于(n-1)*M的值代替。如果在算法結(jié)束時，A(I,j)>(n-1)*M，則表明G中沒有由i到j(luò)的有向路徑。2024/4/224.4最優(yōu)二分檢索樹1.問題的描述1）二分檢索樹定義二分檢索樹Ｔ是一棵二元樹，它或者為空，或者其每個結(jié)點含有一個可以比較大小的數(shù)據(jù)元素，且有：

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

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

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

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

對于一個給定的標識符集合，可能有若干棵不同的二分檢索樹:不同形態(tài)的二分檢索樹對標識符的檢索性能是不同的。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)：最壞情況下查找標識符loop需要做4次比較；成功檢索平均需要做12/5次比較;圖(b):最壞情況下查找標識符loop/while需要做3次比較；成功檢索平均需要做11/5次比較②查找概率可以期望不同標識符的檢索頻率是不同的。如

Pfor＞Pwhile＞

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

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

2024/4/22二分檢索樹

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

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

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

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

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

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

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

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

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

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

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

則預(yù)期總的成本公式表示如下：2024/4/22最優(yōu)二分檢索樹問題：求一棵使得預(yù)期成本最小的二分檢索樹例5.9標識符集合（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é)點a1,a2,…,ak-1和外部結(jié)點E0,E1,…,Ek-1將位于根ak的左子樹中，而其余的結(jié)點將位于右子樹中。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ù)期成本——左、右子樹的根處于第一級

●左、右子樹中所有結(jié)點的級數(shù)相對于子樹的根測定，而相對于原樹的根少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)，則對于最優(yōu)二分檢索樹T有，

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

★首先計算所有j-i=1的C(i,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)造

●在計算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)(概率值“擴大”了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階段的計算：

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)計算結(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-i=m時，有n-m+1個C(i,j)要計算

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

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

Ｏ(nm-m2)

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

procedureOBST(P,Q,n)//給定n個標識符a1＜a2＜…＜an。已知成功檢索的概率P(i),不成功檢索概率Q(i),0≤i≤n。算法對于標識符ai+1,…,aj計算最優(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//含有一個結(jié)點的最優(yōu)樹//(W(n,n),R(n,n),C(n,n))←(Q(n),0,0)form←2tondo//找有m個結(jié)點的最優(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算法的計算時間:Ｏ(n2)2024/4/221.問題描述

1)KNAP(1,j,X)

目標函數(shù)：

約束條件：

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

最優(yōu)性原理對于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}

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

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

遞推過程：

★初始值

0X≥0f0=

－∞X＜0

★求出所有可能的X對應(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

遞推計算過程－∞ 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計算過程（圖解）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個單位，然后上移pi個單位而得到；●fi(X)曲線的構(gòu)造：由fi-1(X)

和fi-1(X-wi)+pi的曲線按X相同時取大值的規(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個階躍值，分別對應(yīng)r個(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ī)則）。注