《計(jì)算機(jī)算法設(shè)計(jì)與分析》PPT第三章 動(dòng)態(tài)規(guī)劃

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ī)劃（dynamicprogramming）是運(yùn)籌學(xué)的一個(gè)分支，20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(Multistepdecisionprocess)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)性原理，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。多階段決策問題：求解的問題可以劃分為一系列相互聯(lián)系的階段，在每個(gè)階段都需要做出決策，且一個(gè)階段決策的選擇會(huì)影響下一個(gè)階段的決策，從而影響整個(gè)過程的活動(dòng)路線，求解的目標(biāo)是選擇各個(gè)階段的決策使整個(gè)過程達(dá)到最優(yōu)。5動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），可以人為地引進(jìn)時(shí)間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。動(dòng)態(tài)規(guī)劃是考察問題的一種途徑，或是求解某類問題的一種方法。動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比其它方法求解更為方便。6基本概念①狀態(tài)：表示每個(gè)階段開始時(shí)，問題或系統(tǒng)所處的客觀狀況。狀態(tài)既是該階段的某個(gè)起點(diǎn)，又是前一個(gè)階段的某個(gè)終點(diǎn)。通常一個(gè)階段有若干個(gè)狀態(tài)。狀態(tài)無后效性：如果某個(gè)階段狀態(tài)給定后，則該階段以后過程的發(fā)展不受該階段以前各階段狀態(tài)的影響，也就是說狀態(tài)具有馬爾科夫性。適于動(dòng)態(tài)規(guī)劃法求解的問題具有狀態(tài)的無后效性②策略：各個(gè)階段決策確定后，就組成了一個(gè)決策序列，該序列稱之為一個(gè)策略。由某個(gè)階段開始到終止階段的過程稱為子過程，其對(duì)應(yīng)的某個(gè)策略稱為子策略。7最優(yōu)性原理Bellman最優(yōu)性原理求解問題的一個(gè)最優(yōu)策略序列的子策略序列總是最優(yōu)的，則稱該問題滿足最優(yōu)性原理。注：對(duì)具有最優(yōu)性原理性質(zhì)的問題而言，如果有一決策序列包含有非最優(yōu)的決策子序列，則該決策序列一定不是最優(yōu)的。8動(dòng)態(tài)規(guī)劃的思想實(shí)質(zhì)是分治思想和解決冗余動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法總體思想9但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。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)算法總體思想10如果能夠保存已解決的子問題的答案，而在需要時(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)算法總體思想11動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地劃分子問題，遞歸地定義最優(yōu)值，給出最優(yōu)解的遞歸式。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。注：步驟①~③是動(dòng)態(tài)規(guī)劃算法的基本步驟。如果只需要求出最優(yōu)值的情形，步驟④可以省略；若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟④，步驟③中記錄的信息是構(gòu)造最優(yōu)解的基礎(chǔ)；12給定n個(gè)矩陣，其中與是可乘的，。考察這n個(gè)矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積3.2矩陣連乘問題13完全加括號(hào)的矩陣連乘積

