動(dòng)態(tài)規(guī)劃矩陣連乘算法

1、問題解析：由于矩陣乘法滿足結(jié)合律，故計(jì)算矩陣的連乘積可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。完全加括號(hào)的矩陣連乘積可遞歸地定義為：(1)單個(gè)矩陣是完全加括號(hào)的；(2)矩陣連乘積A是完全加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=(BC)例如，矩陣連乘積AAAA舄5種不同的完全加括號(hào)的方式：(Ai(A2(A3A4),(Al(A2A3)A4),(A1A2)(A3A4),(A1(A2A3)A4),(A1A2)A3)A4

2、)o每一種完全加括號(hào)的方式對(duì)應(yīng)于一個(gè)矩陣連乘積的計(jì)算次序，這決定著作乘積所需要的計(jì)算量?？聪旅嬉粋€(gè)例子，計(jì)算三個(gè)矩陣連乘A1,A2,A3;維數(shù)分別為10*100,100*5,5*50按此順序計(jì)算需要的次數(shù)(A1*A2)*A3):10X100X5+10X5X50=7500次，按此順序計(jì)算需要的次數(shù)(A1*(A2*A3):10*5*50+10*100*50=75000次所以問題是：如何確定運(yùn)算順序，可以使計(jì)算量達(dá)到最小算法思路：例：設(shè)要計(jì)算矩陣連乘乘積AAA3AA5A6,其中各矩陣的維數(shù)分別是：Ai：30*35;A2：35*15;A3:15*5;A45*10;A5：10*20;A6：20*25遞推

3、關(guān)系：設(shè)計(jì)算Ai:j,1<i<j<n,所需要的最少數(shù)乘次數(shù)mi,j,則原問題的最優(yōu)值為m1,n。當(dāng)i=j時(shí)，Ai:j=Ai,因此，mii=0,i=1,2,n當(dāng)i<j時(shí)，若Ai:j的最優(yōu)次序在A和A+1之間斷開，i<=k<j,則：mij=mik+mk+1j+pi-1PkP0由于在計(jì)算是并不知道斷開點(diǎn)k的位置，所以k還未定。不過k的位置只有j-i個(gè)可能。因此，k是這j-i個(gè)位置使計(jì)算量達(dá)到最小的那個(gè)位置。綜上，有遞推關(guān)系如下：構(gòu)造最優(yōu)解：若將對(duì)應(yīng)mij的斷開位置k記為sij,在計(jì)算出最優(yōu)值mij后，可遞歸地由sij構(gòu)造出相應(yīng)的最優(yōu)解。sij中的數(shù)表明，計(jì)算矩陣鏈

4、Ai:j的最佳方式應(yīng)在矩陣為和A+1之間斷開，即最優(yōu)的加括號(hào)方式應(yīng)為(Ai:k)(Ak+1:j)。因此，從s1n記錄的信息可知計(jì)算A1:n的最優(yōu)加括號(hào)方式為(A1:s1n)(As1n+1:n),進(jìn)一步遞推，A1:s1n的最優(yōu)加括號(hào)方式為(A1:s1s1n)(As1s1n+1:s1s1n)。同理可以確定As1n+1:n的最優(yōu)加括號(hào)方式在ss1n+1n處斷開照此遞推下去，最終可以確定A1:n的最優(yōu)完全加括號(hào)方式，及構(gòu)造出問題的一個(gè)最優(yōu)解。1、窮舉法列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：以上遞推關(guān)系說明，P(n)是隨n的增長(zhǎng)呈指數(shù)增長(zhǎng)的。因此，窮舉法不是一個(gè)多項(xiàng)式時(shí)間復(fù)雜度算法。2、重疊遞歸從以上遞推關(guān)系和構(gòu)造最優(yōu)解思路出發(fā)，即可寫出有子問題重疊性的遞歸代碼實(shí)現(xiàn)：.m4:6=min(m4:4+m5:6+p3*p4*p6,m4:5+m6:6+p3*p5*p6);依次類推，根據(jù)之前計(jì)算的m值，迭代計(jì)算最優(yōu)解。與備忘錄方法相比，此方法會(huì)將每個(gè)