算法設(shè)計(jì)與分析1ppt

1第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃第四章貪心算法第五章回朔法第六章分支限界法第七章概率算法算法設(shè)計(jì)與分析>目錄23.1 矩陣連乘問題算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃給定n個(gè)矩陣{A1,A2,…,An}，其中Ai

是一個(gè)ri-1×ri

矩陣(1≤i≤n)，即Ai×Ai+1是可乘的，求出n個(gè)矩陣相乘的最優(yōu)計(jì)算次序，使得計(jì)算量最小。兩個(gè)矩陣可乘：僅當(dāng)矩陣A和B相容時(shí)(A矩陣的列數(shù)=B矩陣的行數(shù))，A和B能相乘3算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃矩陣連乘問題:給定一個(gè)矩陣鏈<A1,A2,...,An>，其中矩陣Ai的維數(shù)為pi-1×pi

，尋找一種矩陣連乘完全加括號(hào)方式，使得矩陣連乘積的乘法次數(shù)最少注意:該問題的目的是僅僅確定最少乘法個(gè)數(shù)的矩相乘順序，而不是實(shí)際進(jìn)行矩陣相乘4窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃計(jì)算括號(hào)化方案的數(shù)量分析:對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。n=1,只有一個(gè)矩陣,只有一種方案n>1,由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：由此不難算出P(n)=C(n-1)，其中C表示卡特蘭(Catalan)數(shù)

5算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃結(jié)果:P(n)隨著n的增長(zhǎng)呈指數(shù)增長(zhǎng)k為斷開位置6動(dòng)態(tài)規(guī)劃特點(diǎn)把原始問題劃分成一系列子問題求解每個(gè)子問題僅一次，并將其結(jié)果保存在一個(gè)表中，以后用到時(shí)直接存取不重復(fù)計(jì)算，節(jié)省計(jì)算時(shí)間自底向上地計(jì)算最優(yōu)值適用范圍一類優(yōu)化問題：可分為多個(gè)相關(guān)子問題，子問題的解被重復(fù)使用算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃7算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃法根本步驟分析最優(yōu)解的結(jié)構(gòu)：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。建立遞歸關(guān)系：遞歸地定義最優(yōu)值。計(jì)算最優(yōu)值：以自底向上的方式計(jì)算出最優(yōu)值。構(gòu)造最優(yōu)解：根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃矩陣連乘問題使用的數(shù)據(jù)結(jié)構(gòu)輸入：p數(shù)組——存儲(chǔ)矩陣行列下標(biāo)處理：m數(shù)組——記錄所需要的最小連乘次數(shù)s數(shù)組——記錄最優(yōu)括號(hào)化方案的分割點(diǎn)位置9步驟1：分析最優(yōu)解的結(jié)構(gòu)將矩陣連乘積簡(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ì)算量算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃10關(guān)鍵特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k]的次序也是最優(yōu)的。反證法證明:假設(shè)存在一個(gè)計(jì)算A[i:k]的次序所需計(jì)算量更少，那么進(jìn)行替代，得到的計(jì)算A[i:j]比最優(yōu)次序所需計(jì)算量少，存在矛盾。同理，計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[k+1:j]的次序也是最優(yōu)的。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃11矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。因此任何最優(yōu)解都是由子問題實(shí)例的最優(yōu)解構(gòu)成，可以將問題A[i:j]劃分為兩個(gè)子問題A[i:k]和A[k+1:j]。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征12最優(yōu)子結(jié)構(gòu)性質(zhì)提示我們使用最優(yōu)化原那么產(chǎn)生的算法是遞歸算法。但是，簡(jiǎn)單地使用遞歸算法可能會(huì)增加時(shí)間與空間開銷。使用數(shù)組記錄已解決的子問題的答案。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃步驟二:建立遞歸關(guān)系13數(shù)組P：存放矩陣Ai的行、列數(shù)，矩陣Ai的行列值pi-1,pi，初始值為p0,p1……pn-1,pn

m[i][j]：計(jì)算A[i:j]所需要的最少乘次數(shù)，原問題為求m[1][n]；當(dāng)i=j時(shí),A[i:j]=Ai，只有一個(gè)矩陣Ai

