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

第6章動(dòng)態(tài)規(guī)劃法6.1概述6.2圖問題中的動(dòng)態(tài)規(guī)劃法6.3組合問題中的動(dòng)態(tài)規(guī)劃法6.4查找問題中的動(dòng)態(tài)規(guī)劃法6.5實(shí)驗(yàn)項(xiàng)目——最大子段和問題動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，它是解決多階段決策過程最優(yōu)化問題的一種方法。1951年，美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）提出了解決這類問題的“最優(yōu)化原則”，1957年發(fā)表了他的名著《動(dòng)態(tài)規(guī)劃》，該書是動(dòng)態(tài)規(guī)劃方面的第一本著作。多階段決策問題：可以分為若干個(gè)相互聯(lián)系的階段，每個(gè)階段都要做出一個(gè)決策，這個(gè)決策即決定了本階段的效益，也決定了下一階段的初始狀態(tài)。當(dāng)每一個(gè)階段的決策確定后，就得到一個(gè)決策序列，稱為策略。多階段決策問題就是求一個(gè)策略，使各個(gè)階段的效益總和達(dá)到最優(yōu)。6.1概

述

6.1.1最優(yōu)化問題6.1.2最優(yōu)性原理6.1.3動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

最優(yōu)化問題：有n個(gè)輸入，它的解由這n個(gè)輸入的一個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的條件，這些條件稱為約束條件，滿足約束條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個(gè)，為了衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，這些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得極值（極大或極小）的可行解稱為最優(yōu)解，這類問題就稱為最優(yōu)化問題。

6.1.1最優(yōu)化問題例6-1：付款問題超市的自動(dòng)柜員機(jī)（POS機(jī)）要找給顧客數(shù)量最少的現(xiàn)金。如，要找4元6角現(xiàn)金，如何使找出的貨幣數(shù)量最少？假定POS機(jī)中有n張面值為pi(1≤i≤n)的貨幣，用集合P={p1,p2,…,pn}表示，如果POS機(jī)需支付的現(xiàn)金為A，那么，它必須從P中選取一個(gè)最小子集S，使得（式6.1） 如果用向量X=(x1,x2,…,xn)表示S中所選取的貨幣，則問題的解約束條件可行解

（式6.2）那么，POS機(jī)支付的現(xiàn)金必須滿足（式6.3）并且（式6.4）某問題的解是滿足約束條件的可行解，并且使得目標(biāo)函數(shù)取得極值，這問題就稱為最優(yōu)化問題。目標(biāo)函數(shù)約束條件6.1.2最優(yōu)性原理

對(duì)于一個(gè)具有n個(gè)輸入的最優(yōu)化問題，其求解過程往往可以劃分為若干個(gè)階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。從而，一個(gè)決策序列在不斷變化的狀態(tài)中產(chǎn)生。這個(gè)決策序列產(chǎn)生的過程稱為多階段決策過程。

S0P1P2Pn多階段決策過程S1S2Sn-1SnSn-1SnS1S0s1,1sn,knp1,1s1,k1p1,k1s1,r1………sn-1,kn-1pn,kn…pn-1,kn-1…動(dòng)態(tài)規(guī)劃的決策過程sn-1,1……sn-1,rn-1sn,1sn,rn……

在每一階段的決策中有一個(gè)賴以決策的策略或目標(biāo)，這種策略或目標(biāo)是由問題的性質(zhì)和特點(diǎn)所確定，通常以函數(shù)的形式表示并具有遞推關(guān)系，稱為動(dòng)態(tài)規(guī)劃函數(shù)。

多階段決策過程滿足最優(yōu)性原理（OptimalPrinciple）：無論決策過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的當(dāng)前狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。

最優(yōu)性原理：一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)，即無論其初始狀態(tài)及其初始決策如何，其以后諸決策對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)而言，必須構(gòu)成最優(yōu)策略。直觀理解：如果I-II是A到C的最佳線路，則II一定是B到C的最佳線路。即，“問題”的最優(yōu)解由“子問題”的最優(yōu)解組成。BACII’IIII’如果一個(gè)問題滿足最優(yōu)性原理，則稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。6.1.3動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

動(dòng)態(tài)規(guī)劃法將待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對(duì)應(yīng)決策過程的一個(gè)階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對(duì)給定問題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。原問題的解原問題……填表子問題1子問題2子問題n動(dòng)態(tài)規(guī)劃法的求解過程n=5時(shí)分治法計(jì)算斐波那契數(shù)的過程。

F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例6-2：計(jì)算斐波那契數(shù)：01234567890112358132134動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)F(9)的填表過程：注意到，計(jì)算F(n)是以計(jì)算它的兩個(gè)重疊子問題

