第3章算法設(shè)計(jì)PPT.ppt

1、1,第3章 動(dòng)態(tài)規(guī)劃,2,學(xué)習(xí)要點(diǎn): 理解動(dòng)態(tài)規(guī)劃算法的概念。 掌握動(dòng)態(tài)規(guī)劃算法的基本要素 （1）最優(yōu)子結(jié)構(gòu)性質(zhì) （2）重疊子問題性質(zhì) 掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。 (1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 (2)遞歸地定義最優(yōu)值。 (3)以自底向上的方式計(jì)算出最優(yōu)值。 (4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。,3,通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。 （1）矩陣連乘問題； （2）最長(zhǎng)公共子序列； （3）最大子段和 （4）凸多邊形最優(yōu)三角剖分； （5）多邊形游戲； （6）圖像壓縮； （7）電路布線； （8）流水作業(yè)調(diào)度； （9）背包問題； （10）最優(yōu)二叉搜索樹。,4,動(dòng)態(tài)規(guī)劃算法與

2、分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題,算法總體思想,5,但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。,算法總體思想,6,如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。,算法總體思想,T(n),7,動(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)解。,8,（1）單個(gè)矩陣是完全加括號(hào)的； （2）矩陣連乘積 是完全加括號(hào)的，則 可 表示為2

3、個(gè)完全加括號(hào)的矩陣連乘積 和 的乘積并加括號(hào)，即,16000, 10500, 36000, 87500, 34500,完全加括號(hào)的矩陣連乘積可遞歸地定義為： 設(shè)有四個(gè)矩陣 ，它們的維數(shù)分別是： 總共有五中完全加括號(hào)的方式,完全加括號(hào)的矩陣連乘積,9,矩陣連乘問題,給定n個(gè)矩陣 ， 其中 與 是可乘的， ?？疾爝@n個(gè)矩陣的連乘積 由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。 若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,10,矩陣連乘問題,給定n個(gè)矩陣A

4、1,A2,An，其中Ai與Ai+1是可乘的，i=1，2，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。,窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。,算法復(fù)雜度分析： 對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。 由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：,11,矩陣連乘問題,窮舉法 動(dòng)態(tài)規(guī)劃,將矩陣連乘積 簡(jiǎn)記為Ai:j ，這里ij,考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和Ak+1

5、之間將矩陣鏈斷開，ikj，則其相應(yīng)完全 加括號(hào)方式為,計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上 Ai:k和Ak+1:j相乘的計(jì)算量,12,特征：計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 Ai:k和Ak+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),13,建立遞歸關(guān)系,設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n 當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,n 當(dāng)ij時(shí)， 可以遞歸地定義

6、mi,j為：,這里 的維數(shù)為,的位置只有 種可能,14,計(jì)算最優(yōu)值,對(duì)于1ijn不同的有序?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í)間的算法,15,用動(dòng)態(tài)規(guī)劃法求最優(yōu)解,void MatrixChain(int *p，int n，int *m，int *s) for (int i =

7、 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,算法復(fù)雜度分析： 算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此

8、算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。,16,動(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ī)劃算法求解的前提。,同一個(gè)問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的

9、維度低）,17,動(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í)間，從而獲得較高的解題效率。,18,動(dòng)態(tài)規(guī)劃算法的基本要素,三、備忘錄方法,備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。,int L

10、ookupChain(int i，int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; ,19,關(guān)于動(dòng)態(tài)規(guī)劃算法和備忘錄方法的適用條件,綜上所述，矩陣連

11、乘積的最優(yōu)計(jì)算次序問題可用自頂向下的備忘錄方法或自底向上的動(dòng)態(tài)規(guī)劃算法在O(n3)計(jì)算時(shí)間內(nèi)求解。 這兩個(gè)算法都利用了子問題重疊性質(zhì)。總共有(n2)個(gè)不同的子問題，對(duì)每個(gè)子問題兩種算法都只解一次并記錄答案。當(dāng)再次遇到該子問題時(shí)，簡(jiǎn)單地取用已得到的答案，節(jié)省了計(jì)算量，提高了算法的效率。 適用條件：一般來說，當(dāng)一個(gè)問題的所有子問題都至少要解一次時(shí)，用動(dòng)態(tài)規(guī)劃算法比用備忘錄方法好。此時(shí)，動(dòng)態(tài)規(guī)劃算法沒有任何多余的計(jì)算，還可以利用其規(guī)則的表格存取方式來減少在動(dòng)態(tài)規(guī)劃算法中的計(jì)算時(shí)間和空間需求。當(dāng)子問題空間中部分子問題可以不必求解時(shí)，易用備忘錄方法則較為有利，因?yàn)閺钠淇刂平Y(jié)構(gòu)可以看出，該方法只解那些確實(shí)

12、需要求解的子問題。,20,最長(zhǎng)公共子序列,若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。 給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。 給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長(zhǎng)公共子序列。,21,22,最長(zhǎng)公共子序列的結(jié)構(gòu),設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為

13、Z=z1,z2,zk ，則 (1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。 (2)若xmyn且zkxm，則Z是xm-1和Y的最長(zhǎng)公共子序列。 (3)若xmyn且zkyn，則Z是X和yn-1的最長(zhǎng)公共子序列。,由此可見，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,23,子問題的遞歸結(jié)構(gòu),由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)

14、公共子序列。故此時(shí)Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：,24,計(jì)算最優(yōu)值,由于在所考慮的子問題空間中，總共有(mn)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。,void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; ,構(gòu)造最長(zhǎng)公共子序列 void LCS(int i，int j，char *x，int *b) if (i =0 | j=0

15、) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); ,25,算法的改進(jìn),在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個(gè)值所確定的。 如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算