，沒有矩陣元素相乘，因此，

m[i,i]=0，i=1,2,…,n算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃定義:14這里的維數(shù)為算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃當(dāng)i<j時(shí)設(shè)矩陣連乘Ai..j最優(yōu)全括號(hào)的分割點(diǎn)位于Ak與Ak+1之間，那么…k為最正確斷開位置15由于遞歸方程假設(shè)矩陣連乘最優(yōu)全括號(hào)問題的分隔點(diǎn)k，實(shí)際上k是未知的。k的位置只有j-i種可能，k∈{i,i+1,...,j-1}遞歸地定義m[i][j]為：算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃

的位置只有種可能16算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃步驟三:計(jì)算最優(yōu)值定義:計(jì)算A[1:n]的最小代價(jià)：s[i][j]保存Ai..j

最優(yōu)括號(hào)化方案的分割點(diǎn)位置k17intRecurMatrixChain(inti,intj){if(i==j)return0;//初始化intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];

s[i][j]=i;

for(intk=i+1;k<j;k++){intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];

//遞歸計(jì)算最優(yōu)解if(t<u){u=t;

s[i][j]=k;}}returnu;}算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃遞歸方法18算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃如果用T(n)表示該算法的計(jì)算A[1:n]的時(shí)間，則有如下遞歸關(guān)系式：可用數(shù)學(xué)歸納法直接證明：顯然不是期望結(jié)果19注意到在此問題中，對(duì)于1≤i≤j≤n不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問題。因此，不同子問題的個(gè)數(shù)最多只有由此可見，在遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算屢次。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征20用動(dòng)態(tài)規(guī)劃算法解此問題，消除重復(fù)計(jì)算，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。可以在計(jì)算過程中保存已解決的子問題的答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而防止大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃21voidmatrixChain(int*p,intn,intm[][],ints[][]){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;}}}}算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃計(jì)算m[i][j]不含對(duì)角線的上三角矩陣,利用變量i、j設(shè)置按照斜線順序計(jì)算m[i][j]初始化時(shí)i為斷開位置k從i+1到j(luò)-1循環(huán)查找,不斷替換，找到最優(yōu)值和最正確斷開位置22算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃算法復(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)。23注意:算法MatrixChain只是明確給出了矩陣最優(yōu)連乘次序所用的數(shù)乘次數(shù)m[1][n]，并未明確給出最優(yōu)連乘次序，即完全加括號(hào)方法。s[i][j]=k說明了計(jì)算連乘積A[i:j]的最正確方式應(yīng)該在矩陣Ak和Ak+1之間斷開，即最優(yōu)加括號(hào)方式為(A[i:k])(A[k+1:j])。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃步驟四:用動(dòng)態(tài)規(guī)劃法求最優(yōu)解24VoidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<“MultiplyA〞<<i<<“,〞<<s[i][j];cout<<“andA〞<<(s[i][j]+1)<<“,〞<<j<<endl;}算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃算法Traceback按算法MatrixChain計(jì)算出的斷點(diǎn)信息s指示的加括號(hào)方式輸出計(jì)算A[i:j]的最優(yōu)次序。

