動(dòng)態(tài)的規(guī)劃-矩陣鏈相乘

動(dòng)態(tài)的規(guī)劃-矩陣鏈相乘第一頁(yè)，編輯于星期六：十三點(diǎn)三十七分。例如：項(xiàng)鏈有四個(gè)能量珠，能量數(shù)組p如下：p1=4,p2=5,p3=2,p4=8則這四顆能量珠頭尾部能量分別為（4，5）、（5，2）、（2，8）、（8，4）第二頁(yè)，編輯于星期六：十三點(diǎn)三十七分。（（U1⊙U2）⊙U3）⊙U4釋放能量為4*5*2+4*2*8+4*8*4=232（U1⊙U2）⊙（U3⊙U4）釋放能量為4*5*2+2*8*4+4*2*4=136（U1⊙（U2⊙U3））⊙U4釋放能量為5*2*8+4*5*8+4*8*4=368U1⊙（（U2⊙U3）⊙U4）釋放能量為5*2*8+5*8*4+4*5*4=320U1⊙（U2⊙（U3⊙U4））釋放能量為2*8*4+5*2*4+4*5*4=184p1=4,p2=5,p3=2,p4=8第三頁(yè)，編輯于星期六：十三點(diǎn)三十七分。得到項(xiàng)鏈的最大能量了嗎？還沒(méi)有，因?yàn)檫@僅僅是項(xiàng)鏈在從U4和U1之間斷開(kāi)的情況，項(xiàng)鏈還有其它三個(gè)可能的斷開(kāi)位置：從U1和U2之間斷開(kāi)；從U2和U3之間斷開(kāi)；從U3和U4之間斷開(kāi)。另外，當(dāng)n達(dá)到10時(shí)，就有上百萬(wàn)種組合方法，如何計(jì)算？第四頁(yè)，編輯于星期六：十三點(diǎn)三十七分。7.4矩陣鏈相乘問(wèn)題：給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少第五頁(yè)，編輯于星期六：十三點(diǎn)三十七分。兩個(gè)矩陣相乘

若A是一個(gè)p*q矩陣，B是一個(gè)q*r矩陣，則其乘積C=AB是一個(gè)p*r矩陣。

for(i=1;i<=p;i++)for(j=1;j<=r;j++){c[i][j]=0;for(k=1;k<=q;k++)c[i][j]+=a[i][k]*b[k][j];}總共需要pqr次數(shù)乘。第六頁(yè)，編輯于星期六：十三點(diǎn)三十七分。三個(gè)矩陣相乘

現(xiàn)有三個(gè)矩陣相乘：

Dp?s=Ap?qBq?r

