矩陣連乘問題給定n個矩陣：A1,A2,…,An，其中Ai與Ai+1是可乘的。確定一種連乘的順序，使得矩陣連乘的計算量為最小。設(shè)A和B分別是p×q和q×r的兩個矩陣，則乘積C=AB為p×r的矩陣，計算量為pqr次數(shù)乘。但是對于多于2個以上的矩陣連乘，連乘的順序卻非常重要，因為不同的順序的總計算量將會有很大的差別。1算法設(shè)計與分析矩陣連乘問題給定n個矩陣：A1,A2,…,An，其中A不同計算順序的差別設(shè)矩陣A1,A2和A3分別為10×100,100×5和5×50的矩陣，現(xiàn)要計算A1A2A3。若按((A1A2)A3)來計算，則需要的數(shù)乘次數(shù)為10×100×5+10×5×50=7500若按(A1(A2A3))來計算，則需要的數(shù)乘次數(shù)為100×5×50+10×100×50=75000后一種計算順序的計算量竟是前者的10倍！所以，求多個矩陣的連乘積時，計算的結(jié)合順序是十分重要的。2算法設(shè)計與分析不同計算順序的差別設(shè)矩陣A1,A2和A3分別為10×100不同計算順序的數(shù)量設(shè)n個矩陣的連乘積有P(n)個不同的計算順序。先在第k個和第k+1個矩陣之間將原矩陣序列分成兩個矩陣子序列，k=1，…，n；再分別對兩個子序列完全加括號，最后對結(jié)果加括號，便得到原序列的一種完全加括號方式。由此可得出關(guān)于P(n)的遞歸式：P(n)=

n=1n–1∑P(k)P(n–k)n＞1k=1

解此遞歸方程可得P(n)=C(n–1)，其中C(n)=

1

n+12nn=Ω(4n/n3/2)所以P(n)隨n的增長呈指數(shù)增長。因而窮舉搜索法不是有效的算法。3算法設(shè)計與分析不同計算順序的數(shù)量設(shè)n個矩陣的連乘積有P(n)個不同的計算順分解最優(yōu)解的結(jié)構(gòu)將矩陣連乘積AiAi+1…Aj記為A[i:j]。若A[1:n]的一個最優(yōu)解是在矩陣Ak和Ak+1處斷開的，即A[1:n]=(A[1:k]A[k+1:n])，則A[1:k]和A[k+1:n]也分別是最優(yōu)解。事實上，若A[1:k]的一個計算次序所需計算量更少的話，則用此計算次序替換原來的次序，則得到A[1:n]一個更少的計算量，這是一個矛盾。同理A[k+1:n]也是最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)：最優(yōu)解的子結(jié)構(gòu)也最優(yōu)的。4算法設(shè)計與分析分解最優(yōu)解的結(jié)構(gòu)將矩陣連乘積AiAi+1…Aj記為A[i:建立遞歸關(guān)系令m[i][j],1≤i,j≤n，為計算A[i,j]的最少數(shù)乘次數(shù)，則原問題為m[1][n]。當(dāng)i=j時，A[i,j]為單一矩陣，m[i][j]=0；當(dāng)i＜j時，利用最優(yōu)子結(jié)構(gòu)性質(zhì)有：m[i][j]=min{m[i][k]+m[k+1][j]+pi–1pkpj}i≤k＜j其中矩陣Ai，1≤i≤n，的維數(shù)為pi–1×pi。根據(jù)此遞歸式就可以直接用遞歸程序來實現(xiàn)。5算法設(shè)計與分析建立遞歸關(guān)系令m[i][j],1≤i,j≤n，為計算A直接遞歸的時間復(fù)雜性根據(jù)前面的遞歸式不難得出的時間復(fù)雜性為

n–11+∑(T(k)+T(n–k)+1)k=1

T(n)≥

n–1=1+(n–1)+∑(T(k)+T(n–k))k=1

n–1n–1=n+∑T(k)+∑T(n–k)k=1k=1

可用數(shù)學(xué)歸納法證明T(n)≥2n–1=Ω(2n)。直接遞歸算法的時間復(fù)雜性隨n的指數(shù)增長。

n–1=n+2∑T(k)k=1

6算法設(shè)計與分析直接遞歸的時間復(fù)雜性根據(jù)前面的遞歸式不難得出的時間復(fù)雜性為直接遞歸中有大量重復(fù)計算直接遞歸中有大量重復(fù)計算，如A[1:4]計算中：1:41:12:41:23:41:34:42:23:42:34:41:12:23:34:41:12:31:23:33:34:42:23:32:23:31:12:2圖中紅框標(biāo)出的都是重復(fù)計算。7算法設(shè)計與分析直接遞歸中有大量重復(fù)計算直接遞歸中有大量重復(fù)計算，如A[1:消除重復(fù)的計算要消除重復(fù)計算，可在在計算過程中保存已解決的子問題的答案。這樣，每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免重復(fù)計算。計算方式可依據(jù)遞歸式自底向上地進(jìn)行。注意到在此問題中，不同的有序?qū)?i,j)就對應(yīng)不同的子問題，因此不同的子問題個數(shù)個數(shù)最多只有Cn2+n=(n2)個。這樣便可以得到多項式時間的算法。8算法設(shè)計與分析消除重復(fù)的計算要消除重復(fù)計算，可在在計算過程中保存已解決的子自底向上的計算例如對于A1A2A3A4，依據(jù)遞歸式以自底向上的方式計算出各個子問題，其過程如下：m[1][1]m[2][2]m[3][3]m[4][4]m[1][2]m[2][3]m[3][4]m[1][3]m[2][4]m[2][4]其中m[i][i]=0m[i][i+1]=pi–1pipi+1m[i][j]=mini≤k＜j

