第3章動態(tài)規(guī)劃(2)知識課件

第3章動態(tài)規(guī)劃郭藝輝廣東金融學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系辦公室：1622電話37215835Email：校內(nèi)郵箱gdufguo@126.com第3章動態(tài)規(guī)劃基本思想：動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時間算法。第3章動態(tài)規(guī)劃美國哲學(xué)家喬治.桑塔雅那(GeorgeSantayana)，忽略歷史會使我們重蹈覆轍，而記住過去可以使我們走向光明的未來。Thosewhocannotrememberthepastaredoomedtorepeatit.——GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)4本章主要知識點(diǎn)：3.1矩陣連乘問題3.2動態(tài)規(guī)劃算法的基本要素3.3最長公共子序列問題3.4最大子段和3.5凸多邊形的最優(yōu)三角剖分3.6多邊形游戲3.7圖像壓縮3.8電路布線3.9流水作業(yè)調(diào)度3.100-1背包問題3.11最有二叉搜索樹3.12動態(tài)規(guī)劃加速原理第3章動態(tài)規(guī)劃3.1矩陣連乘問題問題提出：給定n個矩陣{A1,A2,...,An}，其中Ai與Ai+1是可乘的，i=1,2,...,n-1。考察這n個矩陣的連乘積A1A2...An。由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號的方式來確定。若一個矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。3.1矩陣連乘問題完全加括號的矩陣連乘積可遞歸地定義為：單個矩陣是完全加括號的；矩陣連乘積B是完全加括號的，則B可表示為2個完全加括號的矩陣連乘積A1和A2的乘積并加括號，即B=(A1A2)。設(shè)有三個矩陣A1，A2

，A3，它們的維數(shù)分別是：A1=10×100，A2=100×5，A3=5×50總共有兩種完全加括號的方式：((A1A2)A3)、(A1(A2A3))其數(shù)乘次數(shù)分別為：7500,75000。3.1矩陣連乘問題窮舉搜索法問題描述：給定n個矩陣｛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ì)算次序。3.1矩陣連乘問題動態(tài)規(guī)劃法——1.分析最優(yōu)解的結(jié)構(gòu)預(yù)處理：將矩陣連乘積AiAi+1...Aj簡記為A[i:j]，這里i≤j?？疾煊?jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應(yīng)完全加括號方式為（AiAi+1...Ak）（Ak+1Ak+2...Aj）。計(jì)算量：A[i:k]的計(jì)算量加上A[k+1:j]的計(jì)算量，再加上A[i:k]和A[k+1:j]相乘的計(jì)算量。3.1矩陣連乘問題這個問題的一個關(guān)鍵特征是：計(jì)算A［1：n]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A［1：k]和A「k＋1：n]的次序也是最優(yōu)的。事實(shí)上，若有一個計(jì)算A[1：k］的次序需要的計(jì)算量更少，則用此次序替換原來計(jì)算A［1：k]的次序，得到的計(jì)算A［1：n]的計(jì)算量將比最優(yōu)次序所需計(jì)算量更少，這是一個矛盾。同理可知，計(jì)算A［l：n]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[k+1：n]的次序也是最優(yōu)的。

因此，矩陣連乘積計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。3.1矩陣連乘問題2建立遞歸關(guān)系設(shè)計(jì)動態(tài)規(guī)劃算法的第2步是遞歸地定義最優(yōu)值。對于矩陣連乘積的最優(yōu)計(jì)算次序問題，設(shè)計(jì)算A「i：j」，l＜=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時，m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj，這里Ai的維數(shù)為pi-1×pi。可以遞歸地定義m[i,j]為：k的位置只有j-i種可能。3.1矩陣連乘問題3計(jì)算最優(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;}

}

}}3.1矩陣連乘問題A1A2A3A4A5A6303535

1515

55

1010

2020