完全加括號(hào)的矩陣連乘積的遞歸定義：（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積A是完全加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即1415矩陣連乘問題問題描述給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，矩陣Ai的維數(shù)為pi-1×pi，i=1，2…，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。注意①設(shè)Ap×q,Aq×r兩矩陣相乘，普通乘法次數(shù)為p×q×r；②加括號(hào)對(duì)乘法次數(shù)的影響1617窮舉法列舉出所有可能的計(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)的遞推式如下：因此，窮舉法不是一個(gè)有效算法。呈指數(shù)增長(zhǎng)18計(jì)算量小的優(yōu)先計(jì)算n個(gè)矩陣的連乘積共有n-1次乘法計(jì)算。首先在n-1次乘法計(jì)算中選擇乘法計(jì)算量最小的兩個(gè)矩陣優(yōu)先計(jì)算，然后再在剩下的n-2次乘法計(jì)算中選擇計(jì)算量最小的兩個(gè)矩陣進(jìn)行計(jì)算，依此往下。該解決策略在某些情況下可得到最優(yōu)解，但在很多情況下得不到最優(yōu)解。如上例的第(5)種完全加括號(hào)方式即采用該策略，但得到的顯然不是最優(yōu)解。19矩陣維數(shù)大的優(yōu)先計(jì)算在n個(gè)矩陣的n+1個(gè)維數(shù)序列p0,p1,p2,…,pn中選擇維數(shù)的最大值（設(shè)為pi），并把相鄰兩個(gè)含有維數(shù)pi的矩陣優(yōu)先進(jìn)行計(jì)算，然后在剩下的n個(gè)維數(shù)序列中再次選擇維數(shù)的最大值，進(jìn)行相應(yīng)矩陣的乘法運(yùn)算，依此往下。該策略與上一種策略相似，在某些情況下可得到最優(yōu)解，但在有些情況下得不到最優(yōu)解。如上例的第(3)種完全加括號(hào)方式就是采用該策略，顯然它得到的是最優(yōu)解。當(dāng)４個(gè)矩陣的維數(shù)改為50×10,10×40,40×30和30×5時(shí)，可驗(yàn)證采用該策略得到的不是最優(yōu)解。以上兩種策略實(shí)質(zhì)都是基于某種貪心選擇的貪心算法，這種算法不一定能得到問題的全局最優(yōu)解。在下一章我們將詳細(xì)討論此種策略。20分治法將矩陣連乘積AiAi+1…Aj簡(jiǎn)記為A[i:j]。設(shè)n個(gè)矩陣的連乘積A1A2…An的計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，1≤k<n，則其相應(yīng)的完全加括號(hào)方式為(A1...Ak)(Ak+1…An)。完全加括號(hào)是一個(gè)遞歸定義，可遞歸地計(jì)算A[1：k]和A[k+1:n]，然后將計(jì)算結(jié)果相乘得到A[1：n]。可設(shè)計(jì)如下遞歸算法recurmatrixChain：2122該遞歸算法的的計(jì)算時(shí)間T(n)可遞歸定義如下：當(dāng)n>1時(shí)，該算法的計(jì)算時(shí)間T(n)有指數(shù)下界。分治法是該問題的一個(gè)可行方法，但不是一個(gè)有效算法。23為何分治法的效率如此低下？recurmatrixChain(1,4)計(jì)算A[1：4]的遞歸樹。從圖中可看出，許多子問題被重復(fù)計(jì)算。這是分治法效率低下的根本原因。24該問題可用分治思想解決，并存在大量冗余，可用動(dòng)態(tài)規(guī)劃求解。動(dòng)態(tài)規(guī)劃25矩陣連乘問題將矩陣連乘積簡(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ì)算量261、分析最優(yōu)解的結(jié)構(gòu)特征計(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ī)劃算法求解的顯著特征。2728假設(shè)計(jì)算A[i:j](1≤i≤j≤n)所需要的最少數(shù)乘次數(shù)為m[i,j]，則原問題的最優(yōu)值為m[1,n]i=j時(shí)，A[i:j]=Ai，m[i,i]=0，i=1,2,…,ni<j時(shí)，的維數(shù)為2、建立遞歸關(guān)系29遞歸地定義m[i,j]k的位置只有j-i種可能取得的k為A[i:j]最優(yōu)次序中的斷開位置，并記錄到表s[i][j]中，即s[i][j]←k。注：m[i][j]實(shí)際是子問題最優(yōu)解的解值，保存下來避免重復(fù)計(jì)算。30對(duì)于1≤i≤j≤n不同的有序?qū)?i，j)對(duì)應(yīng)于不同的子問題。不同子問題的個(gè)數(shù)最多只有由此可見，在遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。3、計(jì)算最優(yōu)值31用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。32svoidMatrixChain(int*p，intn，int**m，int**s)//n是連乘矩陣數(shù)目，A1A2…An；p是矩陣維數(shù)，Ai的維數(shù)為pi-1×pi(1≤i≤n)；//m是n個(gè)矩陣連乘的數(shù)乘次數(shù)最小值；s存儲(chǔ)矩陣連乘的最優(yōu)計(jì)算次序{