{m[i][k]+m[k+1][j]+pi–1pkpj}例如：m[1][3]=minm[1][1]+m[2][3]+p0p1p3m[1][2]+m[3][3]+p0p2p39算法設(shè)計與分析自底向上的計算例如對于A1A2A3A4，依據(jù)遞歸式以自底向上消除重復(fù)的矩陣連乘算法VoidMatrixChain(intp,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;//將對角線元素賦值為零，即單個矩陣計算量為0for(intr=2;r<=n;r++)for(inti=1;i<=n–r+1;i++){intj=i+r–1;(5)m[i][j]=m[i+1][j]+p[i–1]*p[i]*p[j];

//計算A[i,j]=A[i:i]A[i+1:j]s[i][j]=i;//記下斷點(diǎn)i(7)for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i–1]*p[k]*p[j];

//對i<k<j,逐個計算A[i,j]=A[i:k]A[k+1:j]if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}

//記下較小的m[i][j]及相應(yīng)的斷點(diǎn)k

}}}第(5)步與第(7)步能否合在一起?能。此處分開是為了給m[i][j]賦初值。10算法設(shè)計與分析消除重復(fù)的矩陣連乘算法VoidMatrixChain(inMatrixChain的運(yùn)行舉例設(shè)要計算矩陣連乘積A1A2A3A4A5A6，其維數(shù)分別為35×35,35×15,15×5,5×10,10×20,20×25,即p0=35,p1=35,p2=15,p3=5,p4=10,p5=20,p6=25。

MatrixChain用矩陣m[i][j],s[i][j]存放子問題A[i:j]的最小計算量以及相應(yīng)的斷點(diǎn)。123456

123456m[i][j]123456123456s[i][j]MatrixChain將如下面紅色箭頭所示的過程逐個計算子問題A[i:j]：執(zhí)行for(inti=1;i<=n;i++)m[i][i]=0后將對角線元素全部置零，即子問題A[i][i]=0。000000當(dāng)r=2，執(zhí)行第(5)句完成了相鄰矩陣A[i][i+1]=p[i–1]*p[i]*p[j]的計算，并在s[i][j]中添入了相應(yīng)的斷點(diǎn)。其中的第(7)句因為j=i+1(k=i+1)而被跳過去了，實際并沒有執(zhí)行。1575026257501000500012345當(dāng)r=3，i=1時，執(zhí)行第(5)句計算A[1:1][2:3]，m[1][3]=m[2][3]+p[0]*p[1]*p[3]=2625+30*35*5=787578751執(zhí)行第(7)句計算A[1:2][3:3]，t=m[1][2]+m[3][3]+p[0]*p[2]*p[3]=15750+0+35*15*5=18375＞7875，所以m[1][3]不變，斷點(diǎn)仍為1。當(dāng)r=3，i=2時，執(zhí)行第(5)句計算A[2:2][3:4]，m[2][4]=m[3][4]+p[1]*p[2]*p[4]=750+35*15*10=600060002執(zhí)行第(7)句計算A[2:3][4:4]，t=m[2][3]+m[4][4]+p[1]*p[3]*p[4]=2625+0+35*5*10=4375＜6000，所以m[2][4]改為4375，斷點(diǎn)改為3。43753當(dāng)r=3，i=3時，執(zhí)行第(5)句計算A[3:3][4:5]，m[3][5]=m[4][5]+p[2]*p[3]*p[5]=1000+15*5*20=250025003執(zhí)行第(7)句計算A[3:4][5:5]，t=m[3][4]+m[5][5]+p[2]*p[4]*p[5]=750+0+15*10*20=3750＞2500，所以m[3][5]仍為2500，斷點(diǎn)仍為3。當(dāng)r=3，i=4時，執(zhí)行第(5)句計算A[4:4][5:6]，m[4][6]=m[5][6]+p[3]*p[4]*p[6]=5000+5*10*25=625062504執(zhí)行第(7)句計算A[4:5][6:6]，t=m[4][5]+m[6][6]+p[3]*p[5]*p[6]=1000+0+5*20*25=3500＜6250，所以m[4][6]改為3500，斷點(diǎn)改為5。35005類似的，當(dāng)r=4、5、6時，可以計算出相應(yīng)的m[i][j]及其相應(yīng)的斷點(diǎn)s[i][j]，如下圖中所示：937537125353753118753105003151253由m[1][6]=15125可知這6個矩陣連乘積的最小運(yùn)算次數(shù)為15125。由s[1][6]=3可知A[1:6]的最優(yōu)計算次序為A[1:3]A[4:6]；由s[1][3]=1可知A[1:3]的最優(yōu)計算次序為A[1:1]A[2:3]；由s[4][6]=5可知A[4:6]的最優(yōu)計算次序為A[4:5]A[6:6]；因此最優(yōu)計算次序為：(A1(A2A3))((A4A5)A6)。11算法設(shè)計與分析MatrixChain的運(yùn)行舉例設(shè)要計算矩陣連乘積A1MatrixChain的時間復(fù)雜性算法MatrixChain的主要計算取決于程序中對r、i和k的三重循環(huán)。循環(huán)體內(nèi)的計算量為O(1)，1≤r、i、k≤n，三重循環(huán)的總次數(shù)為O(n3)。因此該算法時間復(fù)雜性的上界為O(n3)，比直接遞歸算法要有效得多。算法使用空間顯然為O(n2)。這種算法稱為動態(tài)規(guī)劃。12算法設(shè)計與分析MatrixChain的時間復(fù)雜性算法MatrixChain動態(tài)規(guī)劃的基本思想將原問題分解為若干個子問題，先求子問題的解，然后從這些子問題的解得到原問題的解。這些子問題的解往往不是相互獨(dú)立的。在求解的過程中，許多子問題的解被反復(fù)地使用。為了避免重復(fù)計算，動態(tài)規(guī)劃算法采用了填表來保存子問題解的方法。在算法中用表格來保存已經(jīng)求解的子問題的解，無論它是否會被用到。當(dāng)以后遇到該子問題時即可查表取出其解，避免了重復(fù)計算。13算法設(shè)計與分析動態(tài)規(guī)劃的基本思想將原問題分解為若干個子問題，先求子問題的解動態(tài)規(guī)劃的基本要素最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解是由其子問題的最優(yōu)解所構(gòu)成的。重疊子問題：子問題之間并非相互獨(dú)立的，而是彼此有重疊的。最優(yōu)子結(jié)構(gòu)性質(zhì)使我們能夠以自底向上的方式遞歸地從子結(jié)構(gòu)的最優(yōu)解構(gòu)造出問題的最優(yōu)解。因為子問題重疊，所以存在著重復(fù)計算。這樣就可以用填表保存子問題解的方法來提高效率。14算法設(shè)計與分析動態(tài)規(guī)劃的基本要素最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解是由其子問題的最優(yōu)動態(tài)規(guī)劃的基本方法動態(tài)規(guī)劃通?？梢园匆韵聨讉€步驟進(jìn)行：(1)找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；(2)遞歸地定義最優(yōu)值；(3)以自底向上的方式計算出各子結(jié)構(gòu)的最優(yōu)值并添入表格中保存；(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。步驟1~3是動態(tài)規(guī)劃算法的基本步驟。若需要最優(yōu)解，則必須執(zhí)行第4步，為此還需要在第3步中記錄構(gòu)造最優(yōu)解所必需的信息。15算法設(shè)計與分析動態(tài)規(guī)劃的基本方法動態(tài)規(guī)劃通?？梢园匆韵聨讉€步驟進(jìn)行：15算動態(tài)規(guī)劃的備忘錄方法動態(tài)規(guī)劃中采用自底向上的方式。但是在遞歸定義中往往是自上而下的描述。備忘錄方法就采用與遞歸定義一致的自上而下的方式。備忘錄方法同樣用表格來保存已解子問題的信息。每個子問題初始化時都標(biāo)記為尚未求解。在遞歸求解過程中，對每個待解子問題，先查看它是否已求解。若未求解，則計算其解并填表保存。若已求解，則查表取出相應(yīng)的結(jié)果。備忘錄方法同樣避免了子問題的重復(fù)計算，因而和動態(tài)規(guī)劃算法具有同樣效率。16算法設(shè)計與分析動態(tài)規(guī)劃的備忘錄方法動態(tài)規(guī)劃中采用自底向上的方式。但是在遞歸凸多邊形最優(yōu)三角剖分凸多邊形的三角剖分是將一個凸多邊形分割成互不相交的三角形的弦的集合T。下面是一個凸7邊形的2個不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6在凸多邊形的一個三角剖分T中，各弦互不相交，且T已達(dá)到最大，即任何一條不在T中的弦必與T中某弦相交。在有n個頂點(diǎn)的凸多邊形的中三角剖分中，恰有n–3條弦和n–2個三角形。凸多邊形的最優(yōu)三角剖分問題：給定凸多邊形P={v0,v1,…,vn–1}，以及定義在由凸多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的一個三角剖分，使得該剖分中諸三角形上權(quán)之和為最小。可定義三角形上各種各樣的權(quán)函數(shù)w。例如w(vivjvk)=|vivj|+|vjvk|+|vkvi|，其中|vivj|是點(diǎn)vi到vj的歐氏距離。相應(yīng)于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。17算法設(shè)計與分析凸多邊形最優(yōu)三角剖分凸多邊形的三角剖分是將一個凸多邊形分割成三角剖分與矩陣連乘積同構(gòu)三角剖分問題和矩陣連乘積問題都對應(yīng)于一個完全二叉樹，也稱為表達(dá)式的語法樹。0123A1A44A2A3A5A6((A1(A2A3))(A4(A5A6))所對應(yīng)的二叉樹v1v0v2v3v4v5v6012A13A2A3A44A5A6凸多邊形v0v1v2v3v4v5v6一個三角剖分所對應(yīng)的二叉樹n個矩陣連乘積計算順序同構(gòu)于n個葉子的完全二叉樹，凸(n+1)邊形三角剖分同構(gòu)于n個葉子的完全二叉樹，所以n個矩陣連乘積的計算順序問題同構(gòu)于凸(n+1)邊形的三角剖分問題。事實上，矩陣連乘積最優(yōu)計算順序問題相當(dāng)于是凸多邊形最優(yōu)三角剖分問題中一種特殊定義的權(quán)函數(shù)的情形。18算法設(shè)計與分析三角剖分與矩陣連乘積同構(gòu)三角剖分問題和矩陣連乘積問題都對應(yīng)于最優(yōu)子結(jié)構(gòu)性質(zhì)能應(yīng)用動態(tài)規(guī)劃求解的問題應(yīng)具有最優(yōu)子結(jié)構(gòu)性質(zhì)。凸多邊形最優(yōu)三角剖分問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實上，若凸(n+1)邊形P={v0,v1,…,vn}的一個最優(yōu)三角剖分T包含了三角形v0vkvn，1≤k＜n，則T的權(quán)為三角形v0vkvn，多邊形{v0,v1,…,vk}和多邊形{vk,vk+1,…,vn}的權(quán)之和。顯然這兩個子多邊形的三角剖分也是最優(yōu)的。因為，其中若有一個子多邊形的三角剖分不是最優(yōu)的將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。19算法設(shè)計與分析最優(yōu)子結(jié)構(gòu)性質(zhì)能應(yīng)用動態(tài)規(guī)劃求解的問題應(yīng)具有最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義t[i][j],1≤i<j≤n,為子多邊形{vi–1,vi,…,vj}的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值，并為方便起見，設(shè)退化的多邊形{vi–1,vi}的權(quán)值為0。于是凸(n+1)邊形的最優(yōu)三角剖分為t[1][n]易知，t[i][j]可遞歸定義為當(dāng)i=j時，為退化多邊形{vi–1,vi}，t[i][j]=0；當(dāng)i＜j時，利用最優(yōu)子結(jié)構(gòu)性質(zhì)有：t[i][j]=min{t[i][k]+t[k+1][j]+w(vi–1vkvj)}i≤k＜j與矩陣連乘積問題相對比：m[i][j]=min{m[i][k]+m[k+1][j]+pi–1pkpj}i≤k＜j顯然，矩陣連乘積的最優(yōu)計算順序與凸多邊形最優(yōu)三角剖分具有完全相同的遞歸結(jié)構(gòu)。20算法設(shè)計與分析最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義t[i][j],1≤i<j≤n,最優(yōu)三角剖分的算法由于凸多邊形最優(yōu)三角剖分與矩陣連乘積的最優(yōu)計算順序具有完全相同的遞歸結(jié)構(gòu)，其區(qū)別僅在于權(quán)函數(shù)的不同，所以只需要修改求矩陣連乘積的最優(yōu)計算順序的算法中的權(quán)函數(shù)計算便可得到凸多邊形最優(yōu)三角剖分的算法。顯然該算法的時間復(fù)雜性也是O(n3)。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<j;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;}}}}//程序中紅色的部分為改動的地方21算法設(shè)計與分析最優(yōu)三角剖分的算法由于凸多邊形最優(yōu)三角剖分與矩陣連乘積的最優(yōu)多邊形游戲有一個n邊形，每個頂點(diǎn)被賦予一整數(shù)值，每條邊上被賦予一個運(yùn)算符“+”或“*”。游戲的第1步，將一條邊刪去；隨后的n–1步按以下方式操作：(1)選擇一條邊E及其所連接的兩個頂點(diǎn)v1和v2；(2)