16、cij時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。,26,3.4 最大子段和,問題描述： 給定由n個(gè)整數(shù)（包含負(fù)整數(shù)）組成的序列a1,a2,.,an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負(fù)值時(shí)定義其最大子段和為0。 依此定義，所求的最優(yōu)值為： 例如，當(dāng)(a1,a2, a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)時(shí)，最大子段和為：,27,1. 一個(gè)簡(jiǎn)單算法,一個(gè)簡(jiǎn)單算法： int MaxSum(int n, a, 算法有3重循環(huán)，復(fù)雜性為O(n3)。,由于有： 算法可作

17、如下改進(jìn)： int MaxSum(int n, a, 改進(jìn)后的算法復(fù)雜性為O(n2) 。,28,2. 分治方法求解,從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解： 如果將所給的序列a1:n分為長(zhǎng)度相等的兩段a1:n/2和an/2+1:n，分別求出這兩段的最大子段和，則a1:n的最大子段和有三種情形： a1:n的最大子段和與a1:n/2的最大子段和相同； a1:n的最大子段和與an/2+1:n的最大子段和相同； a1:n的最大子段和為下面的形式。 A、B這兩種情形可遞歸求得。對(duì)于情形C，容易看出，an/2與an/2+1在最優(yōu)子序列中。因此，我們可以在a1:n/2和an/2+1:n中分別計(jì)算出

18、如下的s1和s2。則s1+s2即為出現(xiàn)情形C使得最優(yōu)值。 從而設(shè)計(jì)出下面所示的分治算法。,int MaxSubSum(int a, int left, int right) int sum=0; if (left=right)sum=aleft0?aleft:0; elseint center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0; for (int i=center;i=left;i-) lefts+=ai

19、; if (leftss1) s1=lefts; int s2=0;rights=0; for (int i=center+1;is2) s2=rights; sum=s1+s2; if (sumleftsum) sum=leftsum; if (sumsightsum) sum=rightsum; return sum; ,29,3. 動(dòng)態(tài)規(guī)劃方法求解,在對(duì)上述分治算法的分析中我們注意到， 由bj的定義易知，當(dāng)bj-10時(shí)bj=bj-1+aj，否則bj=aj。由此可得計(jì)算bj的動(dòng)態(tài)規(guī)劃遞歸式bj=maxbj-1+aj，aj，1jn。 據(jù)此，可設(shè)計(jì)出求最大子段和的動(dòng)態(tài)規(guī)劃算法如下： int M

20、axSum(int n, int a) int sum=0; b=0; for (i=1;i0) b+=ai; else b=ai; if (bsum) sum=b; return sum; 顯然該算法的計(jì)算時(shí)間為O(n)。,30,4. 算法的推廣,最大矩陣和問題，略 最大m子段和問題，略,31,0-1背包問題,給定n種物品U=u1,u2,un和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大? 0-1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題。,32,mi,j是下面兩個(gè)量的最大值,mi-1,j:僅用最優(yōu)方法取自u(píng)1,u2,ui-1的物品去裝入體積為j的背包所得到的價(jià)值最大值,mi-1,j-wi:用最優(yōu)方法取自u(píng)1,u2,ui-1的物品去裝入體積為j-wi的背包所得到的價(jià)值最大值加上vi,33,Knapsack(int v,int w,int c,int n,int m) for (i=0;in;i+) mi0=0; for (j=0;jc;j+) m0j=0; for (i=1;in;i+) for(j=1;jc;j+) mij=mi-1j if (wi=j