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

算法分析與設(shè)計(jì)課件動(dòng)態(tài)規(guī)劃法1第一頁，共一百三十八頁，2022年，8月28日通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。（1）矩陣連乘問題；（2）最長公共子序列；（3）最大子段和（4）凸多邊形最優(yōu)三角剖分；（5）多邊形游戲；（6）圖像壓縮；（7）電路布線；（8）流水作業(yè)調(diào)度；（9）背包問題；（10）最優(yōu)二叉搜索樹。2第二頁，共一百三十八頁，2022年，8月28日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)動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。算法總體思想3第三頁，共一百三十八頁，2022年，8月28日如果能夠保存已解決的子問題的答案，而在需要時(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)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)4第四頁，共一百三十八頁，2022年，8月28日動(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)解。5第五頁，共一百三十八頁，2022年，8月28日假定A為100×1矩陣,B為1×100矩陣，C為100×1矩陣,(A*B)*C需乘法數(shù)為100×1×100＋100×100×1＝20000而

A*(B*C)所需乘法數(shù)為1×100×1＋100×1×1＝200長度q的矩陣乘法鏈有指數(shù)量級(jí)Ω(2n)的可能的相乘方式(有q個(gè)葉節(jié)點(diǎn)的二叉數(shù)的數(shù)目).要找一種相乘方式,使得元素乘法數(shù)最少6第六頁，共一百三十八頁，2022年，8月28日16000,10500,36000,87500,34500完全加括號(hào)的矩陣連乘積可遞歸地定義為：（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積A是完全加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘積A和B的乘積并加括號(hào)，即A=(BC)設(shè)有四個(gè)矩陣A,B,C,D，它們的維數(shù)分別是：矩陣連乘積總共有五中完全加括號(hào)的方式7第七頁，共一百三十八頁，2022年，8月28日給定n個(gè)矩陣，其中與是可乘的?？疾爝@n個(gè)矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積8第八頁，共一百三十八頁，2022年，8月28日給定n個(gè)矩陣｛A1,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+1…An)可以得到關(guān)于P(n)的遞推式如下：9第九頁，共一百三十八頁，2022年，8月28日動(dòng)態(tài)規(guī)劃將矩陣連乘積AiAi+1…Aj，簡(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ì)算量，再加上A[i:k]和A[k+1:j]相乘的計(jì)算量10第十頁，共一百三十八頁，2022年，8月28日特征：計(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)11第十一頁，共一百三十八頁，2022年，8月28日建立遞歸關(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í)，這里的維數(shù)為

的位置只有種可能可以遞歸地定義m[i,j]為：12第十二頁，共一百三十八頁，2022年，8月28日計(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í)間的算法13第十三頁，共一百三十八頁，2022年，8月28日用動(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;}}}}14第十四頁，共一百三十八頁，2022年，8月28日A1A2A3A4A5A6303535151555101020202515第十五頁，共一百三十八頁，2022年，8月28日算法復(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)。16第十六頁，共一百三十八頁，2022年，8月28日動(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)，有些表示方法的求解速度更快（空間占用小，問題的維度低）17第十七頁，共一百三十八頁，2022年，8月28日二、重疊子問題遞歸算法求解問題時(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)式增長。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。18第十八頁，共一百三十八頁，2022年，8月28日intrecmat(inti，intj){if(i==j)return0;intu=recmat(i，i)+recmat(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=recmat(i，k)+recmat(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}19第十九頁，共一百三十八頁，2022年，8月28日三、備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。intLookupChain(inti，intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i，i)+LookupChain(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)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}20第二十頁，共一百三十八頁，2022年，8月28日最長公共子序列若給定序列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的最長公共子序列。21第二十一頁，共一百三十八頁，2022年，8月28日設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。(2)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長公共子序列。由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。22第二十二頁，共一百三十八頁，2022年，8月28日子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：23第二十三頁，共一百三十八頁，2022年，8月28日計(jì)算最優(yōu)值由于在所考慮的子問題空間中，總共有θ(mn)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}24第二十四頁，共一百三十八頁，2022年，8月28日構(gòu)造最長公共子序列voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}j0123456yjBDCABAi0xj1A2B3C4B5D6A7B0000000000000

