算法 第四章 動態(tài)規(guī)劃

第四章動態(tài)規(guī)劃9/22/20231第四章動態(tài)規(guī)劃4.1一般方法1.多階段決策問題

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

過程的最優(yōu)決策序列具有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。對于一個多階段過程問題，上述最優(yōu)決策是否存在依賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。而能否采用動態(tài)規(guī)劃的方法還要看該問題的子問題是否具有重疊性質(zhì)。問題的子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素。子問題重疊性質(zhì):在求解具有最優(yōu)子結(jié)構(gòu)的問題時，每次產(chǎn)生的子問題并不總是新問題，有些問題被反復(fù)計算多次。

9/22/20234利用動態(tài)規(guī)劃求解問題的前提

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

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

結(jié)點：結(jié)點集V被分成k≥2個不相交的集合Vi，1≤i≤k，其中V1和Vk分別只有一個結(jié)點s(源結(jié)點)和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的最小成本路徑。9/22/2023612345678910111297324227111181456356425V1V2V3V4V55段圖9/22/20237

多段圖問題的多階段決策過程：生成從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)性原理成立9/22/20238例4.2[0/1背包問題]KNAP(1,j,X)

目標函數(shù)：

約束條件：

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

9/22/20239最優(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序列z2,z3,…,zn,使得且則序列y1,z2,…,zn將是一個對于KNAP(1,n,M)具有更大效益值得序列。故，最優(yōu)性原理成立9/22/2023104.動態(tài)規(guī)劃模型的基本要素一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素：1)階段

階段(step)是對整個過程的自然劃分。通常根據(jù)時間順序或空間特征來劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用k=1,2,..,n表示。9/22/2023112）狀態(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)9/22/2023123）決策當一個階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策(decision)。描述決策的變量稱決策變量(decisionvariable)。變量允許取值的范圍稱允許決策集合(setofadmissibledecisions)。用uk(xk)表示第k階段處于狀態(tài)xk時的決策變量，它是xk的函數(shù)，用Uk(xk)表示了xk的允許決策集合。決策變量簡稱決策。9/22/2023134）策略

決策組成的序列稱為策略(policy)。由初始狀態(tài)x1開始的全過程的策略記作p1n(x1)，即p1n(x1)={u1(x1),u2(x2),...，un(xn)}。由第k階段的狀態(tài)xk開始到終止狀態(tài)的后部子過程的策略記作pkn(xk)，即pkn(xk)={uk(xk),uk+1(xk+1),...，un(xn)}。類似地，由第k到第j階段的子過程的策略記作pkj(xk)={uk(xk),uk+1(xk+1),...，uj(xj)}。對于每一個階段k的某一給定的狀態(tài)xk，可供選擇的策略pkj(xk)有一定的范圍，稱為允許策略集合(setofadmissiblepolicies)，用P1n(x1),Pkn(xk),Pkj(xk)表示。9/22/2023145)狀態(tài)轉(zhuǎn)移方程在確定性過程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程(equationofstate)表示這種演變規(guī)律，寫作9/22/2023156)指標函數(shù)和最優(yōu)值函數(shù)指標函數(shù)(objectivefunction)是衡量過程優(yōu)劣的數(shù)量指標，它是關(guān)于策略的數(shù)量函數(shù)，從階段k到階段n的指標函數(shù)用Vkn(xk,pkn(xk))表示，k=1,2,...,n。能夠用動態(tài)規(guī)劃解決的問題的指標函數(shù)應(yīng)具有可分離性，即Vkn可表為xk,uk,Vk+1n的函數(shù)，記為：9/22/2023167.最優(yōu)策略和最優(yōu)軌線使指標函數(shù)Vkn達到最優(yōu)值的策略是從k開始的后部子過程的最優(yōu)策略，記作pkn*={uk*,..un*},p1n*又是全過程的最優(yōu)策略，簡稱最優(yōu)策略(optimalpolicy)。從初始狀態(tài)x1(=x1*)出發(fā)，過程按照p1n*和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列{x1*,x2*,..,xn+1*}稱最優(yōu)軌線(optimaltrajectory)。9/22/2023174.最優(yōu)決策序列的表示設(shè)

●S0：問題的初始狀態(tài)

●n次決策：問題需要做n次決策●xi：i階段的決策值，1≤i≤n。設(shè)X1={r1,1,r1,2,…,r1,p1}是x1可能的決策值的集合，S1,j1是在選擇決策值r1,j1之后所產(chǎn)生的狀態(tài)——初始決策所產(chǎn)生的狀態(tài)。設(shè)Γ1,j1是相應(yīng)于狀態(tài)S1,j1的最優(yōu)決策序列。則，相應(yīng)于S0的最優(yōu)決策序列就是{r1,j1Γ1,j1|1≤j1≤p1}中最優(yōu)的序列，記為