F(n-1)和F(n-2)的形式來表達(dá)的，所以，可以設(shè)計(jì)一張表填入n+1個(gè)F(n)的值。

例6-3：數(shù)塔問題。有形如圖4.3所示的一個(gè)數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。圖4.3

一個(gè)數(shù)塔設(shè)計(jì)過程如下：階段劃分：

第一步對(duì)于第五層的數(shù)據(jù)，我們做如下四次決策：以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?階子問題，遞推出第四層與第五層的和為：21(2+19),28(18+10),19(9+10),21(5+16)

用同樣的方法可以將4階數(shù)塔問題，變?yōu)?階數(shù)塔問題……最后得到的1階數(shù)塔問題，就是整個(gè)問題的最優(yōu)解。2191810951674存儲(chǔ)、求解：原始信息存儲(chǔ)：原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個(gè)整型變量n存儲(chǔ)，數(shù)塔中的數(shù)據(jù)用二維數(shù)組data，存儲(chǔ)成如下的下三角陣：

9121510682189519710416動(dòng)態(tài)規(guī)劃過程存儲(chǔ)：必需用二維數(shù)組d存儲(chǔ)各階段的決策結(jié)果。二維數(shù)組d的存儲(chǔ)內(nèi)容如下：d[n][j]=data[n][j]:j=1,2,……,n；

i=n-1,n-2,……1，j=1,2,……,i時(shí)d[i][j]=max(d[i+1][j],d[i+1][j+1])+data[i][j]最后d[1][1]存儲(chǔ)的就是問題的結(jié)果（最大數(shù)值和）。即，數(shù)組d是自底向上遞推定義最優(yōu)值的結(jié)果。最優(yōu)解路徑求解及存儲(chǔ)：由數(shù)組data和數(shù)組d可以找到最優(yōu)解的路徑，但需要自頂向下比較數(shù)組data和數(shù)組d進(jìn)行尋找。如圖4.4求解和輸出過程如下：數(shù)組data數(shù)組d9121510682189519710416

輸出data[1][1]"9"b=d[1][1]-data[1][1]=59-9=50b與d[2][1],d[2][2]比較，b與d[2][1]相等輸出data[2][1]"12"b=d[2][1]-data[2][1]=50-12=38b與d[3][1],d[3][2]比較，b與d[3][1]相等輸出data[3][1]"10"b=d[3][1]-data[3][1]=38-10=28b與d[4][1],d[4][2]比較，b與d[4][2]相等輸出data[4][2]"18"b=d[4][2]-data[4][2]=28-18=10b與d[5][2],d[5][3]比較，b與d[5][3]相等輸出data[5][3]"10"2128192138342950495919710416最大值！最優(yōu)路徑：9

12

10

18

10為了設(shè)計(jì)簡(jiǎn)潔的算法，我們可以用三維數(shù)組a[50][50][3]存儲(chǔ)以上確定的三個(gè)數(shù)組的信息。a[50][50][1]代替數(shù)組data，a[50][50][2]代替數(shù)組d,a[50][50][3]記錄解路徑。從例子中可以看到：“局部最優(yōu)達(dá)到全局最優(yōu)”策略、遞推算法都是在“線性”地解決問題，而動(dòng)態(tài)規(guī)劃則是全面分階段地解決問題?？梢酝ㄋ椎卣f動(dòng)態(tài)規(guī)劃是“帶決策的多階段、多方位的遞推算法”。動(dòng)態(tài)規(guī)劃=“局部最優(yōu)達(dá)到全局最優(yōu)”策略+遞推(降階)+存儲(chǔ)遞推結(jié)果能夠分解為相互重疊的若干子問題；滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）：該問題的最優(yōu)解中也包含著其子問題的最優(yōu)解。（用反證法）分析問題是否滿足最優(yōu)性原理：先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的;然后再證明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。

用動(dòng)態(tài)規(guī)劃法求解的問題具有特征：動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。矩陣連乘問題給定n個(gè)矩陣，其中與是可乘的，?？疾爝@n個(gè)矩陣的連乘積如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少.由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積是完全加括號(hào)的，則可表示為2個(gè)完全加括號(hào)的矩陣連乘積和的乘積并加括號(hào)，即16000,10500,36000,87500,34500完全加括號(hào)的矩陣連乘積可遞歸地定義為：設(shè)有四個(gè)矩陣，它們的維數(shù)分別是：總共有五中完全加括號(hào)的方式完全加括號(hào)的矩陣連乘積特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。分析最優(yōu)解的結(jié)構(gòu)矩陣連乘問題窮舉法動(dòng)態(tài)規(guī)劃將矩陣連乘積簡(jiǎn)記為A[i:j]，這里i≤j考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應(yīng)完全加括號(hào)方式為計(jì)算量：A[i:k]的計(jì)算量加上A[k+1:j]的計(jì)算量，再加上兩個(gè)矩陣相乘的計(jì)算量建立遞歸關(guān)系設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]當(dāng)i=j時(shí)，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當(dāng)i<j時(shí)，可以遞歸地定義m[i,j]為：這里的維數(shù)為