for(inti=1;i<=n;i++)m[i][i]=0;//對(duì)角線置0,計(jì)算Ai...Ai的乘法次數(shù),鏈長(zhǎng)為1for(intr=2;r<=n;r++)//分別計(jì)算r個(gè)矩陣連乘的最小數(shù)乘次數(shù)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];//Ai...Aj在矩陣i處斷開時(shí)的數(shù)乘次數(shù)s[i][j]=i;//記錄取得Ai...Aj當(dāng)前數(shù)乘次數(shù)的斷開位置for(intk=i+1;k<j;k++){//計(jì)算Ai...Aj的最小數(shù)乘次數(shù)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;}}}}3334A1A2A3A4A5A63035351515551010202025算法復(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)。設(shè)要計(jì)算矩陣連乘積中各矩陣的維數(shù)分別為：354、用動(dòng)態(tài)規(guī)劃法求最優(yōu)解MatrixChain已記錄了構(gòu)造最優(yōu)解所需要的全部信息。S[i][j]表明計(jì)算矩陣A[i,j]的最佳方式應(yīng)在矩陣Ak和Ak+1之間斷開，即最優(yōu)的加括號(hào)方式應(yīng)為(A[i:k])(A[k+1:j])。從s[1][n]記錄的信息可知A[1:n]的最優(yōu)加括號(hào)方式為(A[i:s[1][n]])(A[s[1][n]+1:n])。A[i:s[1][n]]的最優(yōu)加括號(hào)方式為(A[i:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]]])A[s[1][n]+1:n]的最優(yōu)加括號(hào)方式在s[s[1][n]+1][n]處斷開。照此遞推，最終可確定A[1:n]的最優(yōu)完全加括號(hào)方式，即構(gòu)造出問題的一個(gè)最優(yōu)解。36算法traceback：按照MatrixChain計(jì)算出的斷點(diǎn)s指示加括號(hào)方式輸出計(jì)算A[i:j]的最優(yōu)計(jì)算次序。Voidtraceback(inti,intj,int**s)//按算法MatrixChain計(jì)算出的斷點(diǎn)矩陣s指示的加括號(hào)方式輸出計(jì)算A[i:j]的最優(yōu)計(jì)算次序{if(i==j)return;traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);cout<<“MultiplyA”<<i<<“,”<<s[i][j];cout<<“andA”<<(s[i][j]+1)<<“,”<<j<<endl;}37一、最優(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)，有些表示方法的求解速度更快（空間占用小，問題的維度低）3.2動(dòng)態(tài)規(guī)劃算法的基本要素38二、重疊子問題遞歸算法求解問題時(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í)間，從而獲得較高的解題效率。39三、備忘錄方法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;}備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。40動(dòng)態(tài)規(guī)劃的設(shè)計(jì)技巧：階段的劃分、狀態(tài)的表示和存儲(chǔ)表的設(shè)計(jì)在動(dòng)態(tài)規(guī)劃的設(shè)計(jì)過程中，階段的劃分和狀態(tài)的表示是其中最重要的兩步，這兩步會(huì)直接影響該問題的計(jì)算復(fù)雜性和存儲(chǔ)表設(shè)計(jì)，有時(shí)候階段劃分或狀態(tài)表示的不合理還會(huì)使得動(dòng)態(tài)規(guī)劃法不適用。問題的階段劃分和狀態(tài)表示，需要具體問題具體分析，沒有一個(gè)清晰明朗的方法。在實(shí)際應(yīng)用中，許多問題的階段劃分并不明顯，這時(shí)如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)性原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決。41如何判斷問題滿足最優(yōu)性原理？思路：利用反證法，通過假設(shè)每一個(gè)子問題的解都不是最優(yōu)解，然后導(dǎo)出矛盾，即可做到這一點(diǎn)。42例1：設(shè)G是一個(gè)有向加權(quán)圖，則G從頂點(diǎn)i到頂點(diǎn)j之間的最短路徑問題滿足最優(yōu)性原理。證明：（反證法）設(shè)i~ip~iq~j是一條最短路徑，但其中子路徑ip~iq~j不是最優(yōu)的。假設(shè)最優(yōu)的子路徑為ip~iq’~j，則我們可以重新構(gòu)造一條路徑：i~ip~iq’~j，顯然該路徑長(zhǎng)度小于i~ip~iq~j，與i~ip~iq~j是頂點(diǎn)i到頂點(diǎn)j的最短路徑相矛盾。所以，原問題滿足最優(yōu)性原理。43例2：有向圖的最長(zhǎng)簡(jiǎn)單路徑問題不滿足最優(yōu)性原理。證明：如右圖所示，q→r→t是q到t的最長(zhǎng)簡(jiǎn)單路徑，而q→r的最長(zhǎng)簡(jiǎn)單路徑是q→s→t→r，r→t的最長(zhǎng)簡(jiǎn)單路徑是r→q→s→t，但q→r和r→t的最長(zhǎng)簡(jiǎn)單路徑合起來并不是q到t的最長(zhǎng)簡(jiǎn)單路徑。所以，原問題并不滿足最優(yōu)性原理。注：因?yàn)閝→r和r→t的子問題都共享路徑q→s→t，組合成原問題解時(shí)，有重復(fù)的路徑對(duì)原問題是不允許的。44454647484950515253實(shí)例二花束擺放問題1、問題描述現(xiàn)有F束不同品種的花束，同時(shí)有至少同樣數(shù)量的花瓶被按順序擺成一行，其位置固定于架子上，并從1至V按從左到右順序編號(hào)，V是花瓶的數(shù)目(F≤V)。花束可以移動(dòng)，并且每束花用1至F的整數(shù)唯一標(biāo)識(shí)。標(biāo)識(shí)花束的整數(shù)決定了花束在花瓶中排列的順序，如果i<j，花束i必須放在花束j左邊的花瓶中。每個(gè)花瓶只能放一束花。如果花瓶的數(shù)目大于花束的數(shù)目，則多余的花瓶空置。54每一個(gè)花瓶都具有各自的特點(diǎn)。因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)效果，并以一美學(xué)值(一個(gè)整數(shù))來表示，空置花瓶的美學(xué)值為零。為取得最佳美學(xué)效果，必須在保持花束順序的前提下，使花束的擺放取得最大的美學(xué)值。請(qǐng)求出具有最大美學(xué)值的一種擺放方式。552、解題思路狀態(tài)表示法一：設(shè)A(i,j)表示第i種花束擺在第j個(gè)花瓶中獲得的美學(xué)值。S(i,k)表示第i種花束擺在第k個(gè)花瓶中時(shí)(k≥i)，前i種花束能夠獲得的最大美學(xué)值(之和)。這樣，原問題的最優(yōu)值可通過計(jì)算max{S(F,k)|F≤k≤V}獲得。下面分析這種狀態(tài)表示法描述問題的方式是否具備了用動(dòng)態(tài)規(guī)劃求解的基本要素。56最優(yōu)子結(jié)構(gòu)性質(zhì)：對(duì)滿足F≤k≤V的k，設(shè)T(F,k)是達(dá)到最優(yōu)值S(F,k)的一種最佳擺放方式，其中，第F-1種花束擺在第j個(gè)花瓶中(j<k)，則T(F,k)中前F-1種花束的擺放方式獲得的最大美學(xué)值為S(F-1,j)。故對(duì)每個(gè)滿足F≤k≤V的k，計(jì)算S(F,k)的問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。遞歸方程：57在計(jì)算S(i-1,k-1)時(shí)，已經(jīng)計(jì)算出了S(i-1,j)，i-1≤j≤k-2及其max{S(i-1,j)|i-1≤j≤k-2}。因此，計(jì)算S(i,k)時(shí)，只要將S(i-1,k-1)與max{S(i-1,j)|i-1≤j≤k-2}進(jìn)行比較即可求得，即子問題重疊性質(zhì)。這樣做可大大減少計(jì)算量。58狀態(tài)表示法二：設(shè)S[i,k]表示第i種花束擺在第k個(gè)之前(包括第k個(gè))的任意某個(gè)花瓶中，前i種花束能夠獲得的最大美學(xué)值(之和)。這樣，原問題的最優(yōu)值即為S[F,V]。這比前一個(gè)表示法更直接。59容易驗(yàn)證，計(jì)算S[F,V]的問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。遞歸方程為：S[i,k]=max{S[i-1,k-1]+A(i,k),S[i,k-1]},i>1,k>i初始條件為：S[1,1]=A[1,1]S[1,k]=max{A(1,k),S[1,k-1]},k>1S[i,i]=S[i-1,i-1]+A(i,i),i>1603.3最長(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}。例：兩個(gè)DNA序列S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAAS2=GTCGTTCGGAATGCCGTTGCTCTGTAAALCS=GTCGTCGGAAGCCGGCCGAA6162兩個(gè)序列的公共子序列定義給定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)公共子序列。63定理：(一個(gè)LCS的最優(yōu)子結(jié)構(gòu))設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。(2)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長(zhǎng)公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長(zhǎng)公共子序列。2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。1、最長(zhǎng)公共子序列的結(jié)構(gòu)6465662、子問題的遞歸結(jié)構(gòu)將X和Y的LCS分解為2種情況：如xm=yn，找Xm-1和Yn-1的LCS；//解一個(gè)子問題如xm≠yn，找Xm-1和Y的LCS；找X和Yn-1的LCS；//解兩個(gè)子問題取兩者中的最大的；67用c[i][j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。c[i][j]的遞歸方程：當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列，C[i][j]=0。68693、計(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;}}}070過程LCSLength以兩個(gè)序列x、y為輸入，它把c[i,j]的值填入一個(gè)按行計(jì)算表項(xiàng)的表c[0..m,0..n]中，并維護(hù)表b[1..m,1..n]以簡(jiǎn)化最優(yōu)解的構(gòu)造。c[0..m,0..n]//存放最優(yōu)解值，計(jì)算時(shí)行優(yōu)先b[1..m,1..n]//解矩陣，存放構(gòu)造最優(yōu)解信息b[i,j]指向一個(gè)表項(xiàng)，對(duì)應(yīng)于在計(jì)算c[i,j]時(shí)所選擇的最優(yōu)子問題的解。程序最后返回b和c。c[m,n]包含X和Y的一個(gè)LCS的長(zhǎng)度。71由于在所考慮的子問題空間中，總共有θ(mn)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。724、構(gòu)造最長(zhǎng)公共子序列構(gòu)造最長(zhǎng)公共子序列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);}說明當(dāng)b[i,j]=1時(shí)，即xi=yj是LCS的一個(gè)元素；時(shí)間復(fù)雜度：θ(m+n)73構(gòu)造解時(shí)，從b[m,n]出發(fā)，上溯至i=0或j=0，上溯過程中，當(dāng)b[i,j]＝1時(shí)打印出xi或yj74例：X=<A,B,C,B,D,A,B>，Y=<B,D,C,A,B,A>最優(yōu)解：BCAB或BCBA或BADB755、算法的改進(jìn)在算法LCSLength和LCS中，可進(jìn)一步將數(shù)組b省去。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本身在O(1)時(shí)間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個(gè)值所確定的。76如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。計(jì)算c[i][j]時(shí)，只用到數(shù)組c的第i行和第i-1行。只用2行的數(shù)組空間就可計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。773.4最大子段和問題給定由n個(gè)整數(shù)(可能為負(fù)整數(shù))組成的序列a1,a2,…,an，求該序列形如的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)數(shù)時(shí)定義其最大子段和為0。依此定義，所求的最優(yōu)值為78例：整數(shù)序列(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)最大子段和為：791、最大子段和問題的簡(jiǎn)單算法簡(jiǎn)單算法數(shù)組a[]存儲(chǔ)給定的n個(gè)整數(shù)時(shí)間復(fù)雜度為O(n3)80改進(jìn)對(duì)k循環(huán)可以省略改進(jìn)后的算法時(shí)間復(fù)雜度為O(n2)812、最大子段和問題的分治算法將a[1:n]分為長(zhǎng)度相等的兩段a[1:n/2]和a[n/2+1:n]，分別對(duì)兩區(qū)段求最大子段和，則a[1:n]的最大子段和有三種情形：a[1:n]的最大子段和與a[1:n/2]的最大子段和相同a[1:n]的最大子段和與a[n/2:n]的最大子段和相同a[1:n]的最大子段和為對(duì)①②可遞歸求解對(duì)③可知a[n/2]、a[n/2+1]一定在最大和子段中在a[1:n/2]中計(jì)算，在a[n/2+1:n]中計(jì)算，s1+s2是該情況下的最大值。intMaxSubSum(int*a,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;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}//forintMaxSum(intn,int**a){returnMaxSubSum(a,1,n);}ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}//forsum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}//ifreturnsum;}//end83復(fù)雜度分析843、最大子段和問題的動(dòng)態(tài)規(guī)劃算法描述最優(yōu)解的結(jié)構(gòu)子問題定義：考慮所有下標(biāo)以j結(jié)束的最大子段和b[j]，即原問題與子問題的關(guān)系：85遞歸定義最優(yōu)解的值