253.1矩陣連乘問題3計(jì)算最優(yōu)值對于1≤i≤j≤n不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個數(shù)最多只有O(n2)由此可見，在遞歸計(jì)算時，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個子問題只計(jì)算一次，而在后面需要時只要簡單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時間的算法。3.1矩陣連乘問題4.構(gòu)造最優(yōu)解復(fù)雜性分析：算法MatrixChain的主要計(jì)算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時間上界為O(n3)。3.2動態(tài)規(guī)劃算法的基本要素從計(jì)算矩陣連乘積最優(yōu)計(jì)算次序的動態(tài)規(guī)劃算法可以看出，該算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。從一般意義上講，問題所具有的這兩個重要性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的基本要素。這對于在設(shè)計(jì)求解具體問題的算法時，是否選擇動態(tài)規(guī)劃算法具有指導(dǎo)意義。3.2動態(tài)規(guī)劃算法的基本要素

1、最優(yōu)子結(jié)構(gòu)設(shè)計(jì)動態(tài)規(guī)劃算法的第1步通常是要刻畫最優(yōu)解的結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)提供了該問題可用動態(tài)規(guī)劃算法求解的重要線索。在矩陣連乘積最優(yōu)計(jì)算次序問題中注意到，若A1A2…An的最優(yōu)完全加括號方式在AK和AK+1之間將矩陣鏈斷開，則由此確定的子鏈A1A2…Ak和Ak+1，Ak+2…An的完全加括號方式也最優(yōu)，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3.2動態(tài)規(guī)劃算法的基本要素在分析該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性。首先假設(shè)由問題的最優(yōu)解導(dǎo)出的其子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。在動態(tài)規(guī)劃算法中，利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。3.2動態(tài)規(guī)劃算法的基本要素2重疊子問題

可用動態(tài)規(guī)劃算法求解的問題應(yīng)具備的另一基本要素是子問題的重疊性質(zhì)。在用遞歸算法自頂向下解此問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常，不同的子問題個數(shù)隨問題的大小呈多項(xiàng)式增長。因此，用動態(tài)規(guī)劃算法通常只需要多項(xiàng)式時間，從而獲得較高的解題效率。3.2動態(tài)規(guī)劃算法的基本要素3.2動態(tài)規(guī)劃算法的基本要素3、備忘錄方法備忘錄方法是動態(tài)規(guī)劃算法的變形。與動態(tài)規(guī)劃算法一樣，備忘錄方法用表格保存已解決的子問題的答案，在下次需要解此子問題時，只要簡單地查看該子問題的解答，而不必重新計(jì)算。與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復(fù)求解。

3.2動態(tài)規(guī)劃算法的基本要素IntMemoizedMatrixChain（Intn,Int

**

m，Int**s）

{for(i=1;i<=n;i++)for(intj=1;j<=n;j++)

M[i][j]=0

returnLookupChain（1，n）；｝3.2動態(tài)規(guī)劃算法的基本要素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;}算法復(fù)雜性：T(n)=O(n3)3.2動態(tài)規(guī)劃算法的基本要素綜上所述，矩陣連乘積的最優(yōu)計(jì)算次序問題可用自頂向下的備忘錄方法或自底向上的動態(tài)規(guī)劃算法在O(n3)計(jì)算時間內(nèi)求解。這兩個算法都利用了子問題重疊性質(zhì)?？偣灿笑?n2)個不同的子問題，對每個子問題兩種算法都只解一次并記錄答案。當(dāng)再次遇到該子問題時，簡單地取用已得到的答案，節(jié)省了計(jì)算量，提高了算法的效率。3.3最長公共子序列

一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列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}。給定兩個序列X=｛A,B,C,B,D,A,B｝和Y={B,D,C,A,B,A}，當(dāng)另一序列Z={B,D}既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。3.3最長公共子序列

最長公共子序列問題：給定兩個序列X={x1,x2,…,xm}和={y1,y2,…,yn}，找出X和Y的最長公共子序列。

最長公共子序列的結(jié)構(gòu)最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)。設(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的最長公共子序列。3.3最長公共子序列2.子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中，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)系如下：3.3最長公共子序列3.計(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;}}3.3最長公共子序列4.構(gòu)造最長公共子序列Algorithmlcs(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);}3.4最大子段和問題描述：給定由n個整數(shù)（包含負(fù)整數(shù)）組成的序列a1,a2,...,an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負(fù)值時定義其最大子段和為0。依此定義，所求的最優(yōu)值為：