的位置只有種可能計(jì)算最優(yōu)值對(duì)于1≤i≤j≤n不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問題。因此，不同子問題的個(gè)數(shù)最多只有由此可見，在遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法用動(dòng)態(tài)規(guī)劃法求最優(yōu)解A1A2A3A4A5A6303535

1515

55

1010

2020

25用動(dòng)態(tài)規(guī)劃法求最優(yōu)解voidMatrixChain(int*p，intn，int**m，int**s){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++){

intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){

intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。動(dòng)態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結(jié)構(gòu)矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。利用遞歸式直接計(jì)算m[i][j]int

RecurMatrixChain(inti，intj){ if(i==j)return0;

intu=RecurMatrixChain(i，i)+RecurMatrixChain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){

intt=LookupChain(i，k)+RecurMatrixChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}returnu;}動(dòng)態(tài)規(guī)劃算法的基本要素二、重疊子問題遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。6.2圖問題中的動(dòng)態(tài)規(guī)劃法

6.2.1TSP問題

6.2.2多段圖的最短路徑問題6.2.1TSP問題

TSP問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。各個(gè)城市間的距離可以用代價(jià)矩陣來表示。C=∞3675∞2364∞2375∞帶權(quán)圖的代價(jià)矩陣

設(shè)s,s1,s2,…,sp,s是從s出發(fā)的一條路徑長(zhǎng)度最短的簡(jiǎn)單回路，假設(shè)從s到下一個(gè)城市s1已經(jīng)求出，則問題轉(zhuǎn)化為求從s1到s的最短路徑，顯然s1,s2,…,sp,s一定構(gòu)成一條從s1到s的最短路徑。如若不然，設(shè)s1,r1,r2,…,rq,s是一條從s1到s的最短路徑且經(jīng)過n-1個(gè)不同城市，則s,s1,r1,r2,…,rq,s將是一條從s出發(fā)的路徑長(zhǎng)度最短的簡(jiǎn)單回路且比s,s1,s2,…,sp,s要短，從而導(dǎo)致矛盾。所以，TSP問題滿足最優(yōu)性原理。證明TSP問題滿足最優(yōu)性原理假設(shè)從頂點(diǎn)i出發(fā)，令d(i,V')表示從頂點(diǎn)i出發(fā)經(jīng)過V'中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)i的最短路徑長(zhǎng)度，開始時(shí)，V'＝V－{i}，于是，TSP問題的動(dòng)態(tài)規(guī)劃函數(shù)為：d(i,V')=min{cik+d(k,V’－{k})}(k∈V')（式6.5）d(k,{})=cki(k≠i)（式6.6）這是最后一個(gè)階段的決策，而：

d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}這一階段的決策又依賴于下面的計(jì)算結(jié)果：d(1,{2})=c12+d(2,{})d(2,{3})=c23+d(3,{})d(3,{2})=c32+d(2,{})d(1,{3})=c13+d(3,{})d(2,{1})=c21+d(1,{})d(3,{1})=c31+d(1,{})

從城市0出發(fā)經(jīng)城市1、2、3然后回到城市0的最短路徑長(zhǎng)度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}而下式可以直接獲得（括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移）：d(1,{})=c10=5(1→0)d(2,{})=c20=6(2→0)d(3,{})=c30=3(3→0)再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)d(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)再向前倒退，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)

所以，從頂點(diǎn)0出發(fā)的TSP問題的最短路徑長(zhǎng)度為10，路徑是0→1→2→3→0。

假設(shè)n個(gè)頂點(diǎn)用0～n-1的數(shù)字編號(hào)，首先生成1～n-1個(gè)元素的子集存放在數(shù)組V[2n-1]中，設(shè)數(shù)組d[n][2n-1]存放迭代結(jié)果，其中d[i][j]表示從頂點(diǎn)i經(jīng)過子集V[j]中的頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)0的最短路徑長(zhǎng)度。ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0

1015

86

7

269

5

10

331211

14

動(dòng)態(tài)規(guī)劃法求解TSP問題的填表過程算法6.1——TSP問題

