1、第5章 動(dòng)態(tài)規(guī)劃法 2022/8/111成都學(xué)院計(jì)算機(jī)系知識(shí)要點(diǎn):掌握動(dòng)態(tài)規(guī)劃法主要思想;掌握動(dòng)態(tài)規(guī)劃與分治法、貪心法的區(qū)別；掌握基本的運(yùn)算；2022/8/112成都學(xué)院計(jì)算機(jī)系5.1 一般方法和基本要素5.2 每對(duì)結(jié)點(diǎn)間的最短路徑 5.3 最長(zhǎng)公共子序列5.4 矩陣連乘2022/8/113成都學(xué)院計(jì)算機(jī)系5.1 一般方法和基本要素 2022/8/114成都學(xué)院計(jì)算機(jī)系算法總體思想動(dòng)態(tài)規(guī)劃算法是另一種求解最優(yōu)化問(wèn)題的重要算法設(shè)計(jì)策略。與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022/8/115成都學(xué)院計(jì)算機(jī)系但是經(jīng)

2、分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2022/8/116成都學(xué)院計(jì)算機(jī)系如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4

3、)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)2022/8/117成都學(xué)院計(jì)算機(jī)系分治法、貪心法、動(dòng)態(tài)規(guī)劃區(qū)別動(dòng)態(tài)規(guī)劃法的實(shí)質(zhì)也是將較大問(wèn)題分解為較小的同類子問(wèn)題，這一點(diǎn)上它與分治法和貪心法類似。分治法的子問(wèn)題相互獨(dú)立，相同的子問(wèn)題被重復(fù)計(jì)算，動(dòng)態(tài)規(guī)劃法解決這種子問(wèn)題重疊現(xiàn)象。貪心法要求針對(duì)問(wèn)題設(shè)計(jì)最優(yōu)量度標(biāo)準(zhǔn)，但這在很多情況下并不容易。動(dòng)態(tài)規(guī)劃法利用最優(yōu)子結(jié)構(gòu)，自底向上從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解，動(dòng)態(tài)規(guī)劃則可以處理不具備貪心準(zhǔn)則的問(wèn)題。2022/8/118成都學(xué)院計(jì)算機(jī)系5.1.1 一般方法 最優(yōu)子結(jié)構(gòu)特性是動(dòng)態(tài)規(guī)劃法求解問(wèn)題的必要條

4、件。最優(yōu)子結(jié)構(gòu)特性(最優(yōu)性原理)：一個(gè)最優(yōu)策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，其余決策必定構(gòu)成最優(yōu)策略。2022/8/119成都學(xué)院計(jì)算機(jī)系多步?jīng)Q策求解方法是從初始階段的初始狀態(tài)出發(fā)，做出每個(gè)階段的決策，形成一個(gè)決策序列，對(duì)于每一個(gè)決策序列，用一個(gè)數(shù)值函數(shù)（即目標(biāo)函數(shù)）衡量該策略的優(yōu)劣。問(wèn)題求解的目標(biāo)是獲取導(dǎo)致問(wèn)題最優(yōu)解的最優(yōu)決策序列。2022/8/1110成都學(xué)院計(jì)算機(jī)系設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵虏襟E:（1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特性；（2）遞歸定義最優(yōu)解值；（3）以自底向上方式計(jì)算最優(yōu)解值；（4）根據(jù)計(jì)算最優(yōu)值得到的信息構(gòu)造一個(gè)最優(yōu)解。

5、 其中，第（1）至（3）步是動(dòng)態(tài)規(guī)劃算法的基本步驟。 最優(yōu)解值是最優(yōu)解的目標(biāo)函數(shù)的值。 2022/8/1111成都學(xué)院計(jì)算機(jī)系5.1.2 基本要素 一個(gè)最優(yōu)化多步?jīng)Q策問(wèn)題適合用動(dòng)態(tài)規(guī)劃法求解有兩個(gè)要素：最優(yōu)子結(jié)構(gòu)特性和重疊子問(wèn)題。最優(yōu)子結(jié)構(gòu)特性：較小問(wèn)題的最優(yōu)解與較大子問(wèn)題的最優(yōu)解之間存在數(shù)值關(guān)系。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。 2022/8/1112成都學(xué)院計(jì)算機(jī)系5.1.3 多段圖問(wèn)題 1 .多段圖問(wèn)題 多段圖G=(V,E)是一個(gè)帶權(quán)有向圖，它具有如下特性：圖中的結(jié)點(diǎn)被劃分成k2個(gè)互不相交的子集V