253.2動(dòng)態(tài)規(guī)劃算法的根本要素1.最優(yōu)子結(jié)構(gòu)矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)?？s小子問題集合，降低實(shí)現(xiàn)復(fù)雜性最優(yōu)子結(jié)構(gòu)使用自底而上地完成求解過程算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃26注意：同一個(gè)問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快〔空間占用小，問題的維度低〕算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的；然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。272.重疊子問題遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算屢次。這種性質(zhì)稱為子問題的重疊性質(zhì)。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃28動(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í)間，從而獲得較高的解題效率。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃293.備忘錄方法備忘錄方法用一個(gè)表格來保存已解決的子問題的答案,在下次需要解此問題時(shí),只要簡(jiǎn)單地查看該問題的解答,而不必重新計(jì)算.備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同遞歸方式:自頂向下算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃30IntMemoizedMatrixChain(intn,int**m,

int**s){for(inti=1;i<=n,i++)for(intj=i;j<=n,j++)m[i[j]=0;

//初始化returnlookupChain(1,n);}算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，防止了相同子問題的重復(fù)求解。intlookupChain(inti,intj){if(m[i][j]>0)returnm[i][j];

//已經(jīng)計(jì)算過,返回結(jié)果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;}31算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃表示該子問題已經(jīng)求解遞歸求解斷開位置為i時(shí)的計(jì)算量循環(huán)每個(gè)可取斷開位置求計(jì)算量323.3最長(zhǎng)公共子序列算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃應(yīng)用論文相似度檢查比較兩個(gè)不同生物體的DNAS1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAAS2=GTCGTTCGGAATGCCGTTGCTCTGTAAA研究目標(biāo)：確定兩個(gè)DNA序列的相似程度?33如何定義S1和S2的相似度?尋找第3個(gè)串S3，S3中的所有bases都包含在S1和S2中，這些bases在S1和S2中不一定連續(xù)排列，但必須是按順序排列的。S3越長(zhǎng)，那么S1和S2的相似度就越大.算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃34子序列:假設(shè)給定序列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}。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃35公共子序列:給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。例如：X=A,B,C,B,D,A,B

X=A,B,C,B,D,A,BZ1=B,C,A

Z2=B,C,B,AY=B,D,C,A,B,A

Y=B,D,C,A,B,A?算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃36問題描述：最長(zhǎng)公共子序列〔LongestCommonSubsequence，LCS)問題給定兩個(gè)序列X=<x1,x2,…,xm>和Y=<y1,y2,...,yn>,如何尋找X和Y的長(zhǎng)度最大的公共子序列。輸入：X={x1,x2,…,xm}，Y={y1,y2,...,yn}輸出：Z=X和Y最長(zhǎng)公共子序列算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃371、最長(zhǎng)公共子序列的結(jié)構(gòu)X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>原始方法列舉出X的所有子序列，逐項(xiàng)核查這些子序列是否為Y的子序列對(duì)于X的一個(gè)索引的子集{1,2,...,m}，有2m個(gè)X的子序列。需要指數(shù)運(yùn)算時(shí)間，當(dāng)序列較大時(shí)實(shí)際不可行算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃38設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，那么(1)假設(shè)xm=yn，那么zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。(2)假設(shè)xm≠yn且zk≠xm，那么Z是Xm-1和Y的最長(zhǎng)公共子序列。(3)假設(shè)xm≠yn且zk≠yn，那么Z是X和Yn-1的最長(zhǎng)公共子序列。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃39根據(jù)分析要找出序列X={x1,x2,…,xm}和Y={y1,

y2,

…,yn}的最長(zhǎng)公共子序列，可以按以下方式遞歸地進(jìn)行：當(dāng)xm=yn，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm就可以得到X和Y的最長(zhǎng)公共子序列。當(dāng)xm≠yn，找出Xm-1和Yn以及Xm和Yn-1最長(zhǎng)公共子序列，得到X和Y的最長(zhǎng)公共子序列。算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃40算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃LCSXm-1Yn-1在所考慮的子問題空間中，總共有θ(mn)個(gè)不同的子問題。41算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃2.子問題的遞歸結(jié)構(gòu)定義：c[i,j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度(c[i,j]=0,i·j=0).42建立子問題最優(yōu)值的遞歸關(guān)系：當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)c[i][j]=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃433.計(jì)算最優(yōu)值定義：b[i][j]記錄c[i][j]是由哪個(gè)子問題的解得到的。

b[i][j]=1：表示xi=yj，c[i][j]=

c[i-1][j-1]+1;b[i][j]=2：表示xi≠yj且zk≠xi

，c[i][j

]=c[i-1][j];

b[i][j]=3：表示xi≠yj且zk≠yj，

c[i][j]=c[i][j-1];算法設(shè)計(jì)與分析>動(dòng)態(tài)規(guī)劃44voidLCSLength(intm,intn,char*x,char*y,intc[][],intb[][]){inti,j;for(i=1;i<m;i++){c[i][0]=0;}

for(i=1;i<n;i++){c[0][j]=0;}//初始化

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

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