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

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

若A是一個p*q矩陣，B是一個q*r矩陣，則其乘積C=AB是一個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ù)乘。第六頁，編輯于星期六：十三點三十七分。三個矩陣相乘

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

Dp?s=Ap?qBq?r

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

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

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

10?100B100?5

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

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

A34?6

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

5?10A210?4

A34?6

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

(A1A2)A3:

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

5?10A210?4

A34?6

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

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

A2(A3A4):計算量：640第十七頁，編輯于星期六：十三點三十七分。A1

5?10A210?4

A34?6

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

計算量：620第十八頁，編輯于星期六：十三點三十七分。用數(shù)組元素C[i][j]來存儲

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

5?10A210?4

A34?6

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

5?10A210?4

A34?6

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

5?10A210?4

A34?6

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

5?10A210?4

A34?6

A46?103計算規(guī)模為4的原問題A[1:4]所需乘法次數(shù)，有三種結合方法，選最好的一種：(A[1:3])A4:計算A[1:3]的最小計算量+計算（A[1:3]）乘A4的計算量：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第二十二頁，編輯于星期六：十三點三十七分。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第二十三頁，編輯于星期六：十三點三十七分。將例7.1中的中間結果存入數(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第二十四頁，編輯于星期六：十三點三十七分。特征：計算A[i:j]的最優(yōu)次序所包含的計算矩陣子鏈A[i:k-1]和A[k:j]的次序也是最優(yōu)的。舉例矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質稱為最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。分析最優(yōu)解的結構第二十五頁，編輯于星期六：十三點三十七分。建立遞歸關系設計算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)c[i,j]，則原問題的最優(yōu)值為c[1,n]當i=j時，A[i:j]=Ai，因此，c[i,i]=0，i=1,2,…,n當i<j時，需找到一個分割點k,在Ak前斷開：(Ai…Ak-1)(Ak…Aj),使C[i,j]達到最小這里的維數(shù)為第二十六頁，編輯于星期六：十三點三十七分。

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

用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法第二十九頁，編輯于星期六：十三點三十七分。課堂練習(1)請給出計算M1M2M3M4M5乘積所需的最少數(shù)乘次數(shù)（即C[1][5]）。（2）請給出一個括號化表達式，使在這種次序下達到乘法的次數(shù)最少。M1M2M3M4M54?55?33?66?44?5p1=4,p1=5,p3=3,p4=6,p5=4,p6=5第三十頁，編輯于星期六：十三點三十七分。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第三十一頁，編輯于星期六：十三點三十七分。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第三十二頁，編輯于星期六：十三點三十七分。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第三十三頁，編輯于星期六：十三點三十七分。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)計算次序：(M1M2)((M3M4)M5)第三十四頁，編輯于星期六：十三點三十七分。用動態(tài)規(guī)劃法求最優(yōu)解voidMatrixChain(int*p，intn，int**c，int**s){for(inti=1;i<=n;i++)c[i][i]=0;//填充對角線d=0for(intd=1;d<=n-1;d++)//填充對角線d，,d=1,…n-1for(inti=1;i<=n–d;i++){填充對角線d上第i個元素intj=i+d;//以下幾行計算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]達到最小的k;｝}}m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//從i+1位置斷開s[i][j]=i+1;for(intk=i+2;k<=j;k++){//從k(k=i+2,…j)斷開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;}}}第三十五頁，編輯于星期六：十三點三十七分。討論有關數(shù)組的使用：1、一維數(shù)組的聲明和指針的使用2、一維數(shù)組和指針作參數(shù)3、二維數(shù)組的聲明和雙重指針的使用第三十六頁，編輯于星期六：十三點三十七分。程序1：程序沒有任何通用性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);}第三十七頁，編輯于星期六：十三點三十七分。程序2（先開辟一個較大的存儲空間）#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);}第三十八頁，編輯于星期六：十三點三十七分。程序3：用函數(shù)測出字符串的長度#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);}第三十九頁，編輯于星期六：十三點三十七分。程序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);}第四十頁，編輯于星期六：十三點三十七分。程序5:動態(tài)分配存儲空間(推薦）#defineN100voidLCSlength(intm,intn,charx[],chary[],int*c){……}main(){charA[N],B[N];int*c;gets(A);get