1．for(i=1;i<n;i++)//初始化第0列

d[i][0]=c[i][0];2．for(j=1;j<2n-1-1;j++)for(i=1;i<n;i++)//依次進(jìn)行第i次迭代

if(子集V[j]中不包含i)

對(duì)V[j]中的每個(gè)元素k，計(jì)算d[i][j]=min(c[i][k]+d[k][j-1]);3．對(duì)V[2n-1-1]中的每一個(gè)元素k，計(jì)算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);4．輸出最短路徑長(zhǎng)度d[0][2n-1-1];偽代碼顯然，算法6.1的時(shí)間復(fù)雜性為O(2n)。和蠻力法相比，動(dòng)態(tài)規(guī)劃法求解TSP問題，把原來的時(shí)間復(fù)雜性是O(n!)的排列問題，轉(zhuǎn)化為組合問題，從而降低了算法的時(shí)間復(fù)雜性，但它仍需要指數(shù)時(shí)間。

設(shè)頂點(diǎn)之間的代價(jià)存放在數(shù)組c[n][n]中，動(dòng)態(tài)規(guī)劃法求解TSP問題的算法如下：

6.2.2多段圖的最短路徑問題

設(shè)圖G=(V,E)是一個(gè)帶權(quán)有向連通圖，如果把頂點(diǎn)集合V劃分成k個(gè)互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一條邊(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,

1＜i+m≤k），則稱圖G為多段圖，稱s∈V1為源點(diǎn)，t∈Vk為終點(diǎn)。多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。

2120345678949387684756866537一個(gè)多段圖由于多段圖將頂點(diǎn)劃分為k個(gè)互不相交的子集，所以，多段圖劃分為k段，每一段包含頂點(diǎn)的一個(gè)子集。不失一般性，將多段圖的頂點(diǎn)按照段的順序進(jìn)行編號(hào)，同一段內(nèi)頂點(diǎn)的相互順序無關(guān)緊要。假設(shè)圖中的頂點(diǎn)個(gè)數(shù)為n，則源點(diǎn)s的編號(hào)為0，終點(diǎn)t的編號(hào)為n-1，并且，對(duì)圖中的任何一條邊(u,v)，頂點(diǎn)u的編號(hào)小于頂點(diǎn)v的編號(hào)。設(shè)s,s1,s2,…,sp,t是從s到t的一條最短路徑，從源點(diǎn)s開始，設(shè)從s到下一段的頂點(diǎn)s1已經(jīng)求出，則問題轉(zhuǎn)化為求從s1到t的最短路徑，顯然s1,s2,…,sp,t一定構(gòu)成一條從s1到t的最短路徑，如若不然，設(shè)s1,r1,r2,…,rq,t是一條從s1到t的最短路徑，則s,s1,r1,r2,…,rq,t將是一條從s到t的路徑且比s,s1,s2,…,sp,t的路徑長(zhǎng)度要短，從而導(dǎo)致矛盾。所以，多段圖的最短路徑問題滿足最優(yōu)性原理。

證明多段圖問題滿足最優(yōu)性原理對(duì)多段圖的邊(u,v)，用cuv表示邊上的權(quán)值，將從源點(diǎn)s到終點(diǎn)t的最短路徑記為d(s,t)，則從源點(diǎn)0到終點(diǎn)9的最短路徑d(0,9)由下式確定：d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}

這是最后一個(gè)階段的決策，它依賴于d(1,9)、d(2,9)和d(3,9)的計(jì)算結(jié)果，而d(1,9)=min{c14+d(4,9),c15+d(5,9)}d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}d(3,9)=min{c35+d(5,9),c36+d(6,9)}

這一階段的決策又依賴于d(4,9)、d(5,9)和d(6,9)的計(jì)算結(jié)果：

d(4,9)=min{c47+d(7,9),c48+d(8,9)}d(5,9)=min{c57+d(7,9),c58+d(8,9)}d(6,9)=min{c67+d(7,9),c68+d(8,9)}這一階段的決策依賴于d(7,9)和d(8,9)的計(jì)算，而d(7,9)和d(8,9)可以直接獲得（括號(hào)中給出了決策產(chǎn)生的狀態(tài)轉(zhuǎn)移）：d(7,9)=c79＝7(7→9)d(8,9)=c89＝3(8→9)