9/22/202318s0r1,1r1,2...r1,p1snΓ1,j19/22/202319

若已經(jīng)做了k-1次決策，1≤k-1＜n，設(shè)x1,x2,…,xk-1的最優(yōu)決策值是r1,r2,…,rk-1，所產(chǎn)生的狀態(tài)依次為S1,S2,…,Sk-1。設(shè)Xk={rk,1,rk,2,…,rk,pk}是xk可能的決策值的集合，Sk,jk是在選擇決策值rk,jk之后所產(chǎn)生的狀態(tài),1≤jk≤pk。Γk,jk是相應(yīng)于狀態(tài)Sk,jk的最優(yōu)決策序列。則，相應(yīng)于Sk-1的最優(yōu)決策序列是

相應(yīng)于S0的最優(yōu)決策序列為r1,…,rk-1，rk,Γk9/22/2023205.遞推策略1）向前處理法列出根據(jù)xi+1,…,xn的最優(yōu)決策序列求取xi決策值的關(guān)系式。從最后一個階段，逐步向前遞推求出各階段的決策值。決策序列x1,x2,…,xn就是問題的最優(yōu)解。

xn-1,1…xn-1,pn-1xn9/22/202321

例4.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＜09/22/202322

例4.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})9/22/2023232）向后處理法列出根據(jù)x1,…,xi-1的最優(yōu)決策序列求取xi決策值的關(guān)系式。從第一個階段，逐步向后遞推求出各階段的決策值。決策序列x1,x2,…,xn就是問題的最優(yōu)解。

9/22/202324

例4.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＜09/22/202325

例4.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,1≤ji+1≤pi+1})9/22/202326關(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ù)雜度。9/22/2023274.2多段圖問題1.問題的描述

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

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

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

i表示Vi，j表示Vi中的結(jié)點號2)遞推過程

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

∞

9/22/202329l1l2...lpi+1t…jViVi+19/22/20233012345678910111297324227111181456356425V1V2V3V4V55段圖9/22/202331★各遞推結(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的最小成本路徑的成本＝169/22/202332★最小路徑的求取記D(i,j)＝每一COST(i,j)的決策即，使c(j,l)+COST(i+1,l)取得最小值的l值。例：D(3,6)=10,D(3,7)=10，D(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→12

9/22/2023333)算法描述★結(jié)點的編號規(guī)則源點s編號為1,然后依次對V2、V3…Vk-1中的結(jié)點編號，匯點t編號為n。目的：使對COST和D的計算僅按n-1,n-2,…,1的次序計算即可，無需考慮標示結(jié)點所在段的第一個下標?！锼惴枋?/22/202334算法4.1多段圖的向前處理算法procedureFGRAPH(E,k,n,P)//輸入是按段的順序給結(jié)點編號的，有n個結(jié)點的k段圖。E是邊集，c(i,j)是邊<i,j>的成本。P(1:k)是最小成本路徑//realCOST(n);integerD(n-1),P(k),r,j,k,nCOST(n)←0forj←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))//回溯求出該路徑//repeatendFGRAPH9/22/202335算法的時間復(fù)雜度若G采用鄰接表表示，總計算時間為：9/22/2023363.向后處理策略求解

設(shè)BP(i,j)是一條從源點s到Vi中的結(jié)點j的最小成本路徑，BCOST(i,j)是這條路徑的成本。

1)向后遞推式

2)遞推過程

★第2段c(1,j)<1,j>∈ECOST(2,j)=