用一個新頂點(diǎn)取代邊E以及頂點(diǎn)v1和v2，賦予新頂點(diǎn)的值為頂點(diǎn)v1和v2的值通過邊E上的運(yùn)算所得到的值。最后所有的邊被刪去，所剩頂點(diǎn)的值即為得分。22算法設(shè)計與分析多邊形游戲有一個n邊形，每個頂點(diǎn)被賦予一整數(shù)值，每條邊上被賦多邊形游戲的表達(dá)設(shè)所有的邊依次從1到n編號，按順時針序列為op[1],v[1],op[2],v[2],…,op[n],v[n]

其中op[i]為邊i上的運(yùn)算符，v[i]頂點(diǎn)i上的值。將多邊形中始于頂點(diǎn)i(1≤i≤n)，長度為j的順時針鏈v[i],op[i+1],…,v[i+j–1]表示為p(i,j)。若鏈p(i,j)最后一次合并在op[i+s](1≤s≤j–1)處發(fā)生，則被分割為兩個子鏈p(i,s)和p(i+s,j–s)23算法設(shè)計與分析多邊形游戲的表達(dá)設(shè)所有的邊依次從1到n編號，按順時針序列為將多邊形游戲的最優(yōu)子結(jié)構(gòu)性質(zhì)若鏈p(i,j)取最優(yōu)值的最后一次合并是在op[i+s]處發(fā)生的，則子鏈p(i,s)和p(i+s,j–s)也是最優(yōu)。因為若子鏈p(i,s)和p(i+s,j–s)不是最優(yōu)的，則可推出鏈p(i,j)也不是最優(yōu)的矛盾。所以多邊形游戲具有最優(yōu)子結(jié)構(gòu)性質(zhì)。但是這里的最優(yōu)子結(jié)構(gòu)要稍微地復(fù)雜一點(diǎn)。若p(i,j)的最后合并的邊op[i+s]=“+”，子鏈p(i,s)和p(i+s,s)應(yīng)該取最大值，若p(i,j)的最后合并的邊op[i+s]=“*”，子鏈p(i,s)和p(i+s,j–s)是否仍然取最大值呢？不見得！24算法設(shè)計與分析多邊形游戲的最優(yōu)子結(jié)構(gòu)性質(zhì)若鏈p(i,j)取最優(yōu)值的最后一多邊形游戲的最優(yōu)子結(jié)構(gòu)分析設(shè)m1是對子鏈p(i,s)的任意合并方式得到的值，a和b是其最小值和最大值，m2是對子鏈p(i+s,j–s)的任意合并方式得到的值，c和d分別是最小值和最大值，即a≤m1≤b，c≤m2≤d。若op[i+s]=“+”，則a+c≤m≤b+d?？梢妏(i,s)的最小、最大值分別對應(yīng)于子鏈的最小、最大值。若op[i+s]=“*”，由于v[i]可取負(fù)整數(shù)，所以