00011111112211222211223312223312233412234425第二十五頁，共一百三十八頁，2022年，8月28日算法的改進(jìn)在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個(gè)值所確定的。如果只需要計(jì)算最長公共子序列的長度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長公共子序列的長度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。26第二十六頁，共一百三十八頁，2022年，8月28日最大字段和給定由n個(gè)整數(shù)（可能為負(fù)數(shù)）組成的序列a1,a2,…,an，求該序列形如的字段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)，定義其最大字段和為0。所以，所求最優(yōu)值為：例如：當(dāng)（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)時(shí)，最大字段和為27第二十七頁，共一百三十八頁，2022年，8月28日最大字段和的簡(jiǎn)單算法

intmaxsum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){intthissum=0;for(intk=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}O(n3)28第二十八頁，共一百三十八頁，2022年，8月28日最大字段和的簡(jiǎn)單算法改進(jìn)

intmaxsum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}O(n2)29第二十九頁，共一百三十八頁，2022年，8月28日最大字段和的分治算法如果將所給的序列a[1:n]分為長度相等的兩段a[1:n/2]和a[n/2+1:n]，分別求出這兩段的最大字段和，則a[1:n]的最大字段和有三種情形：1、a[1:n]的最大字段和與a[1:n/2]的最大字段和相同；2、a[1:n]的最大字段和與a[n/2+1:n]的最大字段和相同；3、a[1:n]的最大字段和為1<=i<=n/2,n/2+1<=j<=n1,2情形可遞歸求得。對(duì)于3，

在a[1:n/2]計(jì)算出30第三十頁，共一百三十八頁，2022年，8月28日在a[n/2+1:n]計(jì)算出則s1+s2為第3種情形的最優(yōu)解。則分治算法如下：intmaxsubsum(int*a,intleft,intright){intsum=0;If(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=maxsunsum(a,left,center);intrightsum=maxsunsum(a,center+1,right);31第三十一頁，共一百三十八頁，2022年，8月28日ints1=0;intlefts=0;for(inti=center;i>=left;i--){left+=a[i];if(left>s1)s1=left;}ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}returnsum;}32第三十二頁，共一百三十八頁，2022年，8月28日時(shí)間復(fù)雜度：33第三十三頁，共一百三十八頁，2022年，8月28日最大字段和的動(dòng)態(tài)規(guī)劃算法對(duì)于上述分治算法的分析中，若記則所求的最大字段和為：當(dāng)b[j-1]>0時(shí)，b[j]=b[j-1]+a[j]，否則b[j]=a[j]。由此可得動(dòng)態(tài)規(guī)劃遞歸式：

b[j]=max{b[j-1]+a[j],a[j]}，1<=j<=n34第三十四頁，共一百三十八頁，2022年，8月28日最大字段和的動(dòng)態(tài)規(guī)劃算法intmaxsum(intn,int*a){intsum=0,b=0;for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;O(n)}35第三十五頁，共一百三十八頁，2022年，8月28日求任意一對(duì)頂點(diǎn)的最短路徑---弗羅伊德(Floyd)算法設(shè)圖g用鄰接矩陣法表示，求圖g中任意一對(duì)頂點(diǎn)vi、vj間的最短路徑。1.將vi到vj的最短的路徑長度初始化為g.arcs[i][j]，然后進(jìn)行如下n次比較和修正：2.在vi、vj間加入頂點(diǎn)v0，比較（vi,v0,vj）和(vi,vj)的路徑長度，取其中較短的路徑作為vi到vj的且中間頂點(diǎn)號(hào)不大于0的最短路徑。

36第三十六頁，共一百三十八頁，2022年，8月28日3.在vi、vj間加入頂點(diǎn)v1，得（vi,…，v1）和(v1,…，vj)，其中（vi,…,v1）是vi到v1的且中間頂點(diǎn)號(hào)不大于0的最短路徑，

(v1,…,vj)是v1到vj的且中間頂點(diǎn)號(hào)不大于0的最短路徑，這兩條路徑在上一步中已求出。將（vi,…,v1,…,vj）與上一步已求出的且vi到vj中間頂點(diǎn)號(hào)不大于0的最短路徑比較，取其中較短的路徑作為vi到vj的且中間頂點(diǎn)號(hào)不大于1的最短路徑。

