? ? ? ?問題描述：給定n個矩陣：A1,A2,...,An，其中Ai與Ai+1是可乘的，i=1，2...，n-1。確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少。輸入數據為矩陣個數和每個矩陣規模，輸出結果為計算矩陣連乘積的計算次序和最少數乘次數。

? ? ??問題解析：由于矩陣乘法滿足結合律，故計算矩陣的連乘積可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調用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)。每一種完全加括號的方式對應于一個矩陣連乘積的計算次序，這決定著作乘積所需要的計算量。

? ? ? 看下面一個例子，計算三個矩陣連乘{A1，A2，A3}；維數分別為10*100 , 100*5 , 5*50 按此順序計算需要的次數((A1*A2)*A3):10X100X5+10X5X50=7500次，按此順序計算需要的次數(A1*(A2*A3)):10*5*50+10*100*50=75000次

? ? ? 所以問題是：如何確定運算順序，可以使計算量達到最小化。? ? ??

? ? ??算法思路：

? ? ? 例：設要計算矩陣連乘乘積A1A2A3A4A5A6，其中各矩陣的維數分別是：

? ? ? A1：30*35; ? ? A2：35*15; ? ? A3：15*5; ? ? A4：5*10; ? ? A5：10*20; ? ? A6：20*25?

? ? ??遞推關系：

? ? ??設計算A[i:j]，1≤i≤j≤n，所需要的最少數乘次數m[i,j]，則原問題的最優值為m[1,n]。

? ? ? 當i=j時，A[i:j]=Ai，因此，m[i][i]=0，i=1,2,…,n
? ? ? 當i<j時，若A[i:j]的最優次序在Ak和Ak+1之間斷開，i<=k<j,則：m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。由于在計算是并不知道斷開點k的位置，所以k還未定。不過k的位置只有j-i個可能。因此，k是這j-i個位置使計算量達到最小的那個位置。

? ? ? 綜上，有遞推關系如下：

? ? ??? ??

? ? ??構造最優解：

? ? ? 若將對應m[i][j]的斷開位置k記為s[i][j]，在計算出最優值m[i][j]后，可遞歸地由s[i][j]構造出相應的最優解。s[i][j]中的數表明，計算矩陣鏈A[i:j]的最佳方式應在矩陣Ak和Ak+1之間斷開，即最優的加括號方式應為(A[i:k])(A[k+1:j)。因此，從s[1][n]記錄的信息可知計算A[1:n]的最優加括號方式為(A[1:s[1][n]])(A[s[1][n]+1:n])，進一步遞推，A[1:s[1][n]]的最優加括號方式為(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]])。同理可以確定A[s[1][n]+1:n]的最優加括號方式在s[s[1][n]+1][n]處斷開...照此遞推下去，最終可以確定A[1:n]的最優完全加括號方式，及構造出問題的一個最優解。

? ? ??1、窮舉法

? ? ??列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數乘次數，從中找出一種數乘次數最少的計算次序。

? ? ??對于n個矩陣的連乘積，設其不同的計算次序為P(n)。每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1...Ak)(Ak+1…An)可以得到關于P(n)的遞推式如下：

? ? ??

? ? ? 以上遞推關系說明，P(n)是隨n的增長呈指數增長的。因此，窮舉法不是一個多項式時間復雜度算法。

? ? ??2、重疊遞歸

? ? ??從以上遞推關系和構造最優解思路出發，即可寫出有子問題重疊性的遞歸代碼實現：

//3d1-1 重疊子問題的遞歸最優解

//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25

//p[0-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 **s,int *p);//遞歸求最優解

void Traceback(int i,int j,int **s);//構造最優解

int main()

{

int p[L]={30,35,15,5,10,20,25};

int **s = new int *[L];

for(int i=0;i<L;i++)

{

s[i] = new int[L];

}

cout<<"矩陣的最少計算次數為："<<RecurMatrixChain(1,6,s,p)<<endl;

cout<<"矩陣最優計算次序為："<<endl;

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)+p[i-1]*p[i]*p[j];

s[i][j] = i;

for(int k=i+1; k<j; k++)

{

int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + p[i-1]*p[k]*p[j];

if(t<u)

{

u=t;

s[i][j]=k;

}

}

return u;

}

void Traceback(int i,int j,int **s)

{

if(i==j) return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+1,j,s);

cout<<"Multiply A"<<i<<","<<s[i][j];

cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;

}

用算法RecurMatrixChain(1,4,s,p)計算a[1:4]的計算遞歸樹如下圖所示：

? ? ? 從上圖可以看出很多子問題被重復運算?？梢宰C明，該算法的計算時間T(n)有指數下界。設算法中判斷語句和賦值語句為常數時間，則由算法的遞歸部分可得關于T(n)的遞歸不等式：

? ? ?用數學歸納法可以證明，因此，算法RecurMatrixChain的計算時間也隨n指數增長。

? ? ??3、備忘錄遞歸算法

? ? ?備忘錄方法用表格保存已解決的子問題答案，在下次需要解決此子問題時，只要簡單查看該子問題的解答，而不必重新計算。備忘錄方法為每一個子問題建立一個記錄項，初始化時，該記錄項存入一個特殊的值，表示該子問題尚未求解。在求解的過程中，對每個帶求的子問題，首先查看其相應的記錄項。若記錄項中存儲的是初始化時存入的特殊值，則表示該問題是第一次遇到，此時計算出該子問題的解，并將其保存在相應的記錄項中，以備以后查看。若記錄項中存儲的已不是初始化時存入的特殊值，則表示該子問題已被計算過，相應的記錄項中存儲的是該子問題的解答。此時從記錄項中取出該子問題的解答即可，而不必重新計算。