min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}。即主鏈最小、最大值亦來自子鏈最小、最大值。25算法設(shè)計與分析多邊形游戲的最優(yōu)子結(jié)構(gòu)分析設(shè)m1是對子鏈p(i,s)的任意多邊形游戲的遞歸求解由前面的分析可知，為了求鏈合并的最大值，必須同時求子鏈合并的最大值和最小值。因此整個計算過程中應(yīng)同時計算最大值和最小值。設(shè)鏈p(i,j)合并的最大、最小值分別是m[i,j,0]和m[i,j,1]，最優(yōu)合并處是在op[i+s]，且長度小于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]，則⑴當(dāng)op[i+s]=“+”時，m[i,j,0]=a+c，m[i,j,1]=b+d⑵當(dāng)op[i+s]=“*”時，m[i,j,0]=min{ac,ad,bc,bd}m[i,j,1]=max{ac,ad,bc,bd}26算法設(shè)計與分析多邊形游戲的遞歸求解由前面的分析可知，為了求鏈合并的最大值，多邊形游戲的遞歸求解令p(i,j)在op[i+s]斷開的最大值和最小值分別為maxf(i,j,s)和minf(i,j,s)，綜合上面的討論則minf(i,j,s)=a+cop[i+s]=“+”min{ac,ad,bc,bd}op[i+s]=“*”maxf(i,j,s)=b+dop[i+s]=“+”max{ac,ad,bc,bd}op[i+s]=“*”由于p(i,j)的最優(yōu)斷開位置s有1≤s≤j–1的j–1中情況，于是便可得到求解多邊形游戲的遞歸式：27算法設(shè)計與分析多邊形游戲的遞歸求解令p(i,j)在op[i+s]斷開的最求解多邊形游戲的遞歸式由于多邊形是封閉的，當(dāng)i+s＞n時，頂點(diǎn)i+s實際編號應(yīng)為(i+s)modn。多邊形游戲的最大得分即為m[i,n,1]。