37第三十七頁，共一百三十八頁，2022年，8月28日4.在vi、vj間加入頂點(diǎn)v2，得（vi,…,v2）和(v2,…,vj)，其中（vi,…,v2）是vi到v2的且中間頂點(diǎn)號(hào)不大于1的最短路徑

(v2,…,vj)

是v2到vj的且中間頂點(diǎn)號(hào)不大于1的最短路徑，這兩條路徑在上一步中已求出。將（vi,…,v2,…,vj）與上一步已求出的且vi到vj中間頂點(diǎn)號(hào)不大于1的最短路徑比較，取其中較短的路徑作為vi到vj的且中間頂點(diǎn)號(hào)不大于2的最短路徑。依次類推，經(jīng)過n次比較和修正，在第（n-1）步，將求得vi到vj的且中間頂點(diǎn)號(hào)不大于n-1的最短路徑，這必是從vi到vj的最短路徑。按此方法可求得各對(duì)頂點(diǎn)間的最短路徑。38第三十八頁，共一百三十八頁，2022年，8月28日現(xiàn)定義一個(gè)n階方陣序列。

A(-1)，A(0)，A(1)，…，A(k)，…，A(n-1)

其中

A(-1)[i][j]=G.arcs[i][j]

A(k)[i][j]=Min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}0≦k≦n-1

從上述計(jì)算公式可見，A(1)[i][j]是從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑的長度；A(k)[i][j]是從vi到vj的中間頂點(diǎn)的個(gè)數(shù)不大于k的最短路徑的長度；A(n-1)[i][j]就是從vi到vj的最短路徑的長度。由此得到求任意兩頂點(diǎn)間的最短路徑的算法。39第三十九頁，共一百三十八頁，2022年，8月28日voidFloyd(MgraphG,PathMatrix*P[],DistancMatrix*A){/*用Floyd算法求有向網(wǎng)G中各對(duì)頂點(diǎn)v和w之間的最短路徑P[v][w]及其帶權(quán)長度D[v][w]。

/*若P[v][w][u]為1，則u是從v到w當(dāng)前求得的最短路徑上的頂點(diǎn)。*/

for(v=0;v<G.vexnum;++v)/*各對(duì)頂點(diǎn)之間初始已知路徑及距離*/

for(w=0;w<G.vexnum;++w)

{

A[v][w]=G.arcs[v][w];

for(u=0;u<G.vexnum;++u)P[v][w][u]=0;

if(A[v][w]<INFINITY)/*從v到w有直接路徑*/

{P[v][w][v]=1;

}

}40第四十頁，共一百三十八頁，2022年，8月28日

for(u=0;u<G.vexnum;++u)

for(v=0;v<G.vexnum;++v)

for(w=0;w<G.vexnum;++w)

if(A[v][u]+A[u][w]<A[v][w])/*從v經(jīng)u到w的一條路徑更短*/

{

A[v][w]=A[v][u]+A[u][w];

for(i=0;i<G.vexnum;++i)

P[v][w][i]=P[v][u][i]||P[u][w][i];

}

}/*Floyd*/圖7.20給出了一個(gè)簡(jiǎn)單的有向網(wǎng)及其鄰接矩陣。圖7.21給出了用Floyd算法求該有向網(wǎng)中每對(duì)頂點(diǎn)之間的最短路徑過程中，數(shù)組D和數(shù)組P的變化情況。41第四十一頁，共一百三十八頁，2022年，8月28日42第四十二頁，共一百三十八頁，2022年，8月28日43第四十三頁，共一百三十八頁，2022年，8月28日凸多邊形最優(yōu)三角剖分用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P={v0,v1,…,vn-1}表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。44第四十四頁，共一百三十八頁，2022年，8月28日三角剖分的結(jié)構(gòu)及其相關(guān)問題一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語法樹。例如，完全加括號(hào)的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語法樹如圖(a)所示。

矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，i<j，對(duì)應(yīng)于矩陣連乘積A[i+1:j]。一般情況下，一個(gè)凸邊形的三角剖分對(duì)應(yīng)于一棵有n-1個(gè)葉結(jié)點(diǎn)的語法樹。凸多邊形{v0,v1,…vn-1}的三角剖分也可以用語法樹表示。例如，圖(b)中凸多邊形的三角剖分可用圖(a)所示的語法樹表示。45第四十五頁，共一百三十八頁，2022年，8月28日最優(yōu)子結(jié)構(gòu)性質(zhì)凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若凸(n+1)邊形P={v0,v1,…,vn-1}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和?？梢詳嘌?，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衶v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。46第四十六頁，共一百三十八頁，2022年，8月28日最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義t[i][j]，1≤i<j≤n為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見，設(shè)退化的多邊形{vi-1,vi}具有權(quán)值0。據(jù)此定義，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t[1][n]。t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i≥1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，t[i][j]的值應(yīng)為t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的權(quán)值，其中i≤k≤j-1。由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使t[i][j]值達(dá)到最小的位置。由此，t[i][j]可遞歸地定義為：47第四十七頁，共一百三十八頁，2022年，8月28日計(jì)算最優(yōu)值

template<classtype>voidminweighttriangulation(intn,type**t,int**s){for(inti=1;i<=n;i++)t[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++){intj=I+r-1;t[i][j]=t[i+1][j]+w(i-1,i,j);s[i][j]=I;for(intk=i+1;k<=i+r+1;k++){intu=t[i][k]+t[k+1][j]+w(i-1,k,j);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}}占用空間：耗時(shí)：48第四十八頁，共一百三十八頁，2022年，8月28日多邊形游戲多邊形游戲是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號(hào)。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2；(2)用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)值通過邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。問題:對(duì)于給定的多邊形，計(jì)算最高得分。49第四十九頁，共一百三十八頁，2022年，8月28日最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)所給的多邊形的頂點(diǎn)和邊的順時(shí)針序列為：op[1],v[1],op[2],v[2],…,op[n],v[n]其中，op[i]表示第I條邊所對(duì)應(yīng)的運(yùn)算符，v[i]表示第i個(gè)頂點(diǎn)上的數(shù)值。在所給多邊形中，從頂點(diǎn)i(1≤i≤n)開始，長度為j(鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p(i，j)可表示為v[i]，op[i+1]，…，v[i+j-1]。如果這條鏈的最后一次合并運(yùn)算在op[i+s]處發(fā)生(1≤s≤j-1)，則可在op[i+s]處將鏈分割為2個(gè)子鏈p(i，s)和p(i+s，j-s)。設(shè)m1是對(duì)子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有a≤m1≤b，c≤m2≤d50第五十頁，共一百三十八頁，2022年，8月28日由于子鏈p(i,s)和p(i+s,j-s)的合并方式?jīng)Q定了p(i,j)在op[i+s]處斷開后的合并方式，在op[i+s]處合并后其值為：

m=(m1)op[i+s](m2)(1)當(dāng)op[i+s]='+'時(shí)，顯然有a+c≤m≤b+d(2)當(dāng)op[i+s]=‘*’時(shí)，由于v[i]可能取負(fù)值，子鏈的最大值相乘未必得到主鏈的最大值。但有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd}換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。例如：當(dāng)m=ac時(shí)，最大主鏈由它的兩條最小子鏈組成；同理當(dāng)m=bd時(shí)，最大主鏈由它的兩條最大子鏈組成。51第五十一頁，共一百三十八頁，2022年，8月28日遞歸求解為了求鏈合并的最大值，必須同時(shí)求子鏈合并的最大值和最小值。因此，在整個(gè)計(jì)算過程中，應(yīng)同時(shí)計(jì)算最大值和最小值。設(shè)m[i,j,0]是鏈p(i,j)合并的最小值，而m[i,j,1]是最大值。若最優(yōu)合并在op[i+s]處將p(i,j)分為2個(gè)長度小于j的子鏈p(i,i+s)和p(i+s,j-s),且從頂點(diǎn)i開始的長度小于j的子鏈的最大值和最小值均已計(jì)算出。記為：

a=m[i,i+s,0],b=m[i,i+s,1],c=m[i+s,j-s,0],d=m[i+s,j-s,1],(1)當(dāng)op[i+s]=‘+’時(shí)，m[i,j,0]=a+cm[i,j,1]=b+d(2)當(dāng)op[i+s]=‘*’時(shí)m[i,j,0]=min{ac,ad,bc,bd}m[i,j,1]=max{ac,ad,bc,bd}