//3d1-2 矩陣連乘 備忘錄遞歸實現

//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25

//p[0-6]={30,35,15,5,10,20,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);//構造最優解

int main()

{

int p[L]={30,35,15,5,10,20,25};

int **s = new int *[L];

int **m = new int *[L];

for(int i=0;i<L;i++)

{

s[i] = new int[L];

m[i] = new int[L];

}

cout<<"矩陣的最少計算次數為："<<MemoizedMatrixChain(6,m,s,p)<<endl;

cout<<"矩陣最優計算次序為："<<endl;

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; j<=n; j++)

{

m[i][j]=0;

}

}

return LookupChain(1,n,m,s,p);

}

int LookupChain(int i,int j,int **m,int **s,int *p)

{

if(m[i][j]>0)

{

return m[i][j];

}

if(i==j)

{

return 0;

}

int u = LookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+p[i-1]*p[i]*p[j];

s[i][j]=i;

for(int k=i+1; k<j; k++)

{

int t = LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + p[i-1]*p[k]*p[j];

if(t<u)

{

u=t;

s[i][j] = k;

}

}

m[i][j] = u;

return u;

}

void Traceback(int i,int j,int **s)

{

if(i==j) return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+1,j,s);

cout<<"Multiply A"<<i<<","<<s[i][j];

cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;

}

? ? ?算法通過數組m記錄子問題的最優值，m初始化為0，表明相應的子問題還沒有被計算。在調用LookupChain時，若m[i][j]>0，則表示其中存儲的是所要求子問題的計算結果，直接返回即可。否則與直接遞歸算法一樣遞歸計算，并將計算結果存入m[i][j]中返回。備忘錄算法耗時O(n^3)，將直接遞歸算法的計算時間從2^n降至O(n^3)。

? ? ? 4、動態規劃迭代實現

? ? ?用動態規劃迭代方式解決此問題，可依據其遞歸式自底向上的方式進行計算。在計算過程中，保存已解決的子問題的答案。每個子問題只計算一次，而在后面需要時只需簡單檢查一下，從而避免了大量的重復計算，最終得到多項式時間的算法。

//3d1-3 矩陣連乘 動態規劃迭代實現

//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25

//p[0-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);//構造最優解

int main()

{

int p[L]={30,35,15,5,10,20,25};

int **s = new int *[L];

int **m = new int *[L];

for(int i=0;i<L;i++)

{

s[i] = new int[L];

m[i] = new int[L];

}

cout<<"矩陣的最少計算次數為："<<MatrixChain(6,m,s,p)<<endl;

cout<<"矩陣最優計算次序為："<<endl;

Traceback(1,6,s);

return 0;

}

int MatrixChain(int n,int **m,int **s,int *p)

{

for(int i=1; i<=n; i++)

{

m[i][i] = 0;

}

for(int r=2; r<=n; r++) //r為當前計算的鏈長（子問題規模）

{

for(int i=1; i<=n-r+1; i++)//n-r+1為最后一個r鏈的前邊界

{

int j = i+r-1;//計算前邊界為r，鏈長為r的鏈的后邊界

m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//將鏈ij劃分為A(i) * ( A[i+1:j] )

s[i][j] = i;

for(int k=i+1; k<j; k++)

{

//將鏈ij劃分為( A[i:k] )* (A[k+1:j])

int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if(t<m[i][j])

{

m[i][j] = t;

s[i][j] = k;

}

}

}

}

return m[1][L-1];

}

void Traceback(int i,int j,int **s)

{

if(i==j) return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+1,j,s);

cout<<"Multiply A"<<i<<","<<s[i][j];

cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;

}

上述迭代算法的運行過程如下圖所示：

? ? ?如圖所示：

? ? ?當R=2時，先迭代計算出：

? ? ?m[1:2]=m[1:1]+m[2:2}+p[0]*p[1]*p[2]；

? ? ?m[2:3]=m[2:2]+m[3:3]+p[1]*p[2]*p[3];

? ? ?m[3:4]=m[3:3]+m[4][4]+p[2]*p[3]*p[4];

? ? ?m[4:5]=m[4:4]+m[5][5]+p[3]*p[4]*p[5];

? ? ?m[5:6]=m[5][5]+m[6][6]+p[4]*p[5]*p[6]的值；

? ? ?當R=3時，迭代計算出：

? ? ?m[1:3]=min(m[1:1]+m[2:3]+p[0]*p[1]*p[3],m[1:2]+m[3:3]+p[0]*p[2]*p[3]);

? ? ?m[2:4]=min(m[2:2]+m[3:4]+p[1]*p[2]*p[4],m[2:3]+m[4:4]+p[1]*p[3]*p[4]);

? ? ?......

? ? ?m[4:6]=min(m[4:4]+m[5:6]+p[3]*p[4]*p[6],m[4:5]+m[6:6]+p[3]*p[5]*p[6]);

? ? ?......

? ? ?依次類推，根據之前計算的m值，迭代計算最優解。與備忘錄方法相比，此方法會將每個子問題計算一遍，而備忘錄方法則更靈活，當子問題中的部分子問題不必求解釋，用備忘錄方法較有利，因為從控制結構可以看出，該方法只解那些確實需要求解的子問題。

? ? ?程序運行結果如下：

本文轉載自：http://blog.csdn.net/liufeng_king/article/details/8497607#?

總結

以上是生活随笔為你收集整理的矩阵连乘问题的算法分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。