再向前推導(dǎo)，有：d(6,9)=min{c67+d(7,9),c68+d(8,9)}=min{6+7,5+3}=8(6→8)d(5,9)=min{c57+d(7,9),c58+d(8,9)}=min{8+7,6+3}=9(5→8)d(4,9)=min{c47+d(7,9),c48+d(8,9)}=min{5+7,6+3}=9(4→8)d(3,9)=min{c35+d(5,9),c36+d(6,9)}=min{4+9,7+8}=13(3→5)d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}=min{6+9,7+9,8+8}=15(2→4)d(1,9)=min{c14+d(4,9),c15+d(5,9)}=min{9+9,8+9}=17(1→5)d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}=min{4+17,2+15,3+13}=16(0→3)

最后，得到最短路徑為0→3→5→8→9，長(zhǎng)度為16。

下面考慮多段圖的最短路徑問題的填表形式。用一個(gè)數(shù)組cost[n]作為存儲(chǔ)子問題解的表格，cost[i]表示從頂點(diǎn)i到終點(diǎn)n-1的最短路徑，數(shù)組path[n]存儲(chǔ)狀態(tài)，path[i]表示從頂點(diǎn)i到終點(diǎn)n-1的路徑上頂點(diǎn)i的下一個(gè)頂點(diǎn)。則：

cost[i]=min{cij+cost[j]}(i≤j≤n且頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn))

（式6.7）path[i]=使cij+cost[j]最小的j（式6.8）

算法6.2——多段圖的最短路徑

1．初始化：數(shù)組cost[n]初始化為最大值，數(shù)組path[n]初始化為-1；

2．for(i=n-2;i>=0;i--)2.1對(duì)頂點(diǎn)i的每一個(gè)鄰接點(diǎn)j，根據(jù)式6.7計(jì)算cost[i];2.2根據(jù)式6.8計(jì)算path[i];3．輸出最短路徑長(zhǎng)度cost[0];4.輸出最短路徑經(jīng)過的頂點(diǎn)：

4.1i=04.2循環(huán)直到path[i]=n-14.2.1輸出path[i];4.2.2i=path[i];偽代碼算法6.2主要由三部分組成：第一部分是初始化部分，其時(shí)間性能為O(n)；第二部分是依次計(jì)算各個(gè)頂點(diǎn)到終點(diǎn)的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對(duì)所有出邊進(jìn)行計(jì)算，并且在所有循環(huán)中，每條出邊只計(jì)算一次。假定圖的邊數(shù)為m，則這部分的時(shí)間性能是O(m)；第三部分是輸出最短路徑經(jīng)過的頂點(diǎn)，其時(shí)間性能是O(n)。所以，算法6.2的時(shí)間復(fù)雜性為O(n+m)。

6.3組合問題中的動(dòng)態(tài)規(guī)劃法6.3.10/1背包問題

6.3.2最長(zhǎng)公共子序列問題6.3.0最大字段和問題

給定由n個(gè)整數(shù)組成的序列(a1,a2,…,an)，最大子段和問題要求該序列形如的最大值（1≤i≤j≤n），當(dāng)序列中所有整數(shù)均為負(fù)整數(shù)時(shí)，其最大子段和為0。例如，序列(-20,11,-4,13,-5,-2)的最大子段和為：

6.3.0最大子段和問題

Int

Thissum=0;Thissum+=a[j];

分治算法見第四章時(shí)間耗費(fèi)為O(n)6.3.10/1背包問題

在0/1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的情況，則當(dāng)xi=0時(shí)，表示物品i沒有被裝入背包，xi=1時(shí)，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標(biāo)函數(shù)：

（式6.9）（式6.10）于是，問題歸結(jié)為尋找一個(gè)滿足約束條件式6.9，并使目標(biāo)函數(shù)式6.10達(dá)到最大的解向量X=(x1,x2,…,xn)。證明0/1背包問題滿足最優(yōu)性原理。設(shè)(x1,x2,…,xn)是所給0/1背包問題的一個(gè)最優(yōu)解，則(x2,…,xn)是下面一個(gè)子問題的最優(yōu)解：如若不然，設(shè)(y2,…,yn)是上述子問題的一個(gè)最優(yōu)解，則因此，

這說明(x1,y2,…,yn)是所給0/1背包問題比(x1,x2,…,xn)更優(yōu)的解，從而導(dǎo)致矛盾。

0/1背包問題可以看作是決策一個(gè)序列(x1,x2,…,xn)，對(duì)任一變量xi的決策是決定xi=1還是xi=0。在對(duì)xi-1決策后，已確定了(x1,…,xi-1)，在決策xi時(shí)，問題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品i，則xi=0，背包不增加價(jià)值；（2）背包容量可以裝入物品i，則xi=1，背包的價(jià)值增加了vi。這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì)xi決策后的背包價(jià)值。令V(i,j)表示在前i(1≤i≤n)個(gè)物品中能夠裝入容量為j（1≤j≤C）的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)：