因此，將p(i,j)在op[i+s]處斷開的最大值為：52第五十二頁，共一百三十八頁，2022年，8月28日53第五十三頁，共一百三十八頁，2022年，8月28日VoidMIN_MAX(intn,inti,intj,int&minf,int&maxf){inte[4];inta=m[i][s][0],b=m[i][s][1],r=(i+s-1)%n+1,c=m[r][j-s][0],d=m[r][j-s][0];if(op[r]==‘t’){minf=a+c;maxf=b+d;}else{e[1]=a*c;e[2]=a*d;e[3]=b*c;e[4]=b*d;maxf=e[1];minf=e[1];for(intr=2;r<5;r++){if(minf>e[r])minf=e[r];if(maxf<e[r])maxf=e[r];}}}算法描述54第五十四頁，共一百三十八頁，2022年，8月28日intpoly_max(intn){intminf,maxf;for(intj=2;j<=n;j++)for(inti=1;i<=n;i++)for(ints=1;s<j;s++){MIN_MAX(n,i,s,j,minf,maxf,m,op);if(m[i][j][0]>minf)m[i][j][0]=minf;if(m[i][j][1]<maxf)m[i][j][1]=maxf;}inttemp=m[1][n][1];for(inti=2;i<=n;i++)if(temp<m[i][n][1])temp=m[i][n][1];returntemp;}時(shí)間：55第五十五頁，共一百三十八頁，2022年，8月28日?qǐng)D像壓縮圖象的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列{p1,p2,…,pn},0≤pi≤255分割成m個(gè)連續(xù)段S1,S2,…,Sm。第i個(gè)象素段Si中(1≤i≤m)，有l(wèi)[i]個(gè)象素,且該段中每個(gè)象素都只用b[i]位表示。設(shè)則第i個(gè)象素段Si為設(shè)，則hib[i]8。因此需要用3位表示b[i],如果限制1l[i]255，則需要用8位表示l[i]。因此，第i個(gè)象素段所需的存儲(chǔ)空間為l[i]*b[i]+11位。按此格式存儲(chǔ)象素序列{p1,p2,…,pn}，需要位的存儲(chǔ)空間。

56第五十六頁，共一百三十八頁，2022年，8月28日?qǐng)D象壓縮問題要求確定象素序列{p1,p2,…,pn}的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長度不超過256位。

設(shè)l[i]，b[i]，是{p1,p2,…,pn}的最優(yōu)分段。顯而易見，l[1]，b[1]是{p1,…,pl[1]}的最優(yōu)分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最優(yōu)分段。即圖象壓縮問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)s[i]，1≤i≤n，是象素序列{p1,…,pn}的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知：圖像壓縮其中57第五十七頁，共一百三十八頁，2022年，8月28日?qǐng)D像壓縮voidcompree(intn,intp[],ints[],intl[],intb[]){intLmax=256,header=11;s[0]=0;for(inti=1;i<=n;i++){b[i]=length(p[i]);intbmax=b[i];s[i]=s[i-1]+bmax;l[i]=1;for(intj=2;j<=I&&j<=Lmax;j++){if(bmax<b[i-j+1])bmax=b[I-j+1];if(s[i]>s[i-j]+j*bmax]){s[i]=s[i-j]+j*bmax];l[i]=j;}}s[i]+=header;}}Intlength(inti){intk=1;i=i/2;while(i>0){k++;i=i/2;}returnk;}58第五十八頁，共一百三十八頁，2022年，8月28日算法復(fù)雜度分析：由于算法compress中對(duì)k的循環(huán)次數(shù)不超這256，故對(duì)每一個(gè)確定的i，可在時(shí)間O(1)內(nèi)完成的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為O(n)。圖像壓縮59第五十九頁，共一百三十八頁，2022年，8月28日電路布線在一塊電路板的上、下2端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是{1,2,…,n}的一個(gè)排列。導(dǎo)線(i,π(i))稱為該電路板上的第i條連線。對(duì)于任何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。

電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。60第六十頁，共一百三十八頁，2022年，8月28日記。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)當(dāng)i=1時(shí)，

(2)當(dāng)i>1時(shí)，

