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

算法分析與設(shè)計課件動態(tài)規(guī)劃法1第1頁，課件共138頁，創(chuàng)作于2023年2月通過應(yīng)用范例學(xué)習(xí)動態(tài)規(guī)劃算法設(shè)計策略。（1）矩陣連乘問題；（2）最長公共子序列；（3）最大子段和（4）凸多邊形最優(yōu)三角剖分；（5）多邊形游戲；（6）圖像壓縮；（7）電路布線；（8）流水作業(yè)調(diào)度；（9）背包問題；（10）最優(yōu)二叉搜索樹。2第2頁，課件共138頁，創(chuàng)作于2023年2月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)動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級。在用分治法求解時，有些子問題被重復(fù)計算了許多次。算法總體思想3第3頁，課件共138頁，創(chuàng)作于2023年2月如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項(xiàng)式時間算法。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第4頁，課件共138頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。5第5頁，課件共138頁，創(chuàng)作于2023年2月假定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ù)量級Ω(2n)的可能的相乘方式(有q個葉節(jié)點(diǎn)的二叉數(shù)的數(shù)目).要找一種相乘方式,使得元素乘法數(shù)最少6第6頁，課件共138頁，創(chuàng)作于2023年2月16000,10500,36000,87500,34500完全加括號的矩陣連乘積可遞歸地定義為：（1）單個矩陣是完全加括號的；（2）矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積A和B的乘積并加括號，即A=(BC)設(shè)有四個矩陣A,B,C,D，它們的維數(shù)分別是：矩陣連乘積總共有五中完全加括號的方式7第7頁，課件共138頁，創(chuàng)作于2023年2月給定n個矩陣，其中與是可乘的?？疾爝@n個矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積8第8頁，課件共138頁，創(chuàng)作于2023年2月給定n個矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。窮舉法：列舉出所有可能的計算次序，并計算出每一種計算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。

算法復(fù)雜度分析：對于n個矩陣的連乘積，設(shè)其不同的計算次序?yàn)镻(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：9第9頁，課件共138頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃將矩陣連乘積AiAi+1…Aj，簡記為A[i:j]，這里i≤j考察計算A[i:j]的最優(yōu)計算次序。設(shè)這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應(yīng)完全加括號方式為計算量：A[i:k]的計算量加上A[k+1:j]的計算量，再加上A[i:k]和A[k+1:j]相乘的計算量10第10頁，課件共138頁，創(chuàng)作于2023年2月特征：計算A[i:j]的最優(yōu)次序所包含的計算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。分析最優(yōu)解的結(jié)構(gòu)11第11頁，課件共138頁，創(chuàng)作于2023年2月建立遞歸關(guān)系設(shè)計算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]當(dāng)i=j時，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當(dāng)i<j時，這里的維數(shù)為