例如當(dāng)(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時，最大子段和為：

3.4最大子段和一個簡單算法：int

MaxSum(intn,a,&besti,&bestj){intsum=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++){int

thissum=0;for(k=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;Bestj=j;}}returnsum;}算法有3重循環(huán)，復(fù)雜性為O(n3)。由于有：算法可作如下改進(jìn)：int

MaxSum(intn,a,&besti,&bestj){intsum=0;for(i=1;i<=n;i++){int

thissum=0;for(j=1;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}}改進(jìn)后的算法復(fù)雜性為O(n2)。3.4最大子段和2.最大字段和問題的分治算法從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解：如果將所給的序列a[1:n]分為長度相等的兩段a[1:n/1]和a[n/2+1:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有三種情形：a[1:n]的最大子段和與a[1:n/2]的最大子段和相同；a[1:n]的最大子段和與a[n/2+1:n]的最大子段和相同；a[1:n]的最大子段和為，且1<=i<=n/2,n/2+1<=j<=n。

3.4最大子段和2.最大字段和問題的分治算法A、B這兩種情形可遞歸求得。對于情形C，容易看出，a[n/2]與a[n/2+1]在最優(yōu)子序列中。因此，我們可以在a[1:n/2]和a[n/2+1:n]中分別計(jì)算出如下的s1和s2。則s1+s2即為出現(xiàn)情形C使得最優(yōu)值。

從而設(shè)計(jì)出下面所示的分治算法。3.4最大子段和intMaxSubSum(inta,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0;lefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}

ints2=0;rights=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<sightsum)sum=rightsum;}returnsum;}3.4最大子段和3.動態(tài)規(guī)劃方法求解