a)j<π(i)。此時(shí)，，故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。b)j≥π(i)，若(i,π(i))∈MNS(i,j)，則對(duì)任意(t,π(t))∈MNS(i,j)有t<i且π(t)<π(i)。在這種情況下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。61第六十一頁，共一百三十八頁，2022年，8月28日(1)當(dāng)i=1時(shí)(2)當(dāng)i>1時(shí)c）若，則對(duì)任意(t,π(t))∈MNS(i,j)有t<i。從而。因此，Size(i,j)≤Size(i-1,j)。另一方面，故又有Size(i,j)≥Size(i-1,j)，從而Size(i,j)=Size(i-1,j)。綜上可知，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。遞歸計(jì)算最優(yōu)值：最優(yōu)值為Size(n,n)空間：耗時(shí)：62第六十二頁，共一百三十八頁，2022年，8月28日流水作業(yè)調(diào)度n個(gè)作業(yè){1，2，…，n}要在由2臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。63第六十三頁，共一百三十八頁，2022年，8月28日分析：直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般情況下，機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種情況。設(shè)全部作業(yè)的集合為N={1，2，…，n}。SN是N的作業(yè)子集。在一般情況下，機(jī)器M1開始加工S中作業(yè)時(shí)，機(jī)器M2還在加工其它作業(yè)，要等時(shí)間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時(shí)間記為T(S,t)。流水作業(yè)調(diào)度問題的最優(yōu)值為T(N,0)。64第六十四頁，共一百三十八頁，2022年，8月28日設(shè)是所給n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度，它所需的加工時(shí)間為a(1)+T’。其中T’是在機(jī)器M2的等待時(shí)間為b(1)時(shí)，安排作業(yè)(2)，…，(n)所需的時(shí)間。記S=N-{(1)}，則有T’=T(S,b(1))。證明：事實(shí)上，由T的定義知T’T(S,b(1))。若T’>T(S,b(1))，設(shè)’是作業(yè)集S在機(jī)器M2的等待時(shí)間為b(1)情況下的一個(gè)最優(yōu)調(diào)度。則(1)，’(2)，…，’(n)是N的一個(gè)調(diào)度，且該調(diào)度所需的時(shí)間為a(1)+T(S,b(1))<a(1)+T’。這與是N的最優(yōu)調(diào)度矛盾。故T’T(S,b(1))。從而T’=T(S,b(1))。這就證明了流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。65第六十五頁，共一百三十八頁，2022年，8月28日由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，遞歸計(jì)算最優(yōu)值其中，max{t-ai,0},由于作業(yè)在機(jī)器M2上，作業(yè)i必須在max{t,ai}時(shí)間之后才能開工。因此，在機(jī)器M1上完成作業(yè)之之后，在機(jī)器上還需：

bi+max{t,ai}-ai=bi+max{t-ai,0}時(shí)間才能完成對(duì)作業(yè)i的加工。對(duì)遞歸式的深入分析表明，算法可進(jìn)一步得到簡(jiǎn)化。66第六十六頁，共一百三十八頁，2022年，8月28日J(rèn)ohnson不等式設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若(1)=i,(2)=j。則由動(dòng)態(tài)規(guī)劃遞歸式可得:

T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij)其中，如果作業(yè)i和j滿足min{bi,aj}≥min{bj,ai}，則稱作業(yè)i和j滿足Johnson不等式。若作業(yè)i和j不滿足Johnson不等式，則交換作業(yè)i和j的加工順序后，則作業(yè)i和j滿足Johnson不等式。67第六十七頁，共一百三十八頁，2022年，8月28日交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另一調(diào)度，它所需的加工時(shí)間為T’(S,t)=ai+aj+T(S-{i,j},tji)其中，當(dāng)作業(yè)i和j滿足Johnson不等式時(shí)，有68第六十八頁，共一百三十八頁，2022年，8月28日由此可見當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時(shí)，交換它們的加工順序后，不增加加工時(shí)間。對(duì)于流水作業(yè)調(diào)度問題，必存在最優(yōu)調(diào)度，使得作業(yè)(i)和(i+1)滿足Johnson不等式。進(jìn)一步還可以證明，調(diào)度滿足Johnson法則當(dāng)且僅當(dāng)對(duì)任意i<j有由此可知，所有滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。

