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

1、問題描述：給定n個(gè)矩陣：A1,A2,.,An，其中Ai與Ai+1是可乘的，i=1，2.，n-1。確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣個(gè)數(shù)和每個(gè)矩陣規(guī)模，輸出結(jié)果為計(jì)算矩陣連乘積的計(jì)算次序和最少數(shù)乘次數(shù)。 問題解析：由于矩陣乘法滿足結(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是完全

2、加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=(BC) 例如，矩陣連乘積A1A2A3A4有5種不同的完全加括號(hào)的方式：(A1(A2(A3A4)，(A1(A2A3)A4)，(A1A2)(A3A4)，(A1(A2A3)A4)，(A1A2)A3)A4)。每一種完全加括號(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*A

3、3):10*5*50+10*100*50=75000次 所以問題是：如何確定運(yùn)算順序，可以使計(jì)算量達(dá)到最小化。 算法思路： 例：設(shè)要計(jì)算矩陣連乘乘積A1A2A3A4A5A6，其中各矩陣的維數(shù)分別是： A1：30*35; A2：35*15; A3：15*5; A4：5*10; A5：10*20; A6：20*25 遞推關(guān)系： 設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n。 當(dāng)i=j時(shí)，Ai:j=Ai，因此，mii=0，i=1,2,n 當(dāng)ij時(shí)，若Ai:j的最優(yōu)次序在Ak和Ak+1之間斷開，i=kj,則：mij=mik+mk+1j+pi-1pkpj。由于在計(jì)算

4、是并不知道斷開點(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ì)算矩陣鏈Ai:j的最佳方式應(yīng)在矩陣Ak和Ak+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)。同理可以確定As1

5、n+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í)

6、現(xiàn)：/3d1-1 重疊子問題的遞歸最優(yōu)解/A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25/p0-6=30,35,15,5,10,20,25#include stdafx.h#include using namespace std; const int L = 7;int RecurMatrixChain(int i,int j,int *s,int *p);/遞歸求最優(yōu)解void Traceback(int i,int j,int *s);/構(gòu)造最優(yōu)解int main()int pL=30,35,15,5,10,20,25; int *s

7、 = new int *L;for(int i=0;iL;i+) si = new intL; cout矩陣的最少計(jì)算次數(shù)為：RecurMatrixChain(1,6,s,p)endl;cout矩陣最優(yōu)計(jì)算次序?yàn)椋篹ndl;Traceback(1,6,s);return 0;int RecurMatrixChain(int i,int j,int *s,int *p)if(i=j) return 0;int u = RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+pi-1*pi*pj;sij = i;for(int k=i+1; kj

8、; k+)int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + pi-1*pk*pj;if(tu)u=t;sij=k;return u;void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);coutMultiply Ai,sij;cout and A(sij+1),jendl;1. 用算法RecurMatrixChain(1,4,s,p)計(jì)算a1:4的計(jì)算遞歸樹如下圖所示：2.3.4. 從上圖可

9、以看出很多子問題被重復(fù)運(yùn)算。可以證明，該算法的計(jì)算時(shí)間T(n)有指數(shù)下界。設(shè)算法中判斷語句和賦值語句為常數(shù)時(shí)間，則由算法的遞歸部分可得關(guān)于T(n)的遞歸不等式：5.6. 用數(shù)學(xué)歸納法可以證明，因此，算法RecurMatrixChain的計(jì)算時(shí)間也隨n指數(shù)增長(zhǎng)。7. 3、備忘錄遞歸算法8. 備忘錄方法用表格保存已解決的子問題答案，在下次需要解決此子問題時(shí)，只要簡(jiǎn)單查看該子問題的解答，而不必重新計(jì)算。備忘錄方法為每一個(gè)子問題建立一個(gè)記錄項(xiàng)，初始化時(shí)，該記錄項(xiàng)存入一個(gè)特殊的值，表示該子問題尚未求解。在求解的過程中，對(duì)每個(gè)帶求的子問題，首先查看其相應(yīng)的記錄項(xiàng)。若記錄項(xiàng)中存儲(chǔ)的是初始化時(shí)存入的特殊值，則