V(i,0)=V(0,j)=0（式6.11）（式6.12）式6.11表明：把前面i個(gè)物品裝入容量為0的背包和把0個(gè)物品裝入容量為j的背包，得到的價(jià)值均為0。式6.12的第一個(gè)式子表明：如果第i個(gè)物品的重量大于背包的容量，則裝入前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)值是相同的，即物品i不能裝入背包；第二個(gè)式子表明：如果第i個(gè)物品的重量小于背包的容量，則會(huì)有以下兩種情況：（1）如果把第i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把前i-1個(gè)物品裝入容量為j-wi的背包中的價(jià)值加上第i個(gè)物品的價(jià)值vi；（2）如果第i個(gè)物品沒有裝入背包，則背包中物品的價(jià)值就等于把前i-1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。顯然，取二者中價(jià)值較大者作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。

根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)×(C+1)的二維表V，V[i][j]表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。

0例如，有5個(gè)物品，其重量分別是{2,2,6,5,4}，價(jià)值分別為{6,3,5,4,6}，背包的容量為10。x5=1x4=0x3=0x2=1x1=1

012345678910

00000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=5v5=6500669912121515150按下述方法來劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-wn的背包中；否則，第n個(gè)物品沒有被裝入背包，前n-1個(gè)物品被裝入容量為C的背包中。依此類推，直到確定第1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)：

（式6.13）

設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組w[n]中，價(jià)值存儲(chǔ)在數(shù)組v[n]中，背包容量為C，數(shù)組V[n+1][C+1]存放迭代結(jié)果，其中V[i][j]表示前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，數(shù)組x[n]存儲(chǔ)裝入背包的物品，動(dòng)態(tài)規(guī)劃法求解0/1背包問題的算法如下：

算法6.3——0/1背包問題

int

KnapSack(intn,intw[],intv[]){for(i=0;i<=n;i++)//初始化第0列

V[i][0]=0;for(j=0;j<=C;j++)//初始化第0行

V[0][j]=0;for(i=1;i<=n;i++)//計(jì)算第i行，進(jìn)行第i次迭代

for(j=1;j<=C;j++)if(j<w[i])C++描述算法6.3——0/1背包問題V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);j=C;//求裝入背包的物品

for(i=n;i>0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][C];//返回背包取得的最大價(jià)值}C++描述在算法6.3中，第一個(gè)for循環(huán)的時(shí)間性能是O(n)，第二個(gè)for循環(huán)的時(shí)間性能是O(C)，第三個(gè)循環(huán)是兩層嵌套的for循環(huán)，其時(shí)間性能是O(n×C)，第四個(gè)for循環(huán)的時(shí)間性能是O(n)，所以，算法6.3的時(shí)間復(fù)雜性為O(n×C)。

6.3.2最長(zhǎng)公共子序列問題

對(duì)給定序列X=(x1,x2,…,xm)和序列Z=(z1,z2,…,zk)，Z是X的子序列當(dāng)且僅當(dāng)存在一個(gè)嚴(yán)格遞增下標(biāo)序列(i1,i2,…,ik)，使得對(duì)于所有j=1,2,…,k，有zj=xij（1≤ij≤m）。給定兩個(gè)序列X和Y，當(dāng)另一個(gè)序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。最長(zhǎng)公共子序列問題就是在序列X和Y的公共子序列中查找長(zhǎng)度最長(zhǎng)的公共子序列。

證明最長(zhǎng)公共子序列問題滿足最優(yōu)性原理。設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，記Xk為序列X中前k個(gè)連續(xù)字符組成的子序列，Yk為序列Y中前k個(gè)連續(xù)字符組成的子序列，Zk為序列Z中前k個(gè)連續(xù)字符組成的子序列，顯然有下式成立：（1）若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列；（2）若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長(zhǎng)公共子序列；（3）若xm≠yn且zk≠yn，則Z是X和Yn-1的最長(zhǎng)公共子序列?？梢?，兩個(gè)序列的最長(zhǎng)公共子序列包含了這兩個(gè)序列的前綴序列的最長(zhǎng)公共子序列。要找出序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列，可按下述遞推方式計(jì)算：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm即可得到X和Y的最長(zhǎng)公共子序列；當(dāng)xm≠yn時(shí)，必須求解兩個(gè)子問題：找出Xm-1和Y的最長(zhǎng)公共子序列以及Xm和Yn-1的最長(zhǎng)公共子序列，這兩個(gè)公共子序列中的較長(zhǎng)者即為X和Y的最長(zhǎng)公共子序列。用L[i][j]表示子序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度，可得如下動(dòng)態(tài)規(guī)劃函數(shù)：L[0][0]=L[i][0]=L[0][j]=0(1≤i≤m,1≤j≤n)（式6.14）