69第六十九頁，共一百三十八頁，2022年，8月28日算法描述流水作業(yè)調(diào)度問題的Johnson算法(1)令(2)將N1中作業(yè)依ai的非減序排序；將N2中作業(yè)依bi的非增序排序；(3)N1中作業(yè)接N2中作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度。算法復(fù)雜度分析：算法的主要計(jì)算時(shí)間花在對(duì)作業(yè)集的排序。因此，在最壞情況下算法所需的計(jì)算時(shí)間為O(nlogn)。所需的空間為O(n)。70第七十頁，共一百三十八頁，2022年，8月28日0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?0-1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題。71第七十一頁，共一百三十八頁，2022年，8月28日在0/1背包問題中，需對(duì)容量為c的背包進(jìn)行裝載。從n個(gè)物品中選取裝入背包的物品，每件物品i的重量為wi，價(jià)值為pi。對(duì)于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1

72第七十二頁，共一百三十八頁，2022年，8月28日設(shè)所給0-1背包問題的子問題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。73第七十三頁，共一百三十八頁，2022年，8月28日intknapSack(intn,intc,intw[],intv[],intm[6][N],intx[]){intjmax=min(w[n]-1,c);for(intj=0;i<=jmax;j++)

m[n][j]=0;for(intj=w[n];j<=c;j++)

m[n][j]=v[n];for(inti=n-1;i>1;i--)

{jmax=min(w[i]-1,c);for(j=0;j<=jmax;j++)m[i][j]=m[i+1][j];

for(j=w[i]0;j<=c;j++)

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

}

m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

}

74第七十四頁，共一百三十八頁，2022年，8月28日……for(inti=1;i<n;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c=c-w[i];}

x[n]=(m[n][c]?1:0)

M[1][c]為最優(yōu)解

eg:n=5;c=10;W={2,2,6,5,4}V={6,3,5,4,6}75第七十五頁，共一百三十八頁，2022年，8月28日算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c>2n時(shí)，算法需要Ω(n2n)計(jì)算時(shí)間。算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c>2n時(shí)，算法需要Ω(n2n)計(jì)算時(shí)間。76第七十六頁，共一百三十八頁，2022年，8月28日由m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1≤i≤n)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。如圖所示。對(duì)每一個(gè)確定的i(1≤i≤n)，用一個(gè)表p[i]存儲(chǔ)函數(shù)m(i，j)的全部跳躍點(diǎn)。表p[i]可依計(jì)算m(i，j)的遞歸式遞歸地由表p[i+1]計(jì)算，初始時(shí)p[n+1]={(0，0)}。77第七十七頁，共一百三十八頁，2022年，8月28日n=3，c=6，w={4，3，2}，v={5，2，1}。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)78第七十八頁，共一百三十八頁，2022年，8月28日函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運(yùn)算得到的。因此，函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集p[i+1]與函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集q[i+1]的并集中。易知，(s,t)q[i+1]當(dāng)且僅當(dāng)wisc且(s-wi,t-vi)p[i+1]。因此，容易由p[i+1]確定跳躍點(diǎn)集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]}