的位置只有種可能可以遞歸地定義m[i,j]為：12第12頁，課件共138頁，創(chuàng)作于2023年2月計算最優(yōu)值對于1≤i≤j≤n不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個數(shù)最多只有由此可見，在遞歸計算時，許多子問題被重復(fù)計算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復(fù)計算，最終得到多項(xiàng)式時間的算法13第13頁，課件共138頁，創(chuàng)作于2023年2月用動態(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第14頁，課件共138頁，創(chuàng)作于2023年2月A1A2A3A4A5A6303535151555101020202515第15頁，課件共138頁，創(chuàng)作于2023年2月算法復(fù)雜度分析：算法matrixChain的主要計算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。16第16頁，課件共138頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結(jié)構(gòu)矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。同一個問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低）17第17頁，課件共138頁，創(chuàng)作于2023年2月二、重疊子問題遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常不同的子問題個數(shù)隨問題的大小呈多項(xiàng)式增長。因此用動態(tài)規(guī)劃算法只需要多項(xiàng)式時間，從而獲得較高的解題效率。18第18頁，課件共138頁，創(chuàng)作于2023年2月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第19頁，課件共138頁，創(chuàng)作于2023年2月三、備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復(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第20頁，課件共138頁，創(chuàng)作于2023年2月最長公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對于所有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個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。21第21頁，課件共138頁，創(chuàng)作于2023年2月設(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個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。22第22頁，課件共138頁，創(chuàng)作于2023年2月子問題的遞歸結(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時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：23第23頁，課件共138頁，創(chuàng)作于2023年2月計算最優(yōu)值由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(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第24頁，課件共138頁，創(chuàng)作于2023年2月構(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第25頁，課件共138頁，創(chuàng)作于2023年2月算法的改進(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個數(shù)組元素的值所確定。對于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在時間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個值所確定的。如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。事實(shí)上，在計算c[i][j]時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計算出最長公共子序列的長度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。26第26頁，課件共138頁，創(chuàng)作于2023年2月最大字段和給定由n個整數(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)時，最大字段和為27第27頁，課件共138頁，創(chuàng)作于2023年2月最大字段和的簡單算法

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第28頁，課件共138頁，創(chuàng)作于2023年2月最大字段和的簡單算法改進(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第29頁，課件共138頁，創(chuàng)作于2023年2月最大字段和的分治算法如果將所給的序列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情形可遞歸求得。對于3，

在a[1:n/2]計算出30第30頁，課件共138頁，創(chuàng)作于2023年2月在a[n/2+1:n]計算出則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第31頁，課件共138頁，創(chuàng)作于2023年2月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第32頁，課件共138頁，創(chuàng)作于2023年2月時間復(fù)雜度：33第33頁，課件共138頁，創(chuàng)作于2023年2月最大字段和的動態(tài)規(guī)劃算法對于上述分治算法的分析中，若記則所求的最大字段和為：當(dāng)b[j-1]>0時，b[j]=b[j-1]+a[j]，否則b[j]=a[j]。由此可得動態(tài)規(guī)劃遞歸式：

b[j]=max{b[j-1]+a[j],a[j]}，1<=j<=n34第34頁，課件共138頁，創(chuàng)作于2023年2月最大字段和的動態(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第35頁，課件共138頁，創(chuàng)作于2023年2月求任意一對頂點(diǎn)的最短路徑---弗羅伊德(Floyd)算法設(shè)圖g用鄰接矩陣法表示，求圖g中任意一對頂點(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)號不大于0的最短路徑。

36第36頁，課件共138頁，創(chuàng)作于2023年2月3.在vi、vj間加入頂點(diǎn)v1，得（vi,…，v1）和(v1,…，vj)，其中（vi,…,v1）是vi到v1的且中間頂點(diǎn)號不大于0的最短路徑，

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

37第37頁，課件共138頁，創(chuàng)作于2023年2月4.在vi、vj間加入頂點(diǎn)v2，得（vi,…,v2）和(v2,…,vj)，其中（vi,…,v2）是vi到v2的且中間頂點(diǎn)號不大于1的最短路徑

(v2,…,vj)

是v2到vj的且中間頂點(diǎn)號不大于1的最短路徑，這兩條路徑在上一步中已求出。將（vi,…,v2,…,vj）與上一步已求出的且vi到vj中間頂點(diǎn)號不大于1的最短路徑比較，取其中較短的路徑作為vi到vj的且中間頂點(diǎn)號不大于2的最短路徑。依次類推，經(jīng)過n次比較和修正，在第（n-1）步，將求得vi到vj的且中間頂點(diǎn)號不大于n-1的最短路徑，這必是從vi到vj的最短路徑。按此方法可求得各對頂點(diǎn)間的最短路徑。38第38頁，課件共138頁，創(chuàng)作于2023年2月現(xiàn)定義一個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

從上述計算公式可見，A(1)[i][j]是從vi到vj的中間頂點(diǎn)的序號不大于1的最短路徑的長度；A(k)[i][j]是從vi到vj的中間頂點(diǎn)的個數(shù)不大于k的最短路徑的長度；A(n-1)[i][j]就是從vi到vj的最短路徑的長度。由此得到求任意兩頂點(diǎn)間的最短路徑的算法。39第39頁，課件共138頁，創(chuàng)作于2023年2月voidFloyd(MgraphG,PathMatrix*P[],DistancMatrix*A){/*用Floyd算法求有向網(wǎng)G中各對頂點(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)/*各對頂點(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第40頁，課件共138頁，創(chuàng)作于2023年2月

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

矩陣連乘積中的每個矩陣Ai對應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，i<j，對應(yīng)于矩陣連乘積A[i+1:j]。一般情況下，一個凸邊形的三角剖分對應(yīng)于一棵有n-1個葉結(jié)點(diǎn)的語法樹。凸多邊形{v0,v1,…vn-1}的三角剖分也可以用語法樹表示。例如，圖(b)中凸多邊形的三角剖分可用圖(a)所示的語法樹表示。45第45頁，課件共138頁，創(chuàng)作于2023年2月最優(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個部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和?？梢詳嘌?，由T所確定的這2個子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衶v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。46第46頁，課件共138頁，創(chuàng)作于2023年2月最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義t[i][j]，1≤i<j≤n為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見，設(shè)退化的多邊形{vi-1,vi}具有權(quán)值0。據(jù)此定義，要計算的凸(n+1)邊形P的最優(yōu)權(quán)值為t[1][n]。t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計算。當(dāng)j-i≥1時，凸子多邊形至少有3個頂點(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。由于在計算時還不知道k的確切位置，而k的所有可能位置只有j-i個，因此可以在這j-i個位置中選出使t[i][j]值達(dá)到最小的位置。由此，t[i][j]可遞歸地定義為：47第47頁，課件共138頁，創(chuàng)作于2023年2月計算最優(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;}}}}占用空間：耗時：48第48頁，課件共138頁，創(chuàng)作于2023年2月多邊形游戲多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點(diǎn)構(gòu)成的多邊形。每個頂點(diǎn)被賦予一個整數(shù)值，每條邊被賦予一個運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個頂點(diǎn)V1和V2；(2)用一個新的頂點(diǎn)取代邊E以及由E連接著的2個頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)值通過邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。問題:對于給定的多邊形，計算最高得分。49第49頁，課件共138頁，創(chuàng)作于2023年2月最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)所給的多邊形的頂點(diǎn)和邊的順時針序列為：op[1],v[1],op[2],v[2],…,op[n],v[n]其中，op[i]表示第I條邊所對應(yīng)的運(yùn)算符，v[i]表示第i個頂點(diǎn)上的數(shù)值。在所給多邊形中，從頂點(diǎn)i(1≤i≤n)開始，長度為j(鏈中有j個頂點(diǎn))的順時針鏈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個子鏈p(i，s)和p(i+s，j-s)。設(shè)m1是對子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有a≤m1≤b，c≤m2≤d50第50頁，課件共138頁，創(chuàng)作于2023年2月由于子鏈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]='+'時，顯然有a+c≤m≤b+d(2)當(dāng)op[i+s]=‘*’時，由于v[i]可能取負(fù)值，子鏈的最大值相乘未必得到主鏈的最大值。但有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd}換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。例如：當(dāng)m=ac時，最大主鏈由它的兩條最小子鏈組成；同理當(dāng)m=bd時，最大主鏈由它的兩條最大子鏈組成。51第51頁，課件共138頁，創(chuàng)作于2023年2月遞歸求解為了求鏈合并的最大值，必須同時求子鏈合并的最大值和最小值。因此，在整個計算過程中，應(yīng)同時計算最大值和最小值。設(shè)m[i,j,0]是鏈p(i,j)合并的最小值，而m[i,j,1]是最大值。若最優(yōu)合并在op[i+s]處將p(i,j)分為2個長度小于j的子鏈p(i,i+s)和p(i+s,j-s),且從頂點(diǎn)i開始的長度小于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]=‘+’時，m[i,j,0]=a+cm[i,j,1]=b+d(2)當(dāng)op[i+s]=‘*’時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第52頁，課件共138頁，創(chuàng)作于2023年2月53第53頁，課件共138頁，創(chuàng)作于2023年2月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第54頁，課件共138頁，創(chuàng)作于2023年2月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;}時間：55第55頁，課件共138頁，創(chuàng)作于2023年2月圖像壓縮圖象的變位壓縮存儲格式將所給的象素點(diǎn)序列{p1,p2,…,pn},0≤pi≤255分割成m個連續(xù)段S1,S2,…,Sm。第i個象素段Si中(1≤i≤m)，有l(wèi)[i]個象素,且該段中每個象素都只用b[i]位表示。設(shè)則第i個象素段Si為設(shè)，則hib[i]8。因此需要用3位表示b[i],如果限制1l[i]255，則需要用8位表示l[i]。因此，第i個象素段所需的存儲空間為l[i]*b[i]+11位。按此格式存儲象素序列{p1,p2,…,pn}，需要位的存儲空間。

56第56頁，課件共138頁，創(chuàng)作于2023年2月圖象壓縮問題要求確定象素序列{p1,p2,…,pn}的最優(yōu)分段，使得依此分段所需的存儲空間最少。每個分段的長度不超過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)分段所需的存儲位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知：圖像壓縮其中57第57頁，課件共138頁，創(chuàng)作于2023年2月圖像壓縮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第58頁，課件共138頁，創(chuàng)作于2023年2月算法復(fù)雜度分析：由于算法compress中對k的循環(huán)次數(shù)不超這256，故對每一個確定的i，可在時間O(1)內(nèi)完成的計算。因此整個算法所需的計算時間為O(n)。圖像壓縮59第59頁，課件共138頁，創(chuàng)作于2023年2月電路布線在一塊電路板的上、下2端分別有n個接線柱。根據(jù)電路設(shè)計，要求用導(dǎo)線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是{1,2,…,n}的一個排列。導(dǎo)線(i,π(i))稱為該電路板上的第i條連線。對于任何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。

電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。60第60頁，課件共138頁，創(chuàng)作于2023年2月記。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)當(dāng)i=1時，

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

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

bi+max{t,ai}-ai=bi+max{t-ai,0}時間才能完成對作業(yè)i的加工。對遞歸式的深入分析表明，算法可進(jìn)一步得到簡化。66第66頁，課件共138頁，創(chuàng)作于2023年2月Johnson不等式設(shè)是作業(yè)集S在機(jī)器M2的等待時間為t時的任一最優(yōu)調(diào)度。若(1)=i,(2)=j。則由動態(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第67頁，課件共138頁，創(chuàng)作于2023年2月交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另一調(diào)度，它所需的加工時間為T’(S,t)=ai+aj+T(S-{i,j},tji)其中，當(dāng)作業(yè)i和j滿足Johnson不等式時，有68第68頁，課件共138頁，創(chuàng)作于2023年2月由此可見當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時，交換它們的加工順序后，不增加加工時間。對于流水作業(yè)調(diào)度問題，必存在最優(yōu)調(diào)度，使得作業(yè)(i)和(i+1)滿足Johnson不等式。進(jìn)一步還可以證明，調(diào)度滿足Johnson法則當(dāng)且僅當(dāng)對任意i<j有由此可知，所有滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。

69第69頁，課件共138頁，創(chuàng)作于2023年2月算法描述流水作業(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ù)雜度分析：算法的主要計算時間花在對作業(yè)集的排序。因此，在最壞情況下算法所需的計算時間為O(nlogn)。所需的空間為O(n)。70第70頁，課件共138頁，創(chuàng)作于2023年2月0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。71第71頁，課件共138頁，創(chuàng)作于2023年2月在0/1背包問題中，需對容量為c的背包進(jìn)行裝載。從n個物品中選取裝入背包的物品，每件物品i的重量為wi，價值為pi。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1

72第72頁，課件共138頁，創(chuàng)作于2023年2月設(shè)所給0-1背包問題的子問題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i，j)的遞歸式如下。73第73頁，課件共138頁，創(chuàng)作于2023年2月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第74頁，課件共138頁，創(chuàng)作于2023年2月……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第75頁，課件共138頁，創(chuàng)作于2023年2月算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當(dāng)背包容量c很大時，算法需要的計算時間較多。例如，當(dāng)c>2n時，算法需要Ω(n2n)計算時間。算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當(dāng)背包容量c很大時，算法需要的計算時間較多。例如，當(dāng)c>2n時，算法需要Ω(n2n)計算時間。76第76頁，課件共138頁，創(chuàng)作于2023年2月由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1≤i≤n)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。如圖所示。對每一個確定的i(1≤i≤n)，用一個表p[i]存儲函數(shù)m(i，j)的全部跳躍點(diǎn)。表p[i]可依計算m(i，j)的遞歸式遞歸地由表p[i+1]計算，初始時p[n+1]={(0，0)}。77第77頁，課件共138頁，創(chuàng)作于2023年2月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第78頁，課件共138頁，創(chuàng)作于2023年2月函數(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個跳躍點(diǎn)，則當(dāng)ca且d<b時，(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]計算表p[i]時，可先由p[i+1]計算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點(diǎn)得到表p[i]。算法改進(jìn)79第79頁，課件共138頁，創(chuàng)作于2023年2月n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始時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]的最后的那個跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。80第80頁，課件共138頁，創(chuàng)作于2023年2月上述算法的主要計算量在于計算跳躍點(diǎn)集p[i](1≤i≤n)。由于q[i+1]=p[i+1](wi，vi)，故計算q[i+1]需要O(|p[i+1]|)計算時間。合并p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要O(|p[i+1]|)計算時間。從跳躍點(diǎn)集p[i]的定義可以看出，p[i]中的跳躍點(diǎn)相應(yīng)于xi,…,xn的0/1賦值。因此，p[i]中跳躍點(diǎn)個數(shù)不超過2n-i+1。由此可見，算法計算跳躍點(diǎn)集p[i]所花費(fèi)的計算時間為從而，改進(jìn)后算法的計算時間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1≤i≤n)是整數(shù)時，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進(jìn)后算法的計算時間復(fù)雜性為O(min{nc,2n})。算法復(fù)雜度分析81第81頁，課件共138頁，創(chuàng)作于2023年2月最優(yōu)二叉搜索樹二叉搜索樹（1）若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；（2）若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；（3它的左、右子樹也分別為二叉排序樹45125333724100619078在隨機(jī)的情況下，二叉查找樹的平均查找長度和是等數(shù)量級的82第82頁，課件共138頁，創(chuàng)作于2023年2月已知二叉搜索樹中每個節(jié)點(diǎn)的訪問概率，問這棵樹整體的搜索時間最短是多少（此時稱為最優(yōu)二叉搜索樹）。例:分別以概率:0.1,0.2,0.4,0.3查找四個鍵: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個鍵的二查樹的總量等于第n個數(shù)的卡塔蘭數(shù)83第83頁，課件共138頁，創(chuàng)作于2023年2月設(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第84頁，課件共138頁，創(chuàng)作于2023年2月85第85頁，課件共138頁，創(chuàng)作于2023年2月86第86頁，課件共138頁，創(chuàng)作于2023年2月課后作業(yè)習(xí)題3-1，3-2，3-3，3-4，3-5，3-6，3-987第87頁，課件共138頁，創(chuàng)作于2023年2月小結(jié)1、

階段：把問題分成幾個相互聯(lián)系的有順序的幾個環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。2、狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。3、決策：從某階段的一個狀態(tài)演變到下一個階段某狀態(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)移方程。動態(tài)規(guī)劃法的定義：在求解問題中，對于每一步?jīng)Q策，列出各種可能的局部解，再依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解，在每一步都經(jīng)過篩選，以每一步都是最優(yōu)解來保證全局是最優(yōu)解，這種求解方法稱為動態(tài)規(guī)劃法。88第88頁，課件共138頁，創(chuàng)作于2023年2月適合于用動態(tài)規(guī)劃法求解的問題具有以下特點(diǎn)：1、可以劃分成若干個階段，問題的求解過程就是對若干個階段的一系列決策過程。2、每個階段有若干個可能狀態(tài)3、一個決策將你從一個階段的一種狀態(tài)帶到下一個階段的某種狀態(tài)。4、在任一個階段，最佳的決策序列和該階段以前的決策無關(guān)。5、各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費(fèi)用，而且在選擇最佳決策時有遞推關(guān)系（即動態(tài)轉(zhuǎn)移方程）。89第89頁，課件共138頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟：1、劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。2、確定狀態(tài)：將問題發(fā)展到各個階段時所處的各種客觀情況用不同的狀態(tài)表示出來。3、確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)，所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫出。4、尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是