Cr?s我們知道矩陣相乘滿足結(jié)合率，即(AB)C=A(BC)不同結(jié)合方法得到的結(jié)果是一樣的，然而計(jì)算量卻可能有很大差別。第七頁(yè)，編輯于星期六：十三點(diǎn)三十七分。是否讓你吃驚？如：A50?5B5?100C100?10按(AB)C計(jì)算，所需乘法次數(shù)為：50?5?100+50?100?10=75000按A(BC）計(jì)算，所需乘法次數(shù)為：5?100?10+50?5?10=7500可見(jiàn)如何結(jié)合十分影響計(jì)算的效率，自然提出了矩陣鏈相乘的最優(yōu)計(jì)算次序問(wèn)題第八頁(yè)，編輯于星期六：十三點(diǎn)三十七分。完全加括號(hào)的矩陣連乘積可遞歸地定義為：（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積是完全加括號(hào)的，則可表示為2個(gè)完全加括號(hào)的矩陣連乘積和的乘積并加括號(hào)，即16000,10500,36000,87500,34500完全加括號(hào)的矩陣連乘積設(shè)有四個(gè)矩陣，它們的維數(shù)分別是：則有五種完全加括號(hào)方式：第九頁(yè)，編輯于星期六：十三點(diǎn)三十七分。矩陣連乘問(wèn)題給定n個(gè)矩陣，其中與是可乘的，?？疾爝@n個(gè)矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積第十頁(yè)，編輯于星期六：十三點(diǎn)三十七分。矩陣連乘問(wèn)題問(wèn)題：給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少第十一頁(yè)，編輯于星期六：十三點(diǎn)三十七分。矩陣連乘問(wèn)題窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。

算法復(fù)雜度分析：對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：第十二頁(yè)，編輯于星期六：十三點(diǎn)三十七分。矩陣連乘問(wèn)題窮舉法動(dòng)態(tài)規(guī)劃將矩陣連乘積簡(jiǎn)記為A[i:j]，這里i≤j

考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak-1和Ak之間將矩陣鏈斷開(kāi)，i<k≤j，則其相應(yīng)完全加括號(hào)方式為計(jì)算量：的計(jì)算量加上的計(jì)算量，再加上A[i:k-1]和A[k:j]相乘的計(jì)算量第十三頁(yè)，編輯于星期六：十三點(diǎn)三十七分。關(guān)于計(jì)算量如：A

10?100B100?5

C5?50D50?100按(AB)(CD)計(jì)算，所需乘法次數(shù)為：1、計(jì)算AB所需乘法次數(shù)：10?100?5=50002、計(jì)算CD所需乘法次數(shù)：5?50?100=250003、以上兩個(gè)結(jié)果矩陣(AB)10?5和(CD)5?100再相乘的乘法次數(shù):

10?5?100=5000故按(AB)(CD)計(jì)算，所需乘法次數(shù)為：5000+25000+5000=35000第十四頁(yè)，編輯于星期六：十三點(diǎn)三十七分。規(guī)模為4的情況如：A15?10A210?4

A34?6

A46?10請(qǐng)給出計(jì)算A1A2A3A4的最優(yōu)計(jì)算次序1、計(jì)算規(guī)模為2的子問(wèn)題計(jì)算A1A2所需乘法次數(shù)：5?10?4=200計(jì)算A2A3所需乘法次數(shù)：10?4?6=240計(jì)算A3A4所需乘法次數(shù)：4?6?10=240第十五頁(yè)，編輯于星期六：十三點(diǎn)三十七分。A1

5?10A210?4

A34?6

A46?102、計(jì)算規(guī)模為3的子問(wèn)題(1)計(jì)算A1A2A3所需乘法次數(shù)，有兩種結(jié)合方法:(A1A2)A3和A1(A2A3),選最好的一種：

(A1A2)A3:

計(jì)算量：320(A1A2)A3:計(jì)算A1A2的計(jì)算量+計(jì)算A[1:2]乘A3的計(jì)算量：200+5?4?6=320A1(A2A3):計(jì)算BC的計(jì)算量+計(jì)算A1乘A[2:3]的計(jì)算量：240+5?10?6=540第十六頁(yè)，編輯于星期六：十三點(diǎn)三十七分。A1

5?10A210?4

A34?6

A46?10(2)計(jì)算A2A3A4所需乘法次數(shù)，有兩種結(jié)合方法:(A2A3)A4和A2(A3A4)，選最好的一種：

計(jì)算A2A3的計(jì)算量+計(jì)算A[2:3]乘A4的計(jì)算量：240+10?6?10=840A2(A3A4):計(jì)算A3A4的計(jì)算量+計(jì)算A2乘A[3:4]的計(jì)算量：240+10?4?10=640

A2(A3A4):計(jì)算量：640第十七頁(yè)，編輯于星期六：十三點(diǎn)三十七分。A1

5?10A210?4

A34?6

A46?103計(jì)算規(guī)模為4的原問(wèn)題A1A2A3A4所需乘法次數(shù)，有三種結(jié)合方法:(A1A2A3)A4、(A1A2)(A3A4)、A1(A2A3A4)，選最好的一種：(A1A2A3)A4:計(jì)算A1A2A3的最小計(jì)算量+計(jì)算（A1A2A3）乘A4的計(jì)算量：320+5?6?10=620(A1A2)(A3A4):200+240+5?4?10=640A1(A2A3A4):640+5?10?10=1140(A1A2A3)A4:

計(jì)算量：620第十八頁(yè)，編輯于星期六：十三點(diǎn)三十七分。用數(shù)組元素C[i][j]來(lái)存儲(chǔ)

計(jì)算A[i:j]的最少數(shù)乘次數(shù)例7.1：A1

5?10A210?4

A34?6

A46?10請(qǐng)給出計(jì)算A[1：4]的最優(yōu)計(jì)算次序1、計(jì)算規(guī)模為2的子問(wèn)題計(jì)算A[1：2]所需乘法次數(shù)：5?10?4=200計(jì)算A[2：3]所需乘法次數(shù)：10?4?6=240計(jì)算A[3：4]所需乘法次數(shù)：4?6?10=240將計(jì)算A[i:j]所需最小數(shù)乘次數(shù)存入數(shù)組c[i][j]中C[1][2]=200C[2][3]=240C[3][4]=240第十九頁(yè)，編輯于星期六：十三點(diǎn)三十七分。A1

5?10A210?4

A34?6

A46?102、計(jì)算規(guī)模為3的子問(wèn)題計(jì)算A[1:3]所需乘法次數(shù)，有兩種結(jié)合方法，選最好的一種：(A[1:2])A3:計(jì)算A[1:2]的計(jì)算量+計(jì)算（A[1:2]）乘A3的計(jì)算量：200+5?4?6=320A1(A[2:3]):計(jì)算A[2:3]的計(jì)算量+計(jì)算A1乘(A[2:3])的計(jì)算量：240+5?10?6=540C[1][3]=320第二十頁(yè)，編輯于星期六：十三點(diǎn)三十七分。A1

5?10A210?4

A34?6

A46?10計(jì)算A[2:4]所需乘法次數(shù)，有兩種結(jié)合方法，選最好的一種：840(A[2:3])A4:計(jì)算A[2:3]的計(jì)算量+計(jì)算A[2:3]乘A4的計(jì)算量：240+10?6?10=840A2(A[3:4]):計(jì)算A[3:4]的計(jì)算量+計(jì)算A2乘(A[3:4])的計(jì)算量：240+10?4?10=640C[2][4]=640第二十一頁(yè)，編輯于星期六：十三點(diǎn)三十七分。A1

5?10A210?4

A34?6

A46?103計(jì)算規(guī)模為4的原問(wèn)題A[1:4]所需乘法次數(shù)，有三種結(jié)合方法，選最好的一種：(A[1:3])A4:計(jì)算A[1:3]的最小計(jì)算量+計(jì)算（A[1:3]）乘A4的計(jì)算量：320+5?6?10=620(A[1:2])(A[3:4]):200+240+5?4?10=640A1(A[2:4]):640

+5?10?10=1140C[1][4]=620第二十二頁(yè)，編輯于星期六：十三點(diǎn)三十七分。A15?10A210?4

A34?6

A46?10

d=0d=1d=2d=3C[1:1]=0C[1:2]=200C[1:3]=320C[2:2]=0C[2:3]=240C[2:4]=640C[3:3]=0C[3:4]=240C[4:4]=0第二十三頁(yè)，編輯于星期六：十三點(diǎn)三十七分。將例7.1中的中間結(jié)果存入數(shù)組C[1:1]=0C[1:2]=200C[1:3]=320C[1:4]=620C[2:2]=0C[2:3]=240C[2:4]=640C[3:3]=0C[3:4]=240C[4:4]=0d=0d=1d=2d=3第二十四頁(yè)，編輯于星期六：十三點(diǎn)三十七分。特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k-1]和A[k:j]的次序也是最優(yōu)的。舉例矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。分析最優(yōu)解的結(jié)構(gòu)第二十五頁(yè)，編輯于星期六：十三點(diǎn)三十七分。建立遞歸關(guān)系設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)c[i,j]，則原問(wèn)題的最優(yōu)值為c[1,n]當(dāng)i=j時(shí)，A[i:j]=Ai，因此，c[i,i]=0，i=1,2,…,n當(dāng)i<j時(shí)，需找到一個(gè)分割點(diǎn)k,在Ak前斷開(kāi)：(Ai…Ak-1)(Ak…Aj),使C[i,j]達(dá)到最小這里的維數(shù)為第二十六頁(yè)，編輯于星期六：十三點(diǎn)三十七分。

