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

算法設(shè)計(jì)與分析動(dòng)態(tài)規(guī)劃第四章2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析1第一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析2矩陣連乘問(wèn)題給定n個(gè)矩陣：A1,A2,…,An，其中Ai與Ai+1是可乘的。確定一種連乘的順序，使得矩陣連乘的計(jì)算量為最小。設(shè)A和B分別是p×q和q×r的矩陣，則乘積C=AB為p×r的矩陣，計(jì)算量為pqr次數(shù)乘。但是對(duì)于多于2個(gè)以上的矩陣連乘，連乘的順序卻非常重要，因?yàn)椴煌捻樞虻目傆?jì)算量將會(huì)有很大的差別。第二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析3不同計(jì)算順序的差別設(shè)矩陣A1,A2和A3分別為10×100,100×5和5×50的矩陣，現(xiàn)要計(jì)算A1A2A3。若按((A1A2)A3)來(lái)計(jì)算，則需要的數(shù)乘次數(shù)為10×100×5+10×5×50=7500若按(A1(A2A3))來(lái)計(jì)算，則需要的數(shù)乘次數(shù)為100×5×50+10×100×50=75000兩種計(jì)算順序的計(jì)算量竟然相差10倍！計(jì)算順序通過(guò)加括號(hào)來(lái)實(shí)現(xiàn)第三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析4不同計(jì)算順序的數(shù)量設(shè)n個(gè)矩陣的連乘有P(n)個(gè)不同的計(jì)算順序。先在第k個(gè)和第k+1個(gè)矩陣之間將原矩陣序列分成兩個(gè)矩陣子序列，k=1，…，n；再分別對(duì)兩個(gè)子序列完全加括號(hào)，最后對(duì)結(jié)果加括號(hào)，便得到原序列的一種完全加括號(hào)方式。第四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析5不同計(jì)算順序的數(shù)量設(shè)n個(gè)矩陣的連乘有P(n)個(gè)不同的計(jì)算順序。由此可得出關(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的增長(zhǎng)呈指數(shù)增長(zhǎng)。第五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析6分解最優(yōu)解的結(jié)構(gòu)將AiAi+1…Aj的矩陣連乘問(wèn)題記為A[i:j]。設(shè)A[1:n]的一個(gè)最優(yōu)解是在Ak和Ak+1處斷開(kāi)的，即A[1:n]=(A[1:k]A[k+1:n])，則A[1:k]和A[k+1:n]也分別是其最優(yōu)解。否者，若有A[1:k]的一個(gè)計(jì)算次序的計(jì)算量更少的話，則用此計(jì)算次序替換原來(lái)的次序，則得到A[1:n]一個(gè)更少計(jì)算量。矛盾。同理A[k+1:n]也是最優(yōu)解。第六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析7最優(yōu)子結(jié)構(gòu)性質(zhì)A1A2…An的矩陣連乘問(wèn)題，即A[1:n]，的最優(yōu)解中的子問(wèn)題A[1:k]和A[k+1:n]的解也是該子問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)：如果某問(wèn)題的每個(gè)最優(yōu)解中的子問(wèn)題的解也是最優(yōu)的，則稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。換言之，滿足最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題的最優(yōu)解是由子問(wèn)題的最優(yōu)解構(gòu)成的。第七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析8建立遞歸關(guān)系令m[i][j],1≤i,j≤n，為計(jì)算A[i,j]的最少數(shù)乘次數(shù)，則原問(wèn)題為m[1][n]。當(dāng)i=j時(shí)，A[i,j]為單一矩陣，m[i][j]=0；當(dāng)i＜j時(shí)，利用最優(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。只需數(shù)組P[n+1]就可存放各矩陣的行列數(shù)。注意：因?yàn)檫@n個(gè)矩陣可乘，故后一個(gè)矩陣的行數(shù)就是一個(gè)矩陣的列數(shù)。P[0]為A1的行數(shù),P[1]為A1的列數(shù)，也是A2的行數(shù),以此類(lèi)推。最后的P[n]是An的列數(shù)。第八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析9遞歸的執(zhí)行過(guò)程該遞歸自頂向下地執(zhí)行，如A[1:4]計(jì)算：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第九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析10直接遞歸的時(shí)間復(fù)雜性根據(jù)該遞歸式不難得出的時(shí)間復(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–1

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

k=1

k=1該遞歸算法的時(shí)間復(fù)雜性為O(2n)。

n–1

=n+2∑T(k)

k=1

用數(shù)學(xué)歸納法可證T(n)≥2n–1=O(2n)。第十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析11遞歸的執(zhí)行過(guò)程在此遞歸的執(zhí)行中有大量重復(fù)計(jì)算：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紅色的都是重復(fù)計(jì)算！第十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析12子問(wèn)題個(gè)數(shù)最多為O(n2)可在計(jì)算過(guò)程中保存已解子問(wèn)題的答案。這樣，每個(gè)子問(wèn)題只要計(jì)算一次，而在后面需要該子問(wèn)題答案時(shí)只要簡(jiǎn)單查一下，從而避免了重復(fù)計(jì)算。計(jì)算方式可從最簡(jiǎn)單的子問(wèn)題開(kāi)始，依據(jù)遞歸式自底向上地進(jìn)行。此問(wèn)題中不同有序?qū)?i,j)就對(duì)應(yīng)不同子問(wèn)題，故子問(wèn)題個(gè)數(shù)最多有C

