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

1、問題描述：給定n個矩陣：A1,A2,.,An，其中Ai與Ai+1是可乘的，i=1，2.，n-1。確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣個數(shù)和每個矩陣規(guī)模，輸出結(jié)果為計算矩陣連乘積的計算次序和最少數(shù)乘次數(shù)。      問題解析：由于矩陣乘法滿足結(jié)合律，故計算矩陣的連乘積可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標準算法計算出矩陣連乘積。       完全

2、加括號的矩陣連乘積可遞歸地定義為：     （1）單個矩陣是完全加括號的；     （2）矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)       例如，矩陣連乘積A1A2A3A4有5種不同的完全加括號的方式：(A1(A2(A3A4)，(A1(A2A3)A4)，(A1A2)(A3A4)，(A1(A2A3)A4)，(A1A2)A3)A4)。每一種完全加括號的方式對應(yīng)于一個矩陣連乘積的計算次序，這決定著作乘積所需要的計算量。  &#

3、160;   看下面一個例子，計算三個矩陣連乘A1，A2，A3；維數(shù)分別為10*100 , 100*5 , 5*50 按此順序計算需要的次數(shù)(A1*A2)*A3):10X100X5+10X5X50=7500次，按此順序計算需要的次數(shù)(A1*(A2*A3):10*5*50+10*100*50=75000次      所以問題是：如何確定運算順序，可以使計算量達到最小化。            算法思路：      例：設(shè)要計算矩陣連乘乘積A1A2A3A4A5

4、A6，其中各矩陣的維數(shù)分別是：      A1：30*35;     A2：35*15;     A3：15*5;     A4：5*10;     A5：10*20;     A6：20*25       遞推關(guān)系：      設(shè)計算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n。      當i=j時，Ai:j=Ai，因此，

5、mii=0，i=1,2,n      當i<j時，若Ai:j的最優(yōu)次序在Ak和Ak+1之間斷開，i<=k<j,則：mij=mik+mk+1j+pi-1pkpj。由于在計算是并不知道斷開點k的位置，所以k還未定。不過k的位置只有j-i個可能。因此，k是這j-i個位置使計算量達到最小的那個位置。      綜上，有遞推關(guān)系如下：                構(gòu)造最優(yōu)解：     

6、若將對應(yīng)mij的斷開位置k記為sij，在計算出最優(yōu)值mij后，可遞歸地由sij構(gòu)造出相應(yīng)的最優(yōu)解。sij中的數(shù)表明，計算矩陣鏈Ai:j的最佳方式應(yīng)在矩陣Ak和Ak+1之間斷開，即最優(yōu)的加括號方式應(yīng)為(Ai:k)(Ak+1:j)。因此，從s1n記錄的信息可知計算A1:n的最優(yōu)加括號方式為(A1:s1n)(As1n+1:n)，進一步遞推，A1:s1n的最優(yōu)加括號方式為(A1:s1s1n)(As1s1n+1:s1s1n)。同理可以確定As1n+1:n的最優(yōu)加括號方式在ss1n+1n處斷開.照此遞推下去，最終可以確定A1:n的最優(yōu)完全加括號方式，及構(gòu)造出問題的一個最優(yōu)解。    &

7、#160; 1、窮舉法      列舉出所有可能的計算次序，并計算出每一種計算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。      對于n個矩陣的連乘積，設(shè)其不同的計算次序為P(n)。每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：            以上遞推關(guān)系說明，P(n)是隨n的增長呈指數(shù)增長的。因此，窮舉法不是一個多項式時間復(fù)雜度算法。  &

8、#160;   2、重疊遞歸      從以上遞推關(guān)系和構(gòu)造最優(yōu)解思路出發(fā)，即可寫出有子問題重疊性的遞歸代碼實現(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 <iostream> using namespace std; const int L = 7;int RecurMatrixChain(int i,int j,int

9、 *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 = new int *L;for(int i=0;i<L;i+) si = new intL; cout<<"矩陣的最少計算次數(shù)為："<<RecurMatrixChain(1,6,s,p)<<endl;cout<<"矩陣最優(yōu)計算次序為："<<endl;Traceback(1,6,s)

10、;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; k<j; k+)int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + pi-1*pk*pj;if(t<u)u=t;sij=k;return u;void Tracebac