6、i，1ik。其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)，V1包含源點(diǎn)（source）s，Vk包含匯點(diǎn)（sink）t。對(duì)所有邊E，多段圖要求若uVi，則vVi1，1ik，每條邊的權(quán)值為c(u,v)。從s到t的路徑長(zhǎng)度是這條路徑上邊的權(quán)值之和，多段圖問(wèn)題（multistage graph problem）是求從s到t的一條長(zhǎng)度最短的路徑。2022/8/1113成都學(xué)院計(jì)算機(jī)系5.1.3 多段圖問(wèn)題2022/8/1114成都學(xué)院計(jì)算機(jī)系5.1.3 多段圖問(wèn)題 2.多段圖的最優(yōu)子結(jié)構(gòu) 假定(s,v2,v3,vk-1,t)是一條從s到t的最短路徑，并假定初始狀態(tài)(源點(diǎn)s)已做出到達(dá)v2的決策。 如果將V2看成原問(wèn)題

7、的一個(gè)子問(wèn)題的初始狀態(tài)，求解此子問(wèn)題就變成尋找一個(gè)從v2到t的最短路徑。 如果(s,v2,v3,vk-1,t)是一條從s到t的最短路徑，則(v2,v3,vk-1,t)必是從v2到t的最短路徑，否則存在(v2,q3,qk-1,t)是從v2到t的最短路徑，此時(shí)(s,v2,q3,qk-1,t)比(s,v2,v3,vk-1,t)更短，與假設(shè)矛盾。 所以，多段圖問(wèn)題最優(yōu)性原理成立。2022/8/1115成都學(xué)院計(jì)算機(jī)系 3.多段圖的向前遞推關(guān)系式 對(duì)于多段圖問(wèn)題，一個(gè)階段的決策與后面所要求解的子問(wèn)題相關(guān)，所以不能在某個(gè)階段直接做出決策。 可以從最后階段開(kāi)始，采用逐步向前遞推的方式進(jìn)行求解，可以其向前遞推

8、式： Cost(i,j)是從第i階段狀態(tài)j到t的最短路徑的長(zhǎng)度，i是階段編號(hào)，j是第i階段的一個(gè)狀態(tài)（結(jié)點(diǎn)）編號(hào)。 一般情況，計(jì)算cost(i,j),必須先計(jì)算從j的所有后繼結(jié)點(diǎn)p到t的最短路徑的長(zhǎng)度，即先計(jì)算cost(i+1,p)的值。 2022/8/1116成都學(xué)院計(jì)算機(jī)系 例子：對(duì)于圖所示的5段圖，按由后向前計(jì)算最優(yōu)解值的步驟如下： cost(5,11)=0; cost(4,10)=5,cost(4,9)=2,cost(4,8)=4 cost(3,7)=min6+cost(4,10),5+cost(4,9)=7, cost(3,6)=5,cost(3,5)=7 cost(2,4)= mi

9、n8+cost(3,7),11+cost(3,6)=16 cost(2,3)=18,cost(2,2)=9,cost(2,1)=7 cost(1,0)=min(9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)=162022/8/1117成都學(xué)院計(jì)算機(jī)系4.多段圖的向前遞推算法 使用一維數(shù)組costj保存結(jié)點(diǎn)j到t的最短路徑長(zhǎng)度。根據(jù)遞推式的要求，將圖G的結(jié)點(diǎn)按階段順序從0到n-1進(jìn)行編號(hào)，源點(diǎn)s編號(hào)為0，匯點(diǎn)t為n-1;向前遞推計(jì)算按結(jié)點(diǎn)編號(hào)從大到小的次序進(jìn)行：先計(jì)算costn-1=0,再計(jì)算costn-2,最后計(jì)算得到cost0。數(shù)組p保存對(duì)應(yīng)于