（式6.15）由此，把序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列的搜索分為m個(gè)階段，第1階段，按照式6.15計(jì)算X1和Yj的最長(zhǎng)公共子序列長(zhǎng)度L[1][j]（1≤j≤n），第2階段，按照式6.15計(jì)算X2和Yj的最長(zhǎng)公共子序列長(zhǎng)度L[2][j]（1≤j≤n），依此類推，最后在第m階段，計(jì)算Xm和Yj的最長(zhǎng)公共子序列長(zhǎng)度L[m][j]（1≤j≤n），則L[m][n]就是序列Xm和Yn的最長(zhǎng)公共子序列的長(zhǎng)度。

為了得到序列Xm和Yn具體的最長(zhǎng)公共子序列，設(shè)二維表S[m+1][n+1]，其中S[i][j]表示在計(jì)算L[i][j]的過程中的搜索狀態(tài)，并且有：

（式6.16）若S[i][j]=1，表明ai=bj，則下一個(gè)搜索方向是S[i-1][j-1]；若S[i][j]=2，表明ai≠bj且L[i][j-1]≥L[i-1][j]，則下一個(gè)搜索方向是S[i][j-1]；若S[i][j]=3，表明ai≠bj且L[i][j-1]＜L[i-1][j]，則下一個(gè)搜索方向是S[i-1][j]。

(a)長(zhǎng)度矩陣L(b)狀態(tài)矩陣S01234567890123456789000000000000000000000101111111111012221222220112222222203211212113012222222230312222222401233333334033113131150123333444503332221226012344445560331131211例：序列X=(a,b,c,b,d,b)，Y=(a,c,b,b,a,b,d,b,b)，建立兩個(gè)(m+1)×(n+1)的二維表L和表S，分別存放搜索過程中得到的子序列的長(zhǎng)度和狀態(tài)。算法6.4——最長(zhǎng)公共子序列問題

int

CommonOrder(intm,intn,intx[],inty[],intz[]){for(j=0;j<=n;j++)//初始化第0行

L[0][j]=0;for(i=0;j<=m;i++)//初始化第0列

L[i][0]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(x[i]==y[j]){L[i][j]=L[i-1][j-1]+1;S[i][j]=1;}elseif(L[i][j-1]>=L[i-1][j]){L[i][j]=L[i][j-1];S[i][j]=2;}else{L[i][j]=L[i-1][j];S[i][j]=3;}i=m;j=n;k=L[m][n];for(i>0&&j>0){if(S[i][j]==1){z[k]=x[i];k--;i--;j--;}elseif(S[i][j]==2)j--;elsei--;}returnL[m][n];}C++描述在算法6.4中，第一個(gè)for循環(huán)的時(shí)間性能是O(n)；第二個(gè)for循環(huán)的時(shí)間性能是O(m)；第三個(gè)循環(huán)是兩層嵌套的for循環(huán)，其時(shí)間性能是O(m×n)；第四個(gè)for循環(huán)的時(shí)間性能是O(k)，而k≤min{m,n}，所以，算法6.4的時(shí)間復(fù)雜性是O(m×n)。

6.4查找問題中的動(dòng)態(tài)規(guī)劃法

6.4.1最優(yōu)二叉查找樹

6.4.2近似串匹配問題設(shè){r1,r2,…,rn}是n個(gè)記錄的集合，其查找概率分別是{p1,p2,…,pn}，最優(yōu)二叉查找樹（OptimalBinarySearchTrees）是以這n個(gè)記錄構(gòu)成的二叉查找樹中具有最少平均比較次數(shù)的二叉查找樹，即最小，其中pi是記錄ri的查找概率，ci是在二叉查找樹中查找ri的比較次數(shù)。6.4.1最優(yōu)二叉查找樹

ABCD

