算法設(shè)計(jì)與分析 課件 第四章 動(dòng)態(tài)規(guī)劃

計(jì)算機(jī)算法設(shè)計(jì)與分析第四章

動(dòng)態(tài)規(guī)劃學(xué)習(xí)目標(biāo)了解動(dòng)態(tài)規(guī)劃法的基本概念。掌握動(dòng)態(tài)規(guī)劃法的基本思想。掌握動(dòng)態(tài)規(guī)劃法解決實(shí)際問(wèn)題。4.1動(dòng)態(tài)規(guī)劃的提出在現(xiàn)實(shí)生活中，有一類活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。當(dāng)然，各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線，如下圖所示。這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為多階段決策過(guò)程，這種問(wèn)題就稱為多階段決策問(wèn)題。1狀態(tài)決策2狀態(tài)狀態(tài)決策n狀態(tài)狀態(tài)...決策4.1動(dòng)態(tài)規(guī)劃的提出在多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策取決于當(dāng)前的狀態(tài)，然后又會(huì)引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在不斷變化的狀態(tài)中依次產(chǎn)生出來(lái)的，故有動(dòng)態(tài)的含義。因此，把處理它的方法稱為動(dòng)態(tài)規(guī)劃方法。但是，一些與時(shí)間沒(méi)有關(guān)系的靜態(tài)規(guī)劃，如線性規(guī)劃、非線性規(guī)劃等問(wèn)題，只要人為地引進(jìn)時(shí)間因素，也可把它視為多階段決策問(wèn)題，用動(dòng)態(tài)規(guī)劃方法去處理。4.2動(dòng)態(tài)規(guī)劃基本概念1.階段動(dòng)態(tài)規(guī)劃方法求解的問(wèn)題都屬于多階段決策問(wèn)題。因此需要將所求問(wèn)題劃分為若干個(gè)階段。把描述階段的變量稱為階段變量，用k來(lái)表示。在劃分階段時(shí)，要求劃分后的階段按照時(shí)間或空間特征是有序的，否則問(wèn)題就無(wú)法求解。在下圖中，階段可以劃分為5個(gè)，即k=1,2,3,4,5。2.狀態(tài)每個(gè)階段所處的客觀條件稱為狀態(tài)，它描述了研究問(wèn)題過(guò)程的中間狀況。狀態(tài)就是某階段的出發(fā)位置，既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。通常一個(gè)階段有若干狀態(tài)。在下圖中，第一階段只有狀態(tài){A}，第二階段有狀態(tài){B1，B2}，第三階段有狀態(tài){C1，C2，C3，C4}。描述狀態(tài)的變量稱為狀態(tài)變量。通常用Sk表示第k階段的狀態(tài)變量。在圖中，S3={C1，C2，C3，C4}，該集合就稱為第三階段的可達(dá)狀態(tài)集。4.2動(dòng)態(tài)規(guī)劃基本概念2.狀態(tài)這里的狀態(tài)必須滿足無(wú)后效性（馬爾可夫性），即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說(shuō)，某狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，而只與當(dāng)前狀態(tài)有關(guān)。4.2動(dòng)態(tài)規(guī)劃基本概念

4.2動(dòng)態(tài)規(guī)劃基本概念4.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的過(guò)程。給定第k階段的某個(gè)狀態(tài)變量sk，在選定好決策uk后，第k+1階段的狀態(tài)變量sk+1也就完全確定下來(lái)。這種由sk和uk確定sk+1的對(duì)應(yīng)關(guān)系Tk就稱為狀態(tài)轉(zhuǎn)移方程，即sk+1=Tk(sk,uk)。4.2動(dòng)態(tài)規(guī)劃基本概念5.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)是用來(lái)衡量所選定策略優(yōu)劣的一種數(shù)量指標(biāo)。它是定義在全過(guò)程和所有后部子過(guò)程上確定的數(shù)量函數(shù)。常用Vk,n表示。即Vk,n=Vk,n(sk,uk,sk+1,...,sn+1)，k=1,2,...,n。常見(jiàn)的指標(biāo)函數(shù)的形式如下：（1）過(guò)程和它的任一子過(guò)程的指標(biāo)是它所包含的各階段的指標(biāo)的和。（2）過(guò)程和它的任一子過(guò)程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。4.2動(dòng)態(tài)規(guī)劃基本概念5.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為fk(sk)。它表示從第k階段的狀態(tài)sk開(kāi)始到第n階段的終止?fàn)顟B(tài)的過(guò)程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。在不同的問(wèn)題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤(rùn)、成本、產(chǎn)品的產(chǎn)量或資源消耗等。4.2動(dòng)態(tài)規(guī)劃基本概念4.3動(dòng)態(tài)規(guī)劃基本思想與優(yōu)化原則動(dòng)態(tài)規(guī)劃的基本思想可以總結(jié)為：（1）將多階段決策過(guò)程劃分階段，恰當(dāng)?shù)倪x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)，從而把問(wèn)題化為一組同類型的子問(wèn)題，然后逐個(gè)求解。（2）求解時(shí)從邊界條件開(kāi)始，逆（或順）過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。在每個(gè)子問(wèn)題求解時(shí)，都要使用前面已求出的子問(wèn)題的最優(yōu)結(jié)果，最后一個(gè)子問(wèn)題的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。（3）動(dòng)態(tài)規(guī)劃的基本方程是遞推逐段求解的依據(jù)，一般的動(dòng)態(tài)規(guī)劃的基本方程