m[i,j,0]=min{minf(i,j,s)},1≤i,j≤n

1≤s≤jm[i,j,1]=max{maxf(i,j,s)},1≤i,j≤n

1≤s≤j初始邊界值為：

m[i,1,0]=m[i,1,1]=v[i],1≤i≤n,j=128算法設(shè)計與分析求解多邊形游戲的遞歸式由于多邊形是封閉的，當(dāng)i+s＞n時，頂多邊形游戲的動態(tài)規(guī)劃算法依據(jù)上述討論以及所得的遞歸式，不難寫出多邊形游戲動態(tài)規(guī)劃算法。請同學(xué)們自己編寫。算法的主程序為Poly_Max，它包含了一個子程序MIN_MAX。子程序MIN_MAX負(fù)責(zé)對確定s的minf(i,j,s)和maxf(i,j,s)的計算。而對任意鏈的最大值m[i,j,1]和最小值m[i,j,0]的計算則是在主程序Poly_Max中進(jìn)行的。算法的時間復(fù)雜性顯然仍為O(n3)。29算法設(shè)計與分析多邊形游戲的動態(tài)規(guī)劃算法依據(jù)上述討論以及所得的遞歸式，不難寫DNA序列的相似性將序列A、B表示為對偶(a,b)的序列。其中若：1、aA和bB稱為替換，a=b稱為匹配，否則稱為不匹配，其得分為σ(a,b)；2、aA，b是空位為刪除空白；3、a是空位，bB為插入空白；對于長度為k的空位，其得分為–(q+kr)。