+n=O(n2)個(gè)。n2第十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析13自底向上的計(jì)算例如對(duì)于A1A2A3A4，依據(jù)遞歸式以自底向上的方式計(jì)算出各個(gè)子問(wèn)題，其過(guò)程如下：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[1][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}最簡(jiǎn)單情況是單個(gè)矩陣的計(jì)算。第十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析14自底向上的計(jì)算例如對(duì)于A1A2A3A4，依據(jù)遞歸式以自底向上的方式計(jì)算出各個(gè)子問(wèn)題，其過(guò)程如下：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[1][4]m[i][i]=0m[i][i+1]=pi–1pipi+1例如：m[1][3]=minm[1][1]+m[2][3]+p0p1p3m[1][2]+m[3][3]+p0p2p3第十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析15自底向上的計(jì)算例如對(duì)于A1A2A3A4，依據(jù)遞歸式以自底向上的方式計(jì)算出各個(gè)子問(wèn)題，其過(guò)程如下：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[1][4]m[i][i]=0m[i][i+1]=pi–1pipi+1例如：m[1][4]=m[1][1]+m[2][4]+p0p1p4m[1][2]+m[3][4]+p0p2p4m[1][3]+m[4][4]+p0p3p4min第十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析16自底向上的計(jì)算例如對(duì)于A1A2A3A4，依據(jù)遞歸式以自底向上的方式計(jì)算出各個(gè)子問(wèn)題，其過(guò)程如下：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[1][4]這層的斷點(diǎn)為0個(gè)。這層的斷點(diǎn)為1個(gè)。這層的斷點(diǎn)為2個(gè)。這層的斷點(diǎn)為3個(gè)。第十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析17矩陣連乘算法給矩陣連乘算法取個(gè)名字MatrixChain。第十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析18矩陣連乘算法MatrixChain(形參表）{初始化；自底向上地計(jì)算每一個(gè)m[i][j]并將結(jié)果填入表中。}底是m[i][i]，即對(duì)角線元素。最頂層是m[1][n]。初始化是將m[i][i]，即對(duì)角線元素，賦值為0。第十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析19矩陣連乘算法的數(shù)據(jù)結(jié)構(gòu)形參表中應(yīng)有n和P[n+1]。算法需要兩個(gè)二維數(shù)組：二維矩陣m[n][n]。其每個(gè)元素m[i][j],1≤i,j≤n，為A[i,j]的最少數(shù)乘次數(shù)。二維矩陣s[n][n]，其元素s[i][j],1≤i,j≤n，為計(jì)算A[i,j]的斷點(diǎn)位置。第十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析20矩陣連乘算法MatrixChain(n,P[n+1]）{初始化：將m[i][i]賦值為0。for(i=1;i<=n;i++)m[i][i]=0;第二十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析21矩陣連乘算法MatrixChain(n,P[n+1]）{

for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)for(i=1;i<=n–r+1;i++){j=i+r–1;for(k=i;k<j;k++){t=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;}}}}從第二層開(kāi)始，對(duì)(i,j)間的每個(gè)斷點(diǎn)k，計(jì)算m[i,j]=m[i:k]m[k+1:j]+p[i–1]*p[k]*p[j]，并記下較小的m[i][j]及相應(yīng)的斷點(diǎn)k。第二十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析22矩陣連乘算法MatrixChain(n,P[n+1]）{

for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)for(i=1;i<=n–r+1;i++){j=i+r–1;for(k=i;k<j;k++){t=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;}}}}當(dāng)r=2，對(duì)每個(gè)i，j為i+1，最內(nèi)層循環(huán)僅執(zhí)行一次，計(jì)算相鄰兩個(gè)矩陣的數(shù)乘次數(shù)，即A[i,i+1]=A[i,i]+A[i+1,i+1]+p[i–1]*p[i]*p[i+1]。第二十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析23矩陣連乘算法MatrixChain(n,P[n+1]）{

for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)for(i=1;i<=n–r+1;i++){j=i+r–1;for(k=i;k<j;k++){t=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;}}}}當(dāng)r>2，每對(duì)(i,j)中的斷點(diǎn)k有r–1個(gè)，越往高層斷點(diǎn)數(shù)目越多。這樣自底向上完成整個(gè)m[i][j]的計(jì)算。第二十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析24矩陣連乘算法MatrixChain(n,P[n+1]）{

for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)for(i=1;i<=n–r+1;i++){j=i+r–1;for(k=i;k<j;k++){t=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;}}}}第二十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析25MatrixChain的運(yùn)行舉例MatrixChain用矩陣m[i][j],s[i][j]存放子問(wèn)題A[i:j]的最小計(jì)算量以及相應(yīng)的斷點(diǎn)。123456