4.3動(dòng)態(tài)規(guī)劃基本思想與優(yōu)化原則下面以例子來(lái)說(shuō)明（3）k=2，狀態(tài)變量可以取2個(gè)狀態(tài)B1、B2，它們到達(dá)終點(diǎn)E需要通過(guò)C1、C2、C3或C4，同樣需要選擇一條最短的路徑。計(jì)算如下：（4）k=1，同理可以計(jì)算出從而從起點(diǎn)A到終點(diǎn)E的最短路徑為A-B2-C4-D3-E，最短距離為13。4.3動(dòng)態(tài)規(guī)劃基本思想與優(yōu)化原則優(yōu)化原則（最優(yōu)子結(jié)構(gòu)性質(zhì)）：一個(gè)最優(yōu)決策序列的任何子序列本身一定是相對(duì)于子序列的初始和結(jié)束狀態(tài)的最優(yōu)決策序列。一般來(lái)說(shuō)，能用動(dòng)態(tài)規(guī)劃求解的問(wèn)題具有以下三個(gè)性質(zhì)：（1）滿足最優(yōu)子結(jié)構(gòu)；（2）滿足無(wú)后效性；（3）有重疊的子問(wèn)題。4.3動(dòng)態(tài)規(guī)劃基本思想與優(yōu)化原則動(dòng)態(tài)規(guī)劃和分治法的區(qū)別：

分治法拆分的子問(wèn)題只是求解過(guò)程類似，但問(wèn)題本身是相互獨(dú)立的；而動(dòng)態(tài)規(guī)劃法的子問(wèn)題之間并不獨(dú)立，尤其是相鄰階段的子問(wèn)題最優(yōu)值函數(shù)是有依賴關(guān)系的，這就是所謂的有重疊的子問(wèn)題。有重疊的子問(wèn)題并非動(dòng)態(tài)規(guī)劃法必須滿足的性質(zhì)，但如果沒(méi)有這個(gè)性質(zhì)，那么動(dòng)態(tài)規(guī)劃法相比其他的算法不具備優(yōu)越性。因此，在使用動(dòng)態(tài)規(guī)劃法時(shí)，從邊界條件開(kāi)始將某子問(wèn)題的最優(yōu)解求出并保存起來(lái)，然后利用它來(lái)求解依賴它的其他子問(wèn)題，直到求出整個(gè)問(wèn)題的解。4.3動(dòng)態(tài)規(guī)劃基本思想與優(yōu)化原則4.4.1動(dòng)態(tài)規(guī)劃的典型實(shí)例——背包問(wèn)題1.問(wèn)題描述給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的承重量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中的物品重量在不超過(guò)C的前提下，總價(jià)值最大？在第2章中，假定每件物品至多只能裝一個(gè)，所以所裝的第i件物品xi=0或1，是一個(gè)0-1背包問(wèn)題?，F(xiàn)在問(wèn)題是每件物品可以裝多個(gè)，但仍然不能分割只裝一部分，此時(shí)就是一個(gè)整數(shù)規(guī)劃問(wèn)題。2.問(wèn)題分析（1）不難驗(yàn)證該背包問(wèn)題滿足優(yōu)化原則和無(wú)后效性，可以使用動(dòng)態(tài)規(guī)劃法求解。（2）按照所裝物品種類來(lái)劃分階段，規(guī)定第i階段可以選擇新裝進(jìn)第i件物品，比如第1階段只能選擇裝第1種物品，第2階段可以選擇裝前兩種物品，……，第k階段可以選擇裝前k種物品，以此下去，最后一階段可以選擇裝入全部的物品，此時(shí)的最優(yōu)解就是背包問(wèn)題的解。4.4.1動(dòng)態(tài)規(guī)劃的典型實(shí)例——背包問(wèn)題

4.4.1動(dòng)態(tài)規(guī)劃的典型實(shí)例——背包問(wèn)題3.實(shí)例計(jì)算：設(shè)v1=1，v2=3，v3=5，v4=9；w1=2，w2=3，w3=4，w4=7;C=10。構(gòu)建遞推計(jì)算的備忘錄，根據(jù)優(yōu)化函數(shù)計(jì)算過(guò)程如下：現(xiàn)在還有一個(gè)問(wèn)題是如何得到這個(gè)最大價(jià)值12，也就是如何裝物品。4.4.1動(dòng)態(tài)規(guī)劃的典型實(shí)例——背包問(wèn)題ky1234567891010112233445201334667993013556810101140135569101012