這里，參數(shù)σ(a,b)、q和r由用戶確定。兩個序列A、B的相似性為所有這樣的對偶序列中最高的得分。30算法設(shè)計與分析DNA序列的相似性將序列A、B表示為對偶(a,b)的序列。DNA序列的相似性若給定兩個DNA序列：

AGCTACGTACACTACCAGCTATCGTACTAGC下面是其一個相似性序列：

AGCTA–CGTACACTACCAGCTATCGTAC––TAGC其中有13個匹配、1個不匹配、一個長度為1的插入空白和一個長度為2的刪除空白。若：a=b時σ(a,b)=10；a

b時σ(a,b)=–20；

q=40；r=2。該相似性序列的得分為

10*13–20–(40+2)–(40+2*2)=2431算法設(shè)計與分析DNA序列的相似性若給定兩個DNA序列：下面是其一個相似性序遞歸求序列相似性設(shè)A=a1a2…am，B=b1b2…bn。令S(m,n)為A和B的相似性，即各種對偶序列最大的得分。為了采用遞歸方法來求解此問題，我們從序列尾部來考慮，那么有三種方案：①尾部用替換，即最后一個對偶為(am,bn)；②尾部用刪除空白，即最后一個對偶為(am,–)；③尾部用插入空白，即最后一個對偶為(–,bn)。令S(m,n)、D(m,n)和I(m,n)分別為三種方案的得分，則其相似性應(yīng)為三種方案的最大得分。32算法設(shè)計與分析遞歸求序列相似性設(shè)A=a1a2…am，B=b1b2…遞歸求序列相似性S(m,n)=S(m–1,n–1)+σ(am,bn)。若用方案①，即尾部用替換，則