∞9/22/20233712345678910111297324227111181456356425V1V2V3V4V55段圖9/22/202338★各遞推結(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的最小成本路徑的成本＝169/22/202339★最小路徑的求取記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

9/22/202340算法4.2多段圖的向后處理算法procedureBGRAPH(E,k,n,P)//輸入是按段的順序給結(jié)點編號的，有n個結(jié)點的k段圖。E是邊集，c(i,j)是邊<i,j>的成本。P(1:k)是最小成本路徑//realBCOST(n);integerD(n-1),P(k),r,j,k,nBCOST(1)←0forj←2tondo//計算BCOST(j)//設(shè)r是具有<r,j>∈E且使BCOST(r)+c(r,j)取最小值性質(zhì)的結(jié)點BCOST(j)←BCOST(r)+c(r,j)D(j)←r//記錄決策值//repeat//找一條最小成本路徑//P(1)←1;P(k)←nforj←k-1to2by-1do//找路徑上的第j個結(jié)點//P(j)←D(P(j+1))//回溯求出該路徑//repeatendBGRAPH9/22/2023414.多段圖問題的應(yīng)用實例將n個資源分配給r個項目的問題：如果把j個資源，0≤j≤n，分配給項目i，可以獲得N(i,j)的凈利。問題：如何將這n個資源分配給r個項目才能獲得最大可能的凈利。轉(zhuǎn)換成一個多段圖問題。9/22/202342

用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個資源所可能獲得的凈利?！锂攋≤n且i=r時，此時的邊為：<V(r,j),V(r+1,n)>,該邊賦予成本：9/22/202343實例：將4個資源分配給3個項目。構(gòu)成一個4段圖。

問題的解：資源的最優(yōu)分配方案是由s到t的一條最大成本的路徑給出——改變邊成本的符號，從而將問題轉(zhuǎn)換成為求取最小成本路徑問題。9/22/2023444.3每對結(jié)點之間的最短路徑1.問題描述設(shè)G=(V,E)是一個有n個結(jié)點的有向圖，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的最短路徑長度。9/22/202345分析：利用單源最短路徑算法求解

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

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

●決策什么？

●最優(yōu)性原理對于該問題是否成立？9/22/2023462.動態(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)性原理對于該問題成立。9/22/2023472）多階段決策過程設(shè)k是由i到j(luò)的最短路徑上編號（假設(shè)所有n個結(jié)點依次有從1到n的編號）最高的中間結(jié)點：i,...,k,…,j

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

則由i到k的子路徑上將不會有比編號k-1更大的結(jié)點；同理，由k到j(luò)的子路徑上也將不會有比編號k-1更大的結(jié)點。

構(gòu)造多階段決策過程：對由i到j(luò)的最短路徑，首先決策哪一個結(jié)點是該路徑上具有最大編號的中間結(jié)點k，然后再去求取由i到k和由k到j(luò)的最短路徑——其中應(yīng)不包含比k-1還大的中間結(jié)點。9/22/2023483）遞推關(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é)點9/22/202349

對任意的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)9/22/2023503.算法描述算法4.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-PATHS9/22/202351問：如何求每對結(jié)點之間的路徑？9/22/202352例4.8有向圖如圖所示A012310411260233∞0A11231041126023370A2123104626023370A3123104625023370642113v1v2v312310411260233∞0求圖中所有結(jié)點間的最短路徑矩陣A：注：A(i,j)=∞表明G中從i到j(luò)沒有有向路徑9/22/202353性能分析計算時間＝注：該時間與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)}repeatrepeatrepeat9/22/2023544.4最優(yōu)二分檢索樹1.問題的描述1）二分檢索樹定義二分檢索樹Ｔ是一棵二元樹，它或者為空，或者其每個結(jié)點含有一個可以比較大小的數(shù)據(jù)元素，且有：·Ｔ的左子樹的所有元素比根結(jié)點中的元素?。弧ぃ缘挠易訕涞乃性乇雀Y(jié)點中的元素大；·Ｔ的左子樹和右子樹也是二分檢索樹。注：·二分檢索樹要求樹中所有結(jié)點的元素值互異9/22/202355ifforwhilerepeatloopifforrepeatloopwhile對于一個給定的標識符集合，可能有若干棵不同的二分檢索樹:不同形態(tài)的二分檢索樹對標識符的檢索性能是不同的。9/22/2023562）二分檢索樹的檢索算法4.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ù)查找//endcaserepeatendSEARCH9/22/202357二分檢索樹的性能特征①例圖(a)：

最壞情況下查找標識符loop需要做4次比較；成功檢索平均需要做12/5次比較;圖(b)：

最壞情況下查找標識符loop/while需要做3次比較；成功檢索平均需要做11/5次比較②查找概率可以期望不同標識符的檢索頻率是不同的。如Pfor＞Pwhile＞

Ploop③不成功檢索可以期望不成功檢索出現(xiàn)的頻率也是不同的。9/22/2023583）最優(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種可能的情況，有

9/22/202359二分檢索樹

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

外結(jié)點：代表不成功檢索情況，剛好有n＋1個關(guān)于{a1,a2,…,an}的最優(yōu)二分檢索樹含義如下：9/22/202360二分檢索樹的預(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ù)=l9/22/202361

●不成功檢索：不成功檢索的等價類：每種不成功檢索情況定義了一個等價類，共有n+1個等價類Ei(0≤i≤n)。其中，E0={X|X＜a0}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ù)期總的成本公式表示如下：9/22/202362最優(yōu)二分檢索樹問題：求一棵使得預(yù)期成本最小的二分檢索樹例4.9標識符集合（a1,a2,a3）=（do,if,stop）?？赡艿亩謾z索樹如下所示。成功檢索：3種不成功情況：4種9/22/202363stopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e)9/22/2023641)等概率：P(i)=Q(i)=1/7cost(a)=15/7cost(b)=13/7