10、表示該問題是第一次遇到，此時(shí)計(jì)算出該子問題的解，并將其保存在相應(yīng)的記錄項(xiàng)中，以備以后查看。若記錄項(xiàng)中存儲(chǔ)的已不是初始化時(shí)存入的特殊值，則表示該子問題已被計(jì)算過，相應(yīng)的記錄項(xiàng)中存儲(chǔ)的是該子問題的解答。此時(shí)從記錄項(xiàng)中取出該子問題的解答即可，而不必重新計(jì)算。/3d1-2 矩陣連乘 備忘錄遞歸實(shí)現(xiàn)/A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25/p0-6=30,35,15,5,10,20,25#include stdafx.h#include using namespace std; const int L = 7;int LookupChain

11、(int i,int j,int *m,int *s,int *p);int MemoizedMatrixChain(int n,int *m,int *s,int *p);void Traceback(int i,int j,int *s);/構(gòu)造最優(yōu)解int main()int pL=30,35,15,5,10,20,25; int *s = new int *L;int *m = new int *L;for(int i=0;iL;i+) si = new intL;mi = new intL; cout矩陣的最少計(jì)算次數(shù)為：MemoizedMatrixChain(6,m,s,p)end

12、l;cout矩陣最優(yōu)計(jì)算次序?yàn)椋篹ndl;Traceback(1,6,s);return 0;int MemoizedMatrixChain(int n,int *m,int *s,int *p)for(int i=1; i=n; i+)for(int j=1; j0)return mij;if(i=j)return 0;int u = LookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+pi-1*pi*pj;sij=i;for(int k=i+1; kj; k+)int t = LookupChain(i,k,m,s,p) + LookupCh

13、ain(k+1,j,m,s,p) + pi-1*pk*pj;if(tu)u=t;sij = k;mij = u;return u;void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);coutMultiply Ai,sij;cout and A(sij+1),j0，則表示其中存儲(chǔ)的是所要求子問題的計(jì)算結(jié)果，直接返回即可。否則與直接遞歸算法一樣遞歸計(jì)算，并將計(jì)算結(jié)果存入mij中返回。備忘錄算法耗時(shí)O(n3)，將直接遞歸算法的計(jì)算時(shí)間從2n降至O(n3)。3、動(dòng)態(tài)規(guī)劃迭代實(shí)現(xiàn)

14、 用動(dòng)態(tài)規(guī)劃迭代方式解決此問題，可依據(jù)其遞歸式自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題的答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只需簡(jiǎn)單檢查一下，從而避免了大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。/3d1-2 矩陣連乘 動(dòng)態(tài)規(guī)劃迭代實(shí)現(xiàn)/A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25/p0-6=30,35,15,5,10,20,25#include stdafx.h#include using namespace std; const int L = 7;int MatrixChain(int n,int *m,int

15、 *s,int *p); void Traceback(int i,int j,int *s);/構(gòu)造最優(yōu)解int main()int pL=30,35,15,5,10,20,25; int *s = new int *L;int *m = new int *L;for(int i=0;iL;i+) si = new intL;mi = new intL; cout矩陣的最少計(jì)算次數(shù)為：MatrixChain(6,m,s,p)endl;cout矩陣最優(yōu)計(jì)算次序?yàn)椋篹ndl;Traceback(1,6,s);return 0;int MatrixChain(int n,int *m,int *s

16、,int *p)for(int i=1; i=n; i+)mii = 0;for(int r=2; r=n; r+) /r為當(dāng)前計(jì)算的鏈長(zhǎng)（子問題規(guī)模） for(int i=1; i=n-r+1; i+)/n-r+1為最后一個(gè)r鏈的前邊界 int j = i+r-1;/計(jì)算前邊界為r，鏈長(zhǎng)為r的鏈的后邊界 mij = mi+1j + pi-1*pi*pj;/將鏈ij劃分為A(i) * ( Ai+1:j ) sij = i;for(int k=i+1; kj; k+)/將鏈ij劃分為( Ai:k )* (Ak+1:j) int t = mik + mk+1j + pi-1*pk*pj;if(tm

17、ij)mij = t;sij = k;return m1L-1;void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);coutMultiply Ai,sij;cout and A(sij+1),jendl;上述迭代算法的運(yùn)行過程如下圖所示： 如圖所示： 當(dāng)R=2時(shí)，先迭代計(jì)算出： m1:2=m1:1+m2:2+p0*p1*p2； m2:3=m2:2+m3:3+p1*p2*p3; m3:4=m3:3+m44+p2*p3*p4; m4:5=m4:4+m55+p3*p4*p5; m5:6=m55+m66+p4*p5*p6的值； 當(dāng)R=3時(shí)，迭代計(jì)算出： m1