D(m,n)=S(m–1,n)–q–r或者，D(m,n)=D(m–1,n)–r若用方案②，即尾部用刪除空白，則

I(m,n)=S(m,n–1)–q–r或者，I(m,n)=I(m,n–1)–r若用方案③，即尾部用插入空白，則33算法設(shè)計與分析遞歸求序列相似性S(m,n)=S(m–1,n–遞歸求序列相似性現(xiàn)在考慮非遞歸分支：S(0,0)=0、S(m,0)=D(m,0)、S(0,n)=I(0,n)。對方案①，有D(m,0)=D(m–1,0)–r、D(0,n)=S(0,n)–q。對方案②，有I(m,0)=S(m,0)–q、I(0,n)=S(0,n–1)–q。對方案③，有34算法設(shè)計與分析遞歸求序列相似性現(xiàn)在考慮非遞歸分支：S(0,0)=0、遞歸求序列相似性S(m,n)=0m=0,n=0D(m,0)forn0I(0,n)form0max{S(m–1,n–1)+σ(am,bn),D(m,n),I(m,n)}D(m,n)=S(0,n)–qforn

0D(m–1,0)–rform0max{S(m–1,n)–q-r,D(m–1,n)–r}I(m,n)=S(m,0)–qform

0I(0,n–1)–rforn0max{S(m,n–1)–q-r,I(m–1,n)–r}35算法設(shè)計與分析遞歸求序列相似性S(m,n)=0動態(tài)規(guī)劃求序列相似性如果用遞歸算法求序列的相似性，其時間復(fù)雜性顯然是指數(shù)級的?？紤]采用動態(tài)規(guī)劃法。為此，需要⑴用矩陣S[0:m,0:n]、D[0:m,0:n]和I[0:m,0:n]來分別記載對應(yīng)于子序列Ai和Bj的得分S(i,j)、D(i,j)和I(i,j)，0im，0jn。⑵從(0,0)開始逐個計算S(i,j)、D(i,j)和I(i,j)并將結(jié)果記入S[i,j]、D[i,j]和I[i,j]。⑶必要時，是用輔助矩陣記載每步的方案。36算法設(shè)計與分析動態(tài)規(guī)劃求序列相似性如果用遞歸算法求序列的相似性，其時間復(fù)雜動態(tài)規(guī)劃法的遞歸式S(i,j)=0m=0,n=0D(i,0)forj0I(0,j)fori0max{S(i–1,j–1)+σ(ai,bj),D(i,j),I(i,j)}D(i,j)=S(0,j)–qforj