10、cost0的最短路徑上的結(jié)點(diǎn)，它是問(wèn)題的最優(yōu)解。templatevoid Graph:FMultiGraph(int k,int *p)/采用程序的鄰接表存儲(chǔ)圖G。float *cost=new floatn; int q,*d=new intn;costn-1=0,dn-1=-1; 2022/8/1118成都學(xué)院計(jì)算機(jī)系for (int j=n-2;j=0;j-) /按n-2,0的次序計(jì)算cost和d float min=INFTY; /按式計(jì)算最小值為costj for (ENode *r=aj;r;r=r-nextArc) int v=r-adjVex; if (r-w+costvw+c

11、ostv;q=v; costj=min;dj=q; /q是j在最短子路徑上的后繼結(jié)點(diǎn) p0=0;pk-1=n-1; c=cost0;/p0和pn-1是源點(diǎn)和匯點(diǎn) for(j=1;j=k-2;j+) pj=dpj-1; /pi 是最短路徑上第i階段的結(jié)點(diǎn) delete cost;delete d;2022/8/1119成都學(xué)院計(jì)算機(jī)系5.1.5 資源分配問(wèn)題 實(shí)際應(yīng)用問(wèn)題可抽象成一個(gè)多段圖問(wèn)題處理。例如，資源分配問(wèn)題 將n個(gè)資源分配給r個(gè)項(xiàng)目，已知如果把j個(gè)資源分配給第i個(gè)項(xiàng)目，可以收益N(i,j)，0jn，1ir。求總收益最大的資源分配方案。2022/8/1120成都學(xué)院計(jì)算機(jī)系2022/8/

12、1121成都學(xué)院計(jì)算機(jī)系5.1.6 關(guān)鍵路徑問(wèn)題 關(guān)鍵路徑問(wèn)題是一個(gè)求帶權(quán)有向無(wú)環(huán)圖中兩點(diǎn)間的最長(zhǎng)路徑問(wèn)題。是一個(gè)AOV網(wǎng)絡(luò)問(wèn)題。 （自學(xué)此內(nèi)容）2022/8/1122成都學(xué)院計(jì)算機(jī)系5.2 每對(duì)結(jié)點(diǎn)間的最短路徑 2022/8/1123成都學(xué)院計(jì)算機(jī)系5.2.1 問(wèn)題描述 設(shè)G=(V,E)是一個(gè)有n個(gè)結(jié)點(diǎn)的帶權(quán)有向圖，w(i,j)是權(quán)函數(shù)， 每對(duì)結(jié)點(diǎn)間的最短路徑問(wèn)題是指求圖中任意一對(duì)結(jié)點(diǎn)i和j之間的最短路徑。2022/8/1124成都學(xué)院計(jì)算機(jī)系5.2.1 問(wèn)題描述可以使用迪杰斯特拉算法可求解單源最短路徑問(wèn)題，其時(shí)間復(fù)雜度為O(n2)。求任意一對(duì)結(jié)點(diǎn)之間的最短路徑，可以分別以圖中每個(gè)結(jié)點(diǎn)為源點(diǎn)

13、，n次調(diào)用迪杰斯特拉算法計(jì)算，其時(shí)間復(fù)雜度為O(n3)。sabct32-5452022/8/1125成都學(xué)院計(jì)算機(jī)系5.2.1 問(wèn)題描述弗洛伊德（Floyd）算法是一種動(dòng)態(tài)規(guī)劃算法，它求帶權(quán)有向圖G=（v,E）中所有結(jié)點(diǎn)之間的最短路徑。路徑長(zhǎng)度仍是指路徑上的邊所帶的權(quán)值之和。2022/8/1126成都學(xué)院計(jì)算機(jī)系5.2.2 動(dòng)態(tài)規(guī)劃法求解 最優(yōu)子結(jié)構(gòu) 設(shè)圖G=(V,E)是帶權(quán)有向圖，(i,j)是從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，k是這條路徑上的一個(gè)結(jié)點(diǎn)，(i,k) 和(k,j)分別是從i到k和從k到j(luò)的最短路徑長(zhǎng)度，則必有(i,j)= (i,k)+(k,j)。因?yàn)槿舨蝗唬瑒t(i,j)代表的路徑就