的位置只有種可能可以遞歸地定義C[i,j]為：第二十七頁(yè)，編輯于星期六：十三點(diǎn)三十七分。計(jì)算最優(yōu)值對(duì)于1≤i≤j≤n不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多次。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。第二十八頁(yè)，編輯于星期六：十三點(diǎn)三十七分。動(dòng)態(tài)規(guī)劃--自底向上進(jìn)行計(jì)算

用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法第二十九頁(yè)，編輯于星期六：十三點(diǎn)三十七分。課堂練習(xí)(1)請(qǐng)給出計(jì)算M1M2M3M4M5乘積所需的最少數(shù)乘次數(shù)（即C[1][5]）。（2）請(qǐng)給出一個(gè)括號(hào)化表達(dá)式，使在這種次序下達(dá)到乘法的次數(shù)最少。M1M2M3M4M54?55?33?66?44?5p1=4,p1=5,p3=3,p4=6,p5=4,p6=5第三十頁(yè)，編輯于星期六：十三點(diǎn)三十七分。C[1:1]=060132K=3180K=3C[2:2]=090132K=3C[3:3]=07272+3*4*5K=5C[4:4]=0120C[5:5]=0p1=4,p2=5,p3=3,p4=6,p5=4,p6=5第三十一頁(yè)，編輯于星期六：十三點(diǎn)三十七分。C[1:1]=0C[1:2]=60C[2:2]=0C[2:3]=90C[3:3]=0C[3:4]=72C[4:4]=0C[4:5]=120C[5:5]=0p1=4,p1=5,p3=3,p4=6,p5=4,p6=5第三十二頁(yè)，編輯于星期六：十三點(diǎn)三十七分。C[1:1]=0C[1:2]=60C[1:3]=132k=3C[1:4]=180k=3C[2:2]=0C[2:3]=90C[2:4]=132k=3C[2:5]=207k=3C[3:3]=0C[3:4]=72C[3:5]=132k=5C[4:4]=0C[4:5]=120C[5:5]=0p1=4,p1=5,p3=3,p4=6,p5=4,p6=5C[1:5]=252k=3第三十三頁(yè)，編輯于星期六：十三點(diǎn)三十七分。C[1:1]=0C[1:2]=60C[1:3]=132k=3C[1:4]=180k=3C[1:5]=252k=3C[2:2]=0C[2:3]=90C[2:4]=132k=3C[2:5]=207k=3C[3:3]=0C[3:4]=72C[3:5]=132k=5C[4:4]=0C[4:5]=120C[5:5]=0最優(yōu)計(jì)算次序：(M1M2)((M3M4)M5)第三十四頁(yè)，編輯于星期六：十三點(diǎn)三十七分。用動(dòng)態(tài)規(guī)劃法求最優(yōu)解voidMatrixChain(int*p，intn，int**c，int**s){for(inti=1;i<=n;i++)c[i][i]=0;//填充對(duì)角線d=0for(intd=1;d<=n-1;d++)//填充對(duì)角線d，,d=1,…n-1for(inti=1;i<=n–d;i++){填充對(duì)角線d上第i個(gè)元素intj=i+d;//以下幾行計(jì)算C[I][j]

c[i][j]=Max;for(k=i+1,k<=j;k++){c[i][j]=min{c[i][j],c[i][k-1]+c[k][j]+r[i]r[k]r[j]);s[i][j]=使c[I][j]達(dá)到最小的k;｝}}m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//從i+1位置斷開(kāi)s[i][j]=i+1;for(intk=i+2;k<=j;k++){//從k(k=i+2,…j)斷開(kāi)intt=m[i][k-1]+m[k][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}第三十五頁(yè)，編輯于星期六：十三點(diǎn)三十七分。討論有關(guān)數(shù)組的使用：1、一維數(shù)組的聲明和指針的使用2、一維數(shù)組和指針作參數(shù)3、二維數(shù)組的聲明和雙重指針的使用第三十六頁(yè)，編輯于星期六：十三點(diǎn)三十七分。程序1：程序沒(méi)有任何通用性voidLCSlength(intm,intn,charx[],chary[],intc[][7]){……}main(){charA[8]={'0','A','B','C','B','D','A','B'};charB[7]={'0','A','B','A','B','D',‘C'};intc[8][7];LCSlength(7,6,A,B,c);}第三十七頁(yè)，編輯于星期六：十三點(diǎn)三十七分。程序2（先開(kāi)辟一個(gè)較大的存儲(chǔ)空間）#defineN100voidLCSlength(intm,intn,charx[],chary[],intc[][N]){……}main(){charA[N]={'0','A','B','C','B','D','A','B'};charB[N]={'0','A','B','A','B','D',‘C'};

intm=7,n=6,c[N][N];LCSlength(m,n,A,B,c);}第三十八頁(yè)，編輯于星期六：十三點(diǎn)三十七分。程序3：用函數(shù)測(cè)出字符串的長(zhǎng)度#defineN100#include”stdio.h”voidLCSlength(intm,intn,charx[],chary[],intc[][N]){……}main(){charA[N]=“0ABCBDAB”;charB[N]=“0ABABDC”;intc[N][N];

intm=strlen(A),n=strlen(B);LCSlength(m,n,A,B,c);}第三十九頁(yè)，編輯于星期六：十三點(diǎn)三十七分。程序4：字符串由用戶輸入#defineN100voidLCSlength(intm,intn,charx[],chary[],intc[][N]){……}main(){charA[N],B[N];intc[N][N];

gets(A);gets(B);//cin>>A;cin>>B;intm=strlen(A),n=strlen(B);LCSlength(m,n,A,B,c);}第四十頁(yè)，編輯于星期六：十三點(diǎn)三十七分。程序5:動(dòng)態(tài)分配存儲(chǔ)空間(推薦）#defineN100voidLCSlength(intm,intn,charx[],chary[],int*c){……}main(){charA[N],B[N];int*c;gets(A);get