0D(i–1,0)–rfori0max{S(i–1,j)–q-r,D(i–1,j)–r}I(i,j)=S(i,0)–qfori

0I(0,j–1)–rforj0max{S(i,j–1)–q-r,I(i–1,j)–r}37算法設(shè)計與分析動態(tài)規(guī)劃法的遞歸式S(i,j)=0動態(tài)規(guī)劃法求序列相似性Alignment(intm,intn,charA[m],charB[n])intS[m][n],D[m][n],I[m][n];{

初始化；從(i,j)=(1,1)到(m,n)逐個計算并填寫

D[i,j]、I[i,j]和S[i,j]；

輸出S(m,n);}38算法設(shè)計與分析動態(tài)規(guī)劃法求序列相似性Alignment(intm,in遞歸式中的數(shù)據(jù)依賴由遞歸式可知S(i,j)依賴于S(i–1,j–1)、D(i,j)和I(i,j)。

S(i,j)=0m=0,n=0D(i,0)forj0I(0,j)fori0max{S(i–1,j–1)+σ(ai,bj),D(i,j),I(i,j)}S(i–1,j–1)D(i,j)I(i,j)S(i,j)由遞歸式可知D(i,j)依賴于S(i–1,j)、D(i–1,j)。D(i,j)=S(0,j)–qforj

0D(i–1,0)–rfori0max{S(i–1,j)–q-r,D(i–1,j)–r}S(i–1,j)D(i–1,j)D(i,j)由