b[j]=max{b[j-1]+a[j],a[j]},1≤j≤n86求最大子段和的動(dòng)態(tài)規(guī)劃算法intMaxSum(intn,int*a){intsum=0,b=0;

//sum存儲(chǔ)當(dāng)前最大的b[j],b存儲(chǔ)當(dāng)前b[j]for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];//b=0if(b>sum)sum=b;}returnsum;}874、最大子段和問題與動(dòng)態(tài)規(guī)劃算法的推廣最大子矩陣和問題給定一個(gè)m行n列的整數(shù)矩陣A，試求矩陣A的一個(gè)子矩陣，使其各元素之和為最大。二維數(shù)組a[1:m][1:n]表示給定m行n列的整數(shù)矩陣。子數(shù)組a[i1:i2][j1:j2]表示左上角和右下角行列坐標(biāo)分別為(i1,j1)和(i2,j2)的子矩陣。各元素之和最大子矩陣和問題的最優(yōu)值為88最大m子段和問題給定由n個(gè)整數(shù)（可能為負(fù)整數(shù)）組成的序列a1,a2,…,an，以及一個(gè)正整數(shù)m，要求確定序列a1,a2,…,an的m個(gè)不相交子段，使這m個(gè)子段的總和達(dá)到最大。設(shè)b(i,j)表示數(shù)組a的前j項(xiàng)中i個(gè)子段和的最大值，且第i個(gè)子段含a[j]。所求的最優(yōu)值為。89計(jì)算b(i,j)的遞歸式為初始時(shí)，903.5多段圖規(guī)劃問題描述多段圖G=(V,E)是一個(gè)有向圖，且具有以下特征：劃分為k≥2個(gè)不相交的集合Vi,1≤i≤k;V1和Vk分別只有一個(gè)結(jié)點(diǎn)s(源點(diǎn))和t(匯點(diǎn))；若<u,v>∈E(G)，u∈Vi，則v∈Vi+1,邊上成本記c(u,v)；若<u,v>不屬于E(G)，邊上成本記c(u,v)=∞。求由s到t的最小成本路徑。91例：一個(gè)5-段圖求從s到t的最短路徑。92多段圖問題滿足最優(yōu)性原理設(shè)s,…,vip,…,viq,…,t是一條由s到t的最短路徑，則vip,…,viq,…,t也是由vip到t的最短路徑。(反證即可)遞歸式推導(dǎo)設(shè)cost(i,j)是Vi中結(jié)點(diǎn)vj到匯點(diǎn)t的最小成本路徑的成本，遞歸式為：93計(jì)算過程(以5-段圖為例)cost(4,9)=4,cost(4,10)=2,cost(4,11)=∞cost(3,6)=7,cost(3,7)=5,cost(3,8)=7cost(2,2)=7,cost(2,3)=9,cost(2,4)=18,cost(2,5)=15cost(1,1)=min{9+cost(2,2),7+cost(2,3),3+cost(2,4),2+cost(2,5)}=16構(gòu)造解：解1(1,2,7,10,12)，解2(1,3,6,10,12)94953.60-1背包問題問題描述給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?960-1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題。求(x1,x2,…,xn)使目標(biāo)函數(shù)最大，其中c>0,wi>0,vi>0,1≤i≤n0-1背包問題Knapsack(1,n,c)97例：w=(w1,w2,w3)=(2,3,4)v=(v1,v2,v3)=(2,3,4)求Knapsack(1,3,6)取x=(1,0,1)時(shí)，Knapsack(1,3,6)=(v1x1+v2x2+v3x3)=1*1+2*0+5*1=6最大用窮舉法求解，時(shí)間復(fù)雜度為O(n2n)981、最優(yōu)子結(jié)構(gòu)性質(zhì)證明：(反證法)設(shè)(y1,y2,…,yn)是Knapsack(1,n,c)的一個(gè)最優(yōu)解，則(y2,…,yn)是Knapsack(2,n,c-w1y1)子問題的一個(gè)最優(yōu)解。若不然，設(shè)(z2,…,zn)是Knapsack(2,n,c-w1y1)的最優(yōu)解，因此有說明(y1,z2,…,zn)是Knap(1,n,c)的一個(gè)更優(yōu)解，矛盾。0-1背包問題Knapsack(1,n,c)滿足最優(yōu)性原理992、遞歸關(guān)系設(shè)所給0-1背包問題的子問題記為Knapsack(i,n,j)，j≤c(假設(shè)c,wi取整數(shù))Knapsack(i,n,j)的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。注：子問題的背包容量j在不斷地發(fā)生變化100由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下：臨界條件說明：當(dāng)j＜wi時(shí)，只有xi=0，則m(i,j)=m(i+1,j)當(dāng)j≥wi時(shí)，取xi=0時(shí)，為m(i+1,j)取xi=1時(shí)，為m(i+1,j-wi)+vi3、算法描述voidKnapsack(Type*v,int*w,intc,intn,Type**m){//m[1][c]為最優(yōu)值intjMax=min(w[n]-1,c);//j≤jMax,即0≤j＜wn;j>jMax,即j≥wnfor(intj=0;i<=jMax;j++)m[n][j]=0;//0≤j<wn’for(intj=w[n];i<=c;j++)m[n][j]=v[n];//j≥wn’for(inti=n-1;i>1;i--){//i>1表示對(duì)i=1暫不處理i=1時(shí)只需求m[1][c]jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//0≤j＜wi’m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)//j≥wi’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]);}102voidTraceback(Type**m,int*w,intc,intn,int*x){//輸出解X[]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])?1:0;}1034、計(jì)算復(fù)雜性分析算法復(fù)雜度分析從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例：當(dāng)c>2n時(shí)，算法需要Ω(n2n)計(jì)算時(shí)間。104由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)唯一確定。105對(duì)每一個(gè)確定的i(1≤i≤n)，用一個(gè)表p[i]存儲(chǔ)函數(shù)m(i，j)的全部跳躍點(diǎn)。表p[i]可依計(jì)算m(