(a)(b)(c)二叉查找樹示例BCDAABCD例如，集合{A,B,C,D}的查找概率是{0.1,0.2,0.4,0.3}，(a)的平均比較次數(shù)是0.1×1＋0.2×2+0.4×3+0.3×4=2.9，(b)的平均比較次數(shù)是0.1×2＋0.2×1+0.4×2+0.3×3=2.1，(c)的平均比較次數(shù)是0.1×3＋0.2×2+0.4×1+0.3×2=1.7。將由{r1,r2,…,rn}構(gòu)成的二叉查找樹記為T(1,n)，其中rk（1≤k≤n）是T(1,n)的根結(jié)點(diǎn)，則其左子樹T(1,k-1)由{r1,…,rk-1}構(gòu)成，其右子樹T(k+1,n)由{rk+1,…,rn}構(gòu)成。證明最優(yōu)二叉查找樹滿足最優(yōu)性原理rkT(1,n)以rk為根的二叉查找樹T(k+1,n)T(1,k-1)若T(1,n)是最優(yōu)二叉查找樹，則其左子樹T(1,k-1)和右子樹T(k+1,n)也是最優(yōu)二叉查找樹，如若不然，假設(shè)T'(1,k-1)是比T(1,k-1)更優(yōu)的二叉查找樹，則T'(1,k-1)的平均比較次數(shù)小于T(1,k-1)的平均比較次數(shù)，從而由T'(1,k-1)、rk和T(k+1,n)構(gòu)成的二叉查找樹T'(1,n)的平均比較次數(shù)小于T(1,n)的平均比較次數(shù)，這與T(1,n)是最優(yōu)二叉查找樹的假設(shè)相矛盾。設(shè)T(i,j)是由記錄{ri,…,rj}(1≤i≤j≤n)構(gòu)成的二叉查找樹，C(i,j)是這棵二叉查找樹的平均比較次數(shù)。雖然最后的結(jié)果是C(1,n)，但遵循動(dòng)態(tài)規(guī)劃法的求解方法,需要求出所有較小子問題C(i,j)的值，考慮從{ri,…,rj}中選擇一個(gè)記錄rk作為二叉查找樹的根結(jié)點(diǎn)，可以得到如下關(guān)系：

因此，得到如下動(dòng)態(tài)規(guī)劃函數(shù)：

C(i,i-1)=0(1≤i≤n+1)（式6.17）C(i,i)=pi(1≤i≤n)（式6.18）C(i,j)=min{C(i,k-1)+C(k+1,j)+}(1≤i≤j≤n,i≤k≤j)

（式6.19）設(shè)一個(gè)二維表C[n+1][n+1]，其中C[i][j]表示二叉查找樹T(i,j)的平均比較次數(shù)。注意到在式6.19中，當(dāng)k=1時(shí)，求C[i][j]需要用到C[i][0]，當(dāng)k=n時(shí)，求C[i][j]需要用到C[n+1][j]，所以，二維表C[n+1][n+1]行下標(biāo)的范圍為1～n+1，列下標(biāo)的范圍為0～n。為了在求出由{r1,r2,…,rn}構(gòu)成的二叉查找樹的平均比較次數(shù)的同時(shí)得到最優(yōu)二叉查找樹，設(shè)一個(gè)二維表R[n+1][n+1]，其下標(biāo)范圍與二維表C相同，R[i][j]表示二叉查找樹T(i,j)的根結(jié)點(diǎn)的序號(hào)。例如，集合{A,B,C,D}的查找概率是{0.1,0.2,0.4,0.3}，二維表C和R的初始情況如圖6.13所示。

01234100.1

2

00.2

3

00.4

4

00.35

0

012341

1

2

2

3

3

4

45

在二維表C和R中只需計(jì)算主對(duì)角線以上的元素。首先計(jì)算C(1,2)：

在前兩個(gè)記錄構(gòu)成的最優(yōu)二叉查找樹的根結(jié)點(diǎn)的序號(hào)是2。按對(duì)角線逐條計(jì)算每一個(gè)C(i,j)和R(i,j)，得到最終表。

01234100.10.41.11.72

00.20.81.43

00.41.04

00.35

0

012341

12

2332

2333

334

45

二維表C(b)二維表R

最終表的狀態(tài)d=1d=2d=3d=1d=2d=3設(shè)n個(gè)字符的查找概率存儲(chǔ)在數(shù)組p[n]中，動(dòng)態(tài)規(guī)劃法求解最優(yōu)二叉查找樹的算法如下：算法6.5——最優(yōu)二叉查找樹

doubleOptimalBST(intn,doublep[],doubleC[][],intR[][]){for(i=1;i<=n;i++)//按式6.17和式6.18初始化

{C[i][i-1]=0;

C[i][i]=p[i];

R[i][i]=i;}C[n+1][n]=0;

C++描述for(d=1;d<n;d++)//按對(duì)角線逐條計(jì)算

for(i=1;i<=n-d;i++){j=i+d;min=∞;mink=i;sum=0;for(k=i;k<=j;k++){sum=sum+p[k];if(C[i][k-1]+C[k+1][j]<min){min=C[i][k-1]+C[k+1][j];mink=k;}}

C[i][j]=min+sum;

R[i][j]=mink;}returnC[1][n];}6.4.2近似串匹配問題