例如，求當(dāng)(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時的最大字段和3.4最大子段和3.動態(tài)規(guī)劃方法求解由bj的定義易知，當(dāng)bj-1>0時bj=bj-1+aj，否則bj=aj。由此可得計(jì)算bj的動態(tài)規(guī)劃遞歸式

bj=max{bj-1+aj，aj}，1≤j≤n據(jù)此，可設(shè)計(jì)出求最大子段和的動態(tài)規(guī)劃算法如下：int

MaxSum(intn,inta){intsum=0;b=0;for(i=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;}顯然該算法的計(jì)算時間為O(n)。3.4最大子段和問題描述：給定由n個整數(shù)（包含負(fù)整數(shù)）組成的序列a1,a2,...,an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負(fù)值時定義其最大子段和為0。依此定義，所求的最優(yōu)值為：

例如當(dāng)(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時，最大子段和為：

3.5凸多邊形最優(yōu)三角剖分用動態(tài)規(guī)劃算法能有效地解凸多邊形的最優(yōu)三角剖分問題。多邊形是平面上一條分段線性閉曲線。也就是說，多邊形是由一系列首尾相接的直線段所組成的。組成多邊形的各直線段稱為該多邊形的邊。連接多邊形相繼兩條邊的點(diǎn)稱為多邊形的頂點(diǎn)。若多邊形的邊除了連接頂點(diǎn)外沒有別的交點(diǎn)，則稱該多邊形為一簡單多邊形。一個簡單多邊形將平面分為三個部分：被包圍在多邊形內(nèi)的所有點(diǎn)構(gòu)成了多邊形的內(nèi)部；多邊形本身構(gòu)成多邊形的邊界；而平面上其余包圍著多邊形的點(diǎn)構(gòu)成了多邊形的外部。當(dāng)一個簡單多邊形及其內(nèi)部構(gòu)成一個閉凸集時，稱該簡單多邊形為一凸多邊形。即凸多邊形邊界上或內(nèi)部的任意兩點(diǎn)所連成的直線段上所有點(diǎn)均在凸多邊形的內(nèi)部或邊界上。3.5凸多邊形最優(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。3.5凸多邊形最優(yōu)三角剖分在凸多邊形P的一個三角剖分T中，各弦互不相交，且集合T已達(dá)到最大，即P的任一不在T中的弦必與T中某一弦相交。在有n個頂點(diǎn)的凸多邊形的三角剖分中，恰有n-3條弦和n-2個三角形。凸多邊形最優(yōu)三角剖分問題：

給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小?？梢远x三角形上各種各樣的權(quán)函數(shù)w。3.5凸多邊形最優(yōu)三角剖分1.三角剖分的結(jié)構(gòu)及其相關(guān)問題凸多邊形{v0,v1,…vn-1}的三角剖分可以用語法樹表示。例如，圖3-4(a)中凸多邊形的三角剖分可用圖3-5(b)所示的語法樹表示。3.5凸多邊形最優(yōu)三角剖分2.最優(yōu)子結(jié)構(gòu)性質(zhì)凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若凸(n+1)邊形P={v0,v1,…,vn}的最優(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)三角剖分的矛盾。3.5凸多邊形最優(yōu)三角剖分3.最優(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ù)此定義，要計(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時，凸子多邊形至少有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。由于在計(jì)算時還不知道k的確切位置，而k的所有可能位置只有j-i個，因此可以在這j-i個位置中選出使t[i][j]值達(dá)到最小的位置。3.5凸多邊形最優(yōu)三角剖分由此，t[i][j]可遞歸地定義為：3.5凸多邊形最優(yōu)三角剖分凸n+1邊形P={v0,v1,...,vn}的最有三角剖分動態(tài)規(guī)劃算法MinWT：voidMinWT(intn,type**t,int**s){for(int

i=1;i<=n;i++)t[i][i]=0;for(intr=2;r<=n;r++) for(i=1;i<=n-r+1;i++){intj=i+r-1;t[i][j]=t[i][i]+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;}}}}復(fù)雜性：T(n)=O(n3)S(n)=O(n2)3.8電路布線在一塊電路板的上、下2端分別有n個接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是{1,2,…,n}的一個排列。導(dǎo)線(i,π(i))稱為該電路板上的第i條連線。對于任何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。π(i)=｛8，7，4，2，5，1，9，3，10，6｝3.8電路布線在制作電路板時，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。電路布線問題就是要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。48記N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}，N(i,j)的最大不相交子集為MNS(i,j)，Size(i,j)=|MNS(i,j)|。(1)當(dāng)i=1時，(2)當(dāng)i>1時，j<π(i)。此時，(i,π(i))┐∈N(i,j)。故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。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)的最大不相交子集。若(i,π(i))┐∈N(i,j)，則對任意(t,π(t))∈MNS(i,j)有t<i。從而MNS(i,j)∈N(i-1,j)。因此，Size(i,j)≤Size(i-1,j)。另一方面MNS(i-1,j)∈N(i,j)，故又有Size(i,j)≥Size(i-1,j)，從而Size(i,j)=Size(i-1,j)。綜上可知，電路布線問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。3.8電路布線492.遞歸計(jì)算最優(yōu)值

算法描述：3.8電路布線3.8電路布線VoidMNS(intC[],intn,int**size){inti,j;for(j=0;j<C[1];j++){size[1][j]=0;}for(j=C[1];j<=n;j++){size[1][j]=1;}for(i=2;i<n;i++){for(j=0;j<C[i];j++){size[i][j]=size[i-1][j];}for(j=C[i];j<=n;j++){size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);}}size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);}算法復(fù)雜性：MNS算法：T(n)=O(n2)，S(n)=(n2)3.100-1背包問題問題提出：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

n=3,c=30,w={16,15,15},v={45，25，25}在選擇裝入背包的物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。因此，該問題稱為0-1背包問題。此問題的形式化描述是，0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。3.100-1背包問題1.最優(yōu)子結(jié)構(gòu)性質(zhì)2.建立遞歸關(guān)系設(shè)所給0-1背包問題的子問題：的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。

例如：n=3,c=30,w={16,15,15},v={45，25，25}由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下：3.100-1背包問題3.算法描述:voidknapsack(intv[],intw[],intc,intn,int**m){

intjmax=min(w[n]-1,c);

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

for(j=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];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]);

}3.100-1背包問題4.構(gòu)造最優(yōu)解voidtraceback(int**m,intw[],intc,intn,intx[])//求最優(yōu)解