另一方面，設(shè)(a，b)和(c，d)是p[i+1]q[i+1]中的2個(gè)跳躍點(diǎn)，則當(dāng)ca且d<b時(shí)，(c，d)受控于(a，b)，從而(c，d)不是p[i]中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，p[i+1]q[i+1]中的其它跳躍點(diǎn)均為p[i]中的跳躍點(diǎn)。由此可見，在遞歸地由表p[i+1]計(jì)算表p[i]時(shí)，可先由p[i+1]計(jì)算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點(diǎn)得到表p[i]。算法改進(jìn)79第七十九頁，共一百三十八頁，2022年，8月28日n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始時(shí)p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6](w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5](w4,v4)={(5,4),(9,10)}。從跳躍點(diǎn)集p[5]與q[5]的并集p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4](6，5)={(6，5)，(10，11)}p[3]={(0，0)，(4，6)，(9，10)，(10，11)}q[3]=p[3](2，3)={(2，3)，(6，9)}p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}q[2]=p[2](2，6)={(2，6)，(4，9)，(6，12)，(8，15)}p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}p[1]的最后的那個(gè)跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。80第八十頁，共一百三十八頁，2022年，8月28日上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集p[i](1≤i≤n)。由于q[i+1]=p[i+1](wi，vi)，故計(jì)算q[i+1]需要O(|p[i+1]|)計(jì)算時(shí)間。合并p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要O(|p[i+1]|)計(jì)算時(shí)間。從跳躍點(diǎn)集p[i]的定義可以看出，p[i]中的跳躍點(diǎn)相應(yīng)于xi,…,xn的0/1賦值。因此，p[i]中跳躍點(diǎn)個(gè)數(shù)不超過2n-i+1。由此可見，算法計(jì)算跳躍點(diǎn)集p[i]所花費(fèi)的計(jì)算時(shí)間為從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1≤i≤n)是整數(shù)時(shí)，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(min{nc,2n})。算法復(fù)雜度分析81第八十一頁，共一百三十八頁，2022年，8月28日最優(yōu)二叉搜索樹二叉搜索樹（1）若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；（2）若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；（3它的左、右子樹也分別為二叉排序樹45125333724100619078在隨機(jī)的情況下，二叉查找樹的平均查找長度和是等數(shù)量級(jí)的82第八十二頁，共一百三十八頁，2022年，8月28日已知二叉搜索樹中每個(gè)節(jié)點(diǎn)的訪問概率，問這棵樹整體的搜索時(shí)間最短是多少（此時(shí)稱為最優(yōu)二叉搜索樹）。例:分別以概率:0.1,0.2,0.4,0.3查找四個(gè)鍵:A,B,C,D.第1棵樹:0.1*1+0.2*2+0.4*3+0.3*4=2.9第2棵樹:0.1*2+0.2*1+0.4*2+0.3*3=2.1那棵是最優(yōu)查找樹?窮舉法不現(xiàn)實(shí):包含n個(gè)鍵的二查樹的總量等于第n個(gè)數(shù)的卡塔蘭數(shù)83第八十三頁，共一百三十八頁，2022年，8月28日設(shè)a1,a2,…,an是從大到小排列的互不相等的鍵，p1,p2,…pn是它們的查找概率。記Tij是由鍵ai,…aj構(gòu)成的二叉樹C[i,j]是在這棵樹中成功查找的最小的平均查找次數(shù)。C[1,n]是我們所要求的結(jié)果。akai…ak-1的最優(yōu)二叉查找樹ak+1…aj的最優(yōu)二叉查找樹84第八十四頁，共一百三十八頁，2022年，8月28日85第八十五頁，共一百三十八頁，2022年，8月28日86第八十六頁，共一百三十八頁，2022年，8月28日課后作業(yè)習(xí)題3-1，3-2，3-3，3-4，3-5，3-6，3-987第八十七頁，共一百三十八頁，2022年，8月28日小結(jié)1、

階段：把問題分成幾個(gè)相互聯(lián)系的有順序的幾個(gè)環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。2、狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。3、決策：從某階段的一個(gè)狀態(tài)演變到下一個(gè)階段某狀態(tài)的選擇。4、狀態(tài)轉(zhuǎn)移方程：前一階段的終點(diǎn)就是后一階段的起點(diǎn)，前一階段的決策選擇導(dǎo)出了后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。動(dòng)態(tài)規(guī)劃法的定義：在求解問題中，對(duì)于每一步?jīng)Q策，列出各種可能的局部解，再依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解，在每一步都經(jīng)過篩選，以每一步都是最優(yōu)解來保證全局是最優(yōu)解，這種求解方法稱為動(dòng)態(tài)規(guī)劃法。88第八十八頁，共一百三十八頁，2022年，8月28日適合于用動(dòng)態(tài)規(guī)劃法求解的問題具有以下特點(diǎn)：1、可以劃分成若干個(gè)階段，問題的求解過程就是對(duì)若干個(gè)階段的一系列決策過程。2、每個(gè)階段有若干個(gè)可能狀態(tài)3、一個(gè)決策將你從一個(gè)階段的一種狀態(tài)帶到下一個(gè)階段的某種狀態(tài)。4、在任一個(gè)階段，最佳的決策序列和該階段以前的決策無關(guān)。5、各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費(fèi)用，而且在選擇最佳決策時(shí)有遞推關(guān)系（即動(dòng)態(tài)轉(zhuǎn)移方程）。89第八十九頁，共一百三十八頁，2022年，8月28日動(dòng)態(tài)規(guī)劃設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟：1、劃分階段：按照問題的時(shí)間或空間特征，把問題