4.4.1動(dòng)態(tài)規(guī)劃的典型實(shí)例——背包問(wèn)題

4.4.1動(dòng)態(tài)規(guī)劃的典型實(shí)例——背包問(wèn)題ky1234567891010111111111201222222223012333333340123334344

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題3.算法設(shè)計(jì)算法LCS(X,Y,m,n) else//最后一個(gè)字符不同時(shí) ifC[i-1,j]>C[i,j-1]then //滿足情況（2） C[i,j]←C[i-1,j] B[i,j]←‘↑’ endif else //滿足情況（3） C[i,j]←C[i,j-1] B[i,j]←‘←’ end end endforendfor

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題4.實(shí)例計(jì)算：設(shè)X=<1,3,5,4,2,6,7,8>，Y=<1,4,8,6,7,5>，其中m=8，n=6。構(gòu)建遞推計(jì)算的備忘錄，根據(jù)優(yōu)化函數(shù)計(jì)算過(guò)程如下：4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題ij0123456000000001011111120111111301111124012222250122222601223337012234480123344

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題根據(jù)以上遞推得下表：下面給出求解的追蹤過(guò)程：B[8,6]→B[8,5]→B[7,5]→B[6,4]→B[5,3]→B[5,2]→B[4,2]→B[3,1]→B[2,1]→B[1,1]，其中B[7,5]，B[6,4]，B[4,2]，B[1,1]的值為↖，也就是第①種情況，此時(shí)應(yīng)該將對(duì)應(yīng)的字符加入最長(zhǎng)公共子序列中，即為<1,4,6,7>。4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題ij1234561↖←←←←←2↑←←←←←3↑←←←←↖4↑↖←←←←5↑↑←←←←6↑↑←↖←←7↑↑←↑↖←8↑↑↖←↑←6.算法效率分析在算法LCS中，兩重for循環(huán)時(shí)間復(fù)雜度為，在算法TrackSolution中，最多標(biāo)記m+n次，時(shí)間復(fù)雜度為。因此，綜合起來(lái)整個(gè)算法的時(shí)間復(fù)雜度為，它從蠻力法的降至，可見(jiàn)在求解這個(gè)問(wèn)題中動(dòng)態(tài)規(guī)劃法的優(yōu)越性。

4.4.2動(dòng)態(tài)規(guī)劃的典型實(shí)例——最長(zhǎng)公共子序列問(wèn)題

4.4.3動(dòng)態(tài)規(guī)劃的典型實(shí)例——最大字段和問(wèn)題

4.4.3動(dòng)態(tài)規(guī)劃的典型實(shí)例——最大字段和問(wèn)題

4.4.3動(dòng)態(tài)規(guī)劃的典型實(shí)例——最大字段和問(wèn)題

4.4.3動(dòng)態(tài)規(guī)劃的典型實(shí)例——最大字段和問(wèn)題3.算法設(shè)計(jì)算法MaxConSubSeqSum_DP(A[],n)輸入：序列A[1..n]輸出：最大子段和maxSum，對(duì)應(yīng)的開(kāi)始和結(jié)束位置begin和endmaxSum←-INFb←

0//b是前一個(gè)最大子段和fori←

1tondo ifb>0then //情況（1），應(yīng)續(xù)上A[i] b←b+A[i] endif else //情況（2），應(yīng)拋棄A[1..i-1]的最大子段，重新開(kāi)始選取子段 b←A[i] t←

i //記錄重新開(kāi)始的位置 end

4.4.3動(dòng)態(tài)規(guī)劃的典型實(shí)例——最大字段和問(wèn)題3.算法設(shè)計(jì) ifb>maxSumthen//選取C[1],...C[i-1]中最大的子段和 maxSum←b begin←

t end←

i endifendfor4.4.3動(dòng)態(tài)規(guī)劃的典型實(shí)例——最大字段和問(wèn)題4.實(shí)例計(jì)算：設(shè)A=<2,-3,5,9,-2,1>。構(gòu)建遞推計(jì)算的備忘錄，根據(jù)優(yōu)化函數(shù)計(jì)算過(guò)程如下：C[1]=A[1]=2>0→C[2]=C[1]+A[2]=2-3=-1<0→C[3]=A[3]=5>0→C[4]=C[3]+A[4]=5+9=14>0→C[5]=C[4]+A[5]=14-2=12>0→C[6]=C[5]+1=13。設(shè)立追蹤解的標(biāo)記函數(shù)B[i]，當(dāng)C[i]>0