123456m[i][j]123456s[i][j]第二十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析26MatrixChain的運(yùn)行舉例MatrixChain將如下面紅色箭頭所示的過(guò)程逐個(gè)計(jì)算子問(wèn)題A[i:j]：。123456

123456m[i][j]123456s[i][j]第二十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析27MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]設(shè)要計(jì)算矩陣連乘積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。第二十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析28MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]執(zhí)行for(inti=1;i<=n;i++)m[i][i]=0后將對(duì)角線元素全部置零，即子問(wèn)題A[i][i]=0。000000第二十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析29MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=2，對(duì)每個(gè)i，最內(nèi)層循環(huán)執(zhí)行一次，完成相鄰矩陣數(shù)乘次數(shù)計(jì)算，即A[i][i+1]=p[i–1]*p[i]*p[j]，并在s[i][j]中添入了相應(yīng)的斷點(diǎn)。0000001575012625275031000450005第二十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析30MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=1時(shí)，斷點(diǎn)k有兩個(gè)：對(duì)斷點(diǎn)k=1，計(jì)算A[1:1]A[2:3]有m[1][3]=m[2][3]+p[0]*p[1]*p[3]=2625+30*35*5=7875000000157501262527503100045000578751第三十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析31MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=1時(shí)，斷點(diǎn)k有兩個(gè)：000000157501262527503100045000578751對(duì)斷點(diǎn)k=2，計(jì)算A[1:2]A[3:3]有m[1][3]=m[1][2]+m[3][3]+p[0]*p[2]*p[3]=15750>7857。m[1][3]仍為7857。第三十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析32MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=2時(shí)，斷點(diǎn)k有兩個(gè)：000000157501262527503100045000578751對(duì)斷點(diǎn)k=2，計(jì)算A[2:4]有m[2][4]=m[3][4]+p[1]*p[2]*p[4]=750+35*15*10=6000。60002第三十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析33MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=2時(shí)，斷點(diǎn)k有兩個(gè)：000000157501262527503100045000578751對(duì)斷點(diǎn)k=3，計(jì)算A[2:3]A[4:4]有m[2][4]=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。6000243753第三十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析34MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=3時(shí)，斷點(diǎn)k有兩個(gè)：000000157501262527503100045000578751對(duì)斷點(diǎn)k=3，計(jì)算A[3:3]A[4:5]有m[3][5]=m[4][5]+m[4][5]+p[2]*p[3]*p[5]=1000+15*5*20=2500。4375325003第三十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析35MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=3時(shí)，斷點(diǎn)k有兩個(gè)：000000157501262527503100045000578751對(duì)斷點(diǎn)k=4，計(jì)算A[3:4]A[5:5]有m[3][5]=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。4375325003第三十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析36MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=4時(shí)，斷點(diǎn)k有兩個(gè)：000000157501262527503100045000578751對(duì)斷點(diǎn)k=4，計(jì)算A[4:4]A[5:6]有m[4][6]=m[4][4]+m[5][6]+p[3]*p[4]*p[6]=5000+5*10*25=6250437532500362504第三十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析37MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]當(dāng)r=3，i=4時(shí)，斷點(diǎn)k有兩個(gè)：000000157501262527503100045000578751對(duì)斷點(diǎn)k=5，計(jì)算A[4:5]A[6:6]有m[4][6]=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。43753250036250435005第三十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析38MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]類(lèi)似的，當(dāng)r=4、5、6時(shí)，可計(jì)算出相應(yīng)的m[i][j]及其相應(yīng)的斷點(diǎn)s[i][j]，如下圖中所示：000000157501262527503100045000578751437532500335005937537125353753118753105003151253第三十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析39MatrixChain的運(yùn)行舉例123456