14、不是最短路徑。這表明每對(duì)結(jié)點(diǎn)之間的最短路徑問(wèn)題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。2022/8/1127成都學(xué)院計(jì)算機(jī)系最優(yōu)解的遞推關(guān)系 設(shè)dkij是從結(jié)點(diǎn)i到結(jié)點(diǎn)j的路徑上，只允許包含結(jié)點(diǎn)編號(hào)不大于k的結(jié)點(diǎn)時(shí)，所有可能路徑中的最短路徑長(zhǎng)度。 圖中不存在編號(hào)比n-1更大的編號(hào)，所以 (i,j)=dn-1ij 因?yàn)樽顑?yōu)子結(jié)構(gòu)特性，有 dn-1ij=mindn-2ij,dn-2in-1+ dn-2n-1j 則dn-1ij必為dn-2ij和dn-2in-1+ dn-2n-1j這兩條路徑的較短者。 2022/8/1128成都學(xué)院計(jì)算機(jī)系最優(yōu)解的遞推關(guān)系一般地: dkij=mindk-1ij， dk-2in-1

15、+ dk-2n-1jikjdk-1ikdk-1kjdk-1ij最優(yōu)子結(jié)構(gòu)2022/8/1129成都學(xué)院計(jì)算機(jī)系最優(yōu)解的遞推關(guān)系重疊子問(wèn)題： 從上式可知，為了計(jì)算dkij時(shí)，必須先計(jì)算Dk-1ij、dk-1ik和dk-1ik，dk-1的元素被多個(gè)dk的元素的計(jì)算共享。從前面的分析可知如下遞推式：2022/8/1130成都學(xué)院計(jì)算機(jī)系5.2.3弗洛伊德算法 弗洛伊德算法的基本思想是： 每次考察一個(gè)結(jié)點(diǎn)k(k=0,1,n-1)是否在最短路徑上。 設(shè)有向圖存儲(chǔ)在鄰接矩陣a中，初始時(shí)dij= aij。二維數(shù)組d用于保存各條最短路徑的長(zhǎng)度，其中，dij存放從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑的長(zhǎng)度。二維數(shù)組path

16、記錄相應(yīng)的最短路徑。Pij是從結(jié)點(diǎn)i到j(luò)的最短路徑上結(jié)點(diǎn)j的前一個(gè)結(jié)點(diǎn)，從路徑的終點(diǎn)j開(kāi)始，其前一個(gè)結(jié)點(diǎn)是k=pathij,再向前一個(gè)結(jié)點(diǎn)為k=pathik,直到起始點(diǎn)i為止，形成一條路徑。2022/8/1131成都學(xué)院計(jì)算機(jī)系弗洛伊德算法templatevoid MGraph:Floyd(T*& d, int *& path)int i,j,k;d= new T*n;path=new int *n;for(i=0;in;i+) di=new T n;pathi=new intn; for (j=0;jn;j+) dij=aij; if (i!=j & wijINFTY) pathij=i; else pathij=-1; 2022/8/1132成都學(xué)院計(jì)算機(jī)系 for (k=0;kn;k+) /考察結(jié)點(diǎn)k for (i=0;in;i+) for (j=0;jn;j+) if (dik+dkj dij ) dij=dik+dkj; pathij=pathkj; 弗洛伊德算法的時(shí)間復(fù)雜度為O(n3)2022/8/1133成都學(xué)院計(jì)算機(jī)系2022/8/1