{

for(inti=1;i<n;i++)

if(m[i][c]==m[i+1][c])x[i]=0;

else{x[i]=1;c-=w[i];}

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

3.100-1背包問題算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時間。當(dāng)背包容量c很大時，算法需要的計(jì)算時間較多。例如，當(dāng)c>2n時，算法需要Ω(n2n)計(jì)算時間。3.100-1背包問題算法改進(jìn):考察具體實(shí)例如下：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。在變量j是連續(xù)變量的情況下，可以對每一個確定的i，（1＜=i＜=n），用一個表P[i]來存儲函數(shù)m(i,j)的全部跳躍點(diǎn)。對每一個確定的實(shí)數(shù)j，可以通過查找表p[i]來確定函數(shù)m（i，j）的值。P[i]中全部跳躍點(diǎn)（j，m（i，j））依j的升序排列。由于函數(shù)m（i，j）是關(guān)于量j的階梯狀單調(diào)不減函數(shù)，故p[i]中全部跳躍點(diǎn)的m（i，j）值也是遞增排列的。表P[i]可依計(jì)算m（i，j）的遞歸式遞歸地由表p[i+1]來計(jì)算，初始時p[n+1]={(0,0)}。3.100-1背包問題事實(shí)上，函數(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)wi

s

c且(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]}

3.100-1背包問題另一方面，設(shè)(a，b)和(c，d)是p[i+1]

q[i+1]中的2個跳躍點(diǎn)，則當(dāng)c

a且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]計(jì)算表p[i]時，可先由p[i+1]計(jì)算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點(diǎn)得到表p[i]。59典型例子初始時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。n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。3.100-1背包問題算法復(fù)雜度分析上述算法的主要計(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ì)算時間。合并p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要O(|p[i+1]|)計(jì)算時間。從跳躍點(diǎn)集p[i]的定義可以看出，p[i]中的跳躍點(diǎn)相應(yīng)于xi,…,xn的0/1賦值。因此，p[i]中跳躍點(diǎn)個數(shù)不超過2n-i+1。由此可見，算法計(jì)算跳躍點(diǎn)集p[i]所花費(fèi)的計(jì)算時間為從而，改進(jìn)后算法的計(jì)算時間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1≤i≤n)是整數(shù)時，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進(jìn)后算法的計(jì)算時間復(fù)雜性為O(min{nc,2n})。3.11最優(yōu)二叉搜索樹什么是二叉搜索樹？若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；它的左、右子樹也分別為二叉排序樹45125333724100619078設(shè)S={x1,x2,...,xn}是一個有序集，且x1<x2<...<xn。表示有序集S的二叉搜索樹利用二叉樹的結(jié)點(diǎn)來存儲有序集中的元素。它具有下述性質(zhì)：存儲于每個結(jié)點(diǎn)中的元素x大于其左子樹中任一結(jié)點(diǎn)所存儲的元素，小于其右子樹中任一結(jié)點(diǎn)所存儲的元素。3.11最優(yōu)二叉搜索樹二叉搜索樹的葉結(jié)點(diǎn)是形如(xi，xi+1)的開區(qū)間。在表示S的二叉搜索樹中搜索一個元素x，返回的結(jié)果有兩種情形：在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到x=xi。在二叉搜索樹的葉結(jié)點(diǎn)中確定x∈(xi，xi+1)。3.11最優(yōu)二叉搜索樹設(shè)第一種情形中找到元素x=xi的概率為bi；在第二種情形中確定x∈(xi，xi+1)的概率為ai。并約定x0=-∞，xn+1=+∞。顯然有(a0,b1,a1,...,bn,an)稱為集合S的存取概率分布。在表示S的二叉搜索樹T中，設(shè)存儲元素xi的結(jié)點(diǎn)深度為ci；存儲葉結(jié)點(diǎn)(xj,xj+1)的結(jié)點(diǎn)深度為dj，則表示在二叉搜索樹T中作一次搜索所需要的平均比較次數(shù)。P又稱為二叉搜索樹T的平均路長。在一般情況下，不同的二叉樹的平均路長是不相同的。3.11最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹問題是對于有序集S及其存取概率分布(a0,b1,a1,.