123456m[i][j]123456s[i][j]000000157501262527503100045000578751437532500335005937537125353753118753105003151253由m[1][6]知此矩陣連乘的最小數(shù)乘量為15125。由s[1][6]=3、s[1][3]=1、s[4][6]=5可知矩陣連乘的最優(yōu)計(jì)算次序?yàn)椋?A1(A2A3))((A4A5)A6)。第三十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析40MatrixChain的時(shí)間復(fù)雜性算法MatrixChain的主要計(jì)算取決于程序中對(duì)r、i和k的三重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，1≤r、i、k≤n，三重循環(huán)的總次數(shù)為O(n3)。因此該算法時(shí)間復(fù)雜性的上界為O(n3)，比直接遞歸算法要有效得多。算法使用空間顯然為O(n2)。這種算法就稱(chēng)為動(dòng)態(tài)規(guī)劃。第四十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析41動(dòng)態(tài)規(guī)劃的基本思想其求解方法與分治法是相同的。不同之處是子問(wèn)題不是相互獨(dú)立的，而是互有重疊。為了避免重復(fù)計(jì)算，動(dòng)態(tài)規(guī)劃算法采用填表來(lái)保存子問(wèn)題解的方法。在求解過(guò)程中用表格來(lái)保存已經(jīng)求解的子問(wèn)題的解，無(wú)論它是否會(huì)被用到。當(dāng)以后遇到該子問(wèn)題時(shí)即可查表取出其解，從而避免了重復(fù)計(jì)算。第四十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析42動(dòng)態(tài)規(guī)劃的基本要素最優(yōu)子結(jié)構(gòu)：最優(yōu)解由子問(wèn)題最優(yōu)解構(gòu)成。重疊子問(wèn)題：子問(wèn)題彼此有重疊的。最優(yōu)子結(jié)構(gòu)性質(zhì)使之能以自底向上的方式遞歸地從子結(jié)構(gòu)最優(yōu)解構(gòu)造出問(wèn)題的最優(yōu)解。子問(wèn)題重疊造成重復(fù)計(jì)算。這樣就可以用填表保存子問(wèn)題解的方法來(lái)提高效率。第四十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析43動(dòng)態(tài)規(guī)劃的基本方法動(dòng)態(tài)規(guī)劃求解的步驟：⑴找出最優(yōu)解性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；⑵給出最優(yōu)解的遞歸定義；⑶自底向上地計(jì)算并保存子問(wèn)題最優(yōu)解；⑷根據(jù)步驟⑶中得到的信息構(gòu)造最優(yōu)解。步驟⑴~⑶是動(dòng)態(tài)規(guī)劃算法的基本步驟。若要構(gòu)造最優(yōu)解，則必須執(zhí)行步驟⑷，為此需在步驟⑶中增加必要信息的記錄。第四十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析44動(dòng)態(tài)規(guī)劃的算法框架DynamicProgram(形參表）{初始化；自底向上地計(jì)算子任務(wù)并將結(jié)果填入表中。}第四十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析45動(dòng)態(tài)規(guī)劃的備忘錄方法動(dòng)態(tài)規(guī)劃中的自底向上方式與遞歸定義中自上而下的描述往往不一致。用自上而下的方式求解也可避免重復(fù)。Howtodoit?同樣用表來(lái)存放子問(wèn)題的解，初始時(shí)所有子問(wèn)題都標(biāo)記為未解。在求解過(guò)程中，對(duì)待解子問(wèn)題，先查看是否已解。若已解，則取出其結(jié)果，否則計(jì)算其解并保存。這種方法稱(chēng)為動(dòng)態(tài)規(guī)劃的備忘錄方法。第四十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析46凸多邊形的三角剖分凸多邊形的三角剖分是將一個(gè)凸多邊形分割成互不相交的三角形的弦的集合T。下面是一個(gè)凸7邊形的2個(gè)不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6第四十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析47凸多邊形的三角剖分凸多邊形的三角剖分是將一個(gè)凸多邊形分割成互不相交的三角形的弦的集合T。在凸多邊形的一個(gè)三角剖分T中，各弦互不相交，且T已達(dá)到最大，即任何一條不在T中的弦必與T中某弦相交。在有n個(gè)頂點(diǎn)的凸多邊形的中三角剖分中，恰有n–3條弦和n–2個(gè)三角形。第四十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析48凸多邊形的最優(yōu)三角剖分問(wèn)題：給定凸多邊形P={v0,v1,…,vn–1}及定義在由P的邊和弦組成的三角形上的權(quán)函數(shù)w。求P的一個(gè)三角剖分T，使得T中諸三角形上權(quán)之和為最小?？啥x三角形上各種各樣的權(quán)函數(shù)w。例如：w(vivjvk)=|vivj|+|vjvk|+|vkvi|，其中|vivj|是點(diǎn)vi到vj的歐氏距離，其對(duì)應(yīng)的最優(yōu)三角剖分就是最小弦長(zhǎng)三角剖分。第四十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析49三角剖分與矩陣連乘積同構(gòu)三角剖分問(wèn)題和矩陣連乘問(wèn)題都對(duì)應(yīng)于一棵完全二叉樹(shù)，也稱(chēng)為表達(dá)式的語(yǔ)法樹(shù)。0123A1A44A2A3A5A6((A1(A2A3))(A4(A5A6))所對(duì)應(yīng)的二叉樹(shù)凸多邊形v0v1v2v3v4v5v6的三角剖分對(duì)應(yīng)的二叉樹(shù)v0v1v2v3v4v5v612A13A2A3A44A5A60第四十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析50三角剖分與矩陣連乘積同構(gòu)三角剖分問(wèn)題和矩陣連乘問(wèn)題都對(duì)應(yīng)于一棵完全二叉樹(shù)，也稱(chēng)為表達(dá)式的語(yǔ)法樹(shù)。0123A1A44A2A3A5A6v0v1v2v3v4v5v612A13A2A3A44A5A60顯然，矩陣連乘的最優(yōu)計(jì)算順序與凸多邊形最優(yōu)三角剖分有完全具相同的遞歸結(jié)構(gòu)。第五十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析51最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)三角剖分問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。若凸多邊形P={v0,v1,…,vn}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k＜n，則T的權(quán)為三角形v0vkvn，多邊形P1={v0,v1,…,vk}和多邊形P2={vk,vk+1,…,vn}的權(quán)之和。顯然P1和P2的三角剖分也是最優(yōu)的。因?yàn)?，若P1或P2的三角剖分不是最優(yōu)的，則導(dǎo)致T不是最優(yōu)三角剖分的矛盾。第五十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析52最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義m[i][j]，1≤i<j≤n，為子多邊形{vi–1,vi,…,vj}的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，并設(shè)退化多邊形{vi–1,vi}的權(quán)值為0。m[i][j]可遞歸定義為：當(dāng)i=j時(shí)，m[i][j]=0；退化多邊形{vi–1,vi}第五十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三2023/6/12計(jì)算機(jī)算法設(shè)計(jì)與分析53最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義m[i][j]，1≤i<j≤n，為子多邊形{vi–1,vi,…,vj}的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，并設(shè)退化多邊形{vi–1,vi}的權(quán)值為0。m[i][j]可遞歸定義為：當(dāng)i=j時(shí)，m[i][j]=0；m[i][j]=

min{m[i][k]+m[k+1][j]+w(vi–1vkvj)}i≤k＜j當(dāng)i＜j時(shí)，有：w(vi–1vkvj}計(jì)算以vi–1、vk和v