算法設(shè)計(jì)與分析 課件 5.5.2-動態(tài)規(guī)劃應(yīng)用-矩陣連乘-動態(tài)規(guī)劃求解

信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—矩陣連乘之動態(tài)規(guī)劃求解國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版動態(tài)規(guī)劃解題步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。定義：m[i,j]表示AiAi+1…Aj矩陣連乘問題的最少乘法次數(shù)。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征

m[i,j]表示Ai…Aj矩陣連乘問題的最少乘法次數(shù)。2.遞歸地定義最優(yōu)值

3.以自底向上的方式計(jì)算最優(yōu)值1234…n1234…nm[i,j]表示Ai…Aj矩陣連乘問題的最少乘法次數(shù)。1個(gè)矩陣2個(gè)矩陣3個(gè)矩陣4個(gè)矩陣…n個(gè)矩陣123456123456m[i,j]A1A2252020

15A3A415

55

10A5A610

2020

30p0p1p2p3p4p5P625201551020301.初始化m[i,i]=0，i=1~62.計(jì)算相鄰2個(gè)矩陣m[1,2]=7500m[2,3]=1500m[3,4]=750m[4,5]=1000m[5,6]=6000p數(shù)組存放矩陣的行、列n=6個(gè)矩陣相乘07500000001500750100060001234561075002015003075040100050600060m[i,j]p0p1p2p3p4p5P62520155102030單選題。算一算，m[1,3]等于（）A.1500B.4000C.7500p數(shù)組存放矩陣的行、列12345610750040005250201500250045003075025006250401000400050600060m[i,j]p0p1p2p3p4p5P625201551020303.計(jì)算相鄰3個(gè)矩陣m[1,3],m[2,4],m[3,5],m[4,6]4.計(jì)算相鄰4個(gè)矩陣m[1,4],m[2,5],m[3,6]p數(shù)組存放矩陣的行、列p0p1p2p3p4p5P625201551020305.計(jì)算相鄰5個(gè)矩陣m[1,5]=7500m[2,6]=85006.計(jì)算相鄰6個(gè)矩陣m[1,6]=11750p數(shù)組存放矩陣的行、列123456107500400052507500117502015002500450085003075025006250401000400050600060m[i,j]for(intr=2;r<=n;r++)/*r表示長度*/

for(inti=1;i<=n-r+1;i++)/*i表示起點(diǎn)*/{intj=i+r-1;/*j表示終點(diǎn)*/for(intk=i;k<j;k++)/*k表示斷開位置*/

m[i][j]=min(m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];}123456123456求解矩陣連乘問題的代碼框架1.voidMatrixChain(int*p，intn，int**m，int**s)2.{3.for(inti=1;i<=n;i++)m[i][i]=0;4.for(intr=2;r<=n;r++){/*r是矩陣的數(shù)量*/5.for(inti=1;i<=n-r+1;i++)/*i是起始矩陣的編號*/6.{intj=i+r-1;/*j是終止矩陣的編號*/7.m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];8.s[i][j]=i;9.for(intk=i+1;k<j;k++){/*k是斷開的位置*/10.intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];11.if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}12.}13.}14.}空間復(fù)雜度：O(n2)時(shí)間復(fù)雜度：O(n3)123456123456123456123456單選題。矩陣連乘問題求解最優(yōu)值采用如圖(a)所示的計(jì)算次序，圖(b)給出了另一種計(jì)算次序，正確嗎？A.不正確B.正確(a)(b)123456101133320233330333404550560s[i,j]s[1,6]=3，得到(A1A2A3)(A4A5A6)s[1,3]=1，得到(A1(A2A3))s[4,6]=5，得到((A4A5)A6)最優(yōu)解為：((A1(A2A3))((A4A5)A6))4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解voidtraceback(int**s,inti,intj){if(i==j){printf(“A%d“,i);return;}intk=s[i][j];printf(“(“);traceback(s,i,k);traceback(s,k+1,j);printf(“)“);}4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解分析括號((A1(A2A3))

((A4A5)A6))每個(gè)問題（矩陣長度超過1）的解方案外有一對括號思考：是否可以進(jìn)行空間優(yōu)化？采用下標(biāo)轉(zhuǎn)換法，用一維數(shù)組代替二維數(shù)組，可以節(jié)省(N2-N)/2的空間。123456107500400052507500117502015002500450085003075025006250401000400050600060m[i,j]石子合并問題：

有n堆石子排成一排，依次編號為1~n?，F(xiàn)要將石子有次序地合并為一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為本次合并的得分。

試設(shè)計(jì)一算法，計(jì)算將n堆石子合并成一堆的最大得分。以n=4為例，每堆石子的個(gè)數(shù)為：3465，共5種合并方案。346510151810+15+18=43346511151811+15+18=4434657187+11+18=3611分析：每次只能選相鄰2堆石子合并，最后一次合并是左邊若干堆石子與右邊若干堆石子進(jìn)行合并，與矩陣連乘問題類似。sum(i,j)表