最優(yōu)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

最優(yōu)cost(d)=2.15cost(e)=1.6ifdostopdostopif(b)(c)9/22/2023652.多階段決策過程把構(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)成的二分檢索樹9/22/202366定義：含義：

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

●左、右子樹中所有結(jié)點的級數(shù)相對于子樹的根測定，而相對于原樹的根少19/22/202367記：則，原二分檢索樹的預(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)9/22/202368則，對任何C(i,j)有，向前遞推過程：

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

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

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

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

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

●依據(jù)R(0,n)…，推導(dǎo)樹的形態(tài)9/22/202370例４.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)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①②③④9/22/202371C(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)ji9/22/202372樹的形態(tài)ifdoreadwhile9/22/2023733.計算時間

●當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)]

9/22/2023744.算法描述procedureOBST(P,Q,n)//給定n個互異標識符a1＜a2＜…＜an。已知成功檢索的概率P(i),1≤i≤n。不成功檢索概率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(0: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←2tondofori←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)←krepeatrepeatendOBST9/22/202375OBST算法的計算時間:Ｏ(n2)9/22/2023761.問題描述1)KNAP(1,j,X)

目標函數(shù)：

約束條件：

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

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

4.50/1背包問題9/22/2023772)向后遞推關(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)9/22/202378例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}=69/22/202379解向量的推導(dǎo)f3(M)=6x3=1

ΔP=6-p3=1KNAP(1,3,6)=6

ΔM=6-w3=2X=(1,0,1)

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

9/22/202380f1,f2,f3計算過程（圖解）1234567012f0(x)=0i:fi-1(x-wi)+pii=0:函數(shù)不存在1234567012i＝1:f0(x-w1)+p11234567012f1(x)1234567012i＝2:f1(x-w2)+p23xxxx12345670123xf2(x)9/22/20238112345670678x1234589i＝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ī)則歸并而成9/22/2023822.序偶表示記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)9/22/202383●Si的構(gòu)造記是fi-1(X-wj)+pj的所有序偶的集合，則其中，Si-1是fi-1的所有序偶的集合

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

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

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

★

Si中的所有序偶是背包問題KNAP(1,i,X)在X各種取值下的最優(yōu)解9/22/202384例4.12例4.11的序偶計算S0={(0,0)}={(1,2)}S1={(0,0),(1,2)}={(2,3),(3,5)}S2={(0,0),(1,2),(2,3),(3,5)}={(5,4),(6,6),(7,7),(8,9)}S3={(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)}注：序偶(3,5)被(5,4)“支配”而刪除9/22/202385KNAP(1,n,M)問題的解★Sn是KNAP(1,n,X)在0≤X≤M各種取值下的最優(yōu)解★KNAP(1,n,M)的最優(yōu)解由Sn的最后一對有效序偶給出。xi的推導(dǎo)xn:設(shè)Sn的最后一對有效序偶是(P1,W1)，則(P1,W1)或者是Sn－1的最末一對序偶，或者是(Pj+pn,Wj+wn)，其中(Pj,Wj)∈Sn－1且Wj是Sn－1中滿足Wj+wn≤M的最大值。

●若(P1,W1)∈Sn－1，則Xn＝0；否則，

●(P1－pn,W1-wn)∈Sn－1，Xn＝1xn-1:若xn=0，則判斷(Pl,Wl)∈Sn－2？，以確定Xn-1的值若xn=1，則依據(jù)(Pl－pn,Wl-wn)∈Sn－2？，以判斷Xn-1的值xn-2,…,x1將依次推導(dǎo)得出

9/22/202386例4.13（例4.12)S0={(0,0)}S1={(0,0),(1,2)}S2={(0,0),(1,2),(2,3),(3,5)}S3={(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)}M=6，f3(6)由S3中的序偶(6,6)給出。1)∵(6,6)S2∴x3=12)∵(6-p3,6-w3)=(1,2)∈S2且(1,2)∈S1∴x2=03)∵(1,2)S0∴x1=19/22/202387算法4.6非形式的背包算法procedureDKP(p,w,n,M)

S0

←{(0,0)}fori←1ton-1do←{(P1,W1)|(P1-pi,W1-wi)∈Si-1andW1≤M}Si←MERGE-PURGE(Si-1,)repeat(PX,WX)←Sn-1的最末一個有效序偶(PY,WY)←(P1＋pn,W1+wn)，其中，W1是Sn-1中使得W＋wn≤M的所有序偶中取最大值得W//沿Sn-1,…,S1回溯確定xn,xn-1,…,x1的取值//ifPX＞PYthenxn←0//PX將是Sn的最末序偶//elsexn←1//PY將是Sn的最末序偶//endif回溯確定xn-1,…,x1endDKP9/22