11、k(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"Multiply A"<<i<<","<<sij;cout<<" and A"<<(sij+1)<<","<<j<<endl;1. 用算法RecurMatrixChain(1,4,s,p)計算a1:4的計算遞歸樹如下圖所示： 2.3.4.

12、60;     從上圖可以看出很多子問題被重復(fù)運算。可以證明，該算法的計算時間T(n)有指數(shù)下界。設(shè)算法中判斷語句和賦值語句為常數(shù)時間，則由算法的遞歸部分可得關(guān)于T(n)的遞歸不等式：5.6.      用數(shù)學(xué)歸納法可以證明，因此，算法RecurMatrixChain的計算時間也隨n指數(shù)增長。7.      3、備忘錄遞歸算法8.      備忘錄方法用表格保存已解決的子問題答案，在下次需要解決此子問題時，只要簡單查看該子問題的解答，而不必重新計算。備忘錄方法為每一個子問題建立一個記錄

13、項，初始化時，該記錄項存入一個特殊的值，表示該子問題尚未求解。在求解的過程中，對每個帶求的子問題，首先查看其相應(yīng)的記錄項。若記錄項中存儲的是初始化時存入的特殊值，則表示該問題是第一次遇到，此時計算出該子問題的解，并將其保存在相應(yīng)的記錄項中，以備以后查看。若記錄項中存儲的已不是初始化時存入的特殊值，則表示該子問題已被計算過，相應(yīng)的記錄項中存儲的是該子問題的解答。此時從記錄項中取出該子問題的解答即可，而不必重新計算。/3d1-2 矩陣連乘 備忘錄遞歸實現(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,2

14、0,25#include "stdafx.h"#include <iostream> using namespace std; const int L = 7;int LookupChain(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

15、 *m = new int *L;for(int i=0;i<L;i+) si = new intL;mi = new intL; cout<<"矩陣的最少計算次數(shù)為："<<MemoizedMatrixChain(6,m,s,p)<<endl;cout<<"矩陣最優(yōu)計算次序為："<<endl;Traceback(1,6,s);return 0;int MemoizedMatrixChain(int n,int *m,int *s,int *p)for(int i=1; i<=n; i

16、+)for(int j=1; j<=n; j+)mij=0;return LookupChain(1,n,m,s,p);int LookupChain(int i,int j,int *m,int *s,int *p)if(mij>0)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; k<j; k+)int t = LookupChain(i,k,m,s,p) + LookupChain(k+1

17、,j,m,s,p) + pi-1*pk*pj;if(t<u)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);cout<<"Multiply A"<<i<<","<<sij;cout<<" and A"<<(sij+1)<<","<<

18、;j<<endl;算法通過數(shù)組m記錄子問題的最優(yōu)值，m初始化為0，表明相應(yīng)的子問題還沒有被計算。在調(diào)用LookupChain時，若mij>0，則表示其中存儲的是所要求子問題的計算結(jié)果，直接返回即可。否則與直接遞歸算法一樣遞歸計算，并將計算結(jié)果存入mij中返回。備忘錄算法耗時O(n3)，將直接遞歸算法的計算時間從2n降至O(n3)。3、動態(tài)規(guī)劃迭代實現(xiàn)     用動態(tài)規(guī)劃迭代方式解決此問題，可依據(jù)其遞歸式自底向上的方式進行計算。在計算過程中，保存已解決的子問題的答案。每個子問題只計算一次，而在后面需要時只需簡單檢查一下，從而避免了大量的重復(fù)計算，最

19、終得到多項式時間的算法。/3d1-2 矩陣連乘 動態(tài)規(guī)劃迭代實現(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 <iostream> using namespace std; const int L = 7;int MatrixChain(int n,int *m,int *s,int *p); void Traceback(int i,int j,int *s);/構(gòu)造最優(yōu)解int main()int

20、 pL=30,35,15,5,10,20,25; int *s = new int *L;int *m = new int *L;for(int i=0;i<L;i+) si = new intL;mi = new intL; cout<<"矩陣的最少計算次數(shù)為："<<MatrixChain(6,m,s,p)<<endl;cout<<"矩陣最優(yōu)計算次序為："<<endl;Traceback(1,6,s);return 0;int MatrixChain(int n,int *m,int *

21、s,int *p)for(int i=1; i<=n; i+)mii = 0;for(int r=2; r<=n; r+) /r為當前計算的鏈長（子問題規(guī)模） for(int i=1; i<=n-r+1; i+)/n-r+1為最后一個r鏈的前邊界 int j = i+r-1;/計算前邊界為r，鏈長為r的鏈的后邊界 mij = mi+1j + pi-1*pi*pj;/將鏈ij劃分為A(i) * ( Ai+1:j ) sij = i;for(int k=i+1; k<j; k+)/將鏈ij劃分為( Ai:k )* (Ak+1:j) int t = mik + mk+1j + pi-1*pk*pj;if(t<mij)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);cout<<"Multiply A"<<i<<","<<sij;cout<<" and A"<<(sij+1)<<",&qu