題目
設A1,A2,…,An為矩陣序列，Ai為Pi-1×Pi階矩陣，i = 1,2,…,n. 確定乘法順序使得元素相乘的總次數最少.
輸入：向量P = <P0, P1, … , Pn>
實例：
P = <10, 100, 5, 50> A1: 10 × 100, A2: 100 × 5, A3: 5 × 50
乘法次序：
(A1 A2)A3: 10 × 100 × 5 + 10 ×5 × 50 = 7500
A1(A2 A3): 10 × 100 × 50 + 100 × 5 × 50 = 75000
搜索空間的規模
先將矩陣鏈加括號分為兩部分，即P=A1*A2*...*An=（A1*A2...*Ak）*（Ak+1*...An），則有f(n)=f(1)*f(n-1)+f(2)*f(n-2)+...+f(n-1)*f(1)種方法。f(n)為一個Catalan數，所以一般的方法要計算種。
動態規劃算法
輸入P=< P0, P1, …, Pn>，Ai..j 表示乘積 AiAi+1…Aj 的結果，其最後一次相乘是：
Ai..j = Ai..k Ak+1..j
m[i,j] 表示得到Ai..j的最少的相乘次數。
遞推方程：
為了確定加括號的次序，設計表s[i,j],記錄求得最優時最一位置。
算法遞歸實現
由上面的遞歸公式，很容易得到算法的遞歸實現：
[cpp]
const int N=5;
int m[N][N]; //m[i][j]存儲Ai到Aj的最小乘法次數
int s[N][N];//s[i][j]存儲Ai到Aj之間加括號的位置
int RecurMatrixChain(int P[],int i,int j)
{
m[i][j]=100000;
s[i][j]=i;
if(i==j)
m[i][j]=0;
else{
for(int k=i;k<j;k++){
int q=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+P[i]*P[k+1]*P[j+1];
if(q<m[i][j]){
m[i][j]=q;
s[i][j]=k;
}
}
}
return m[i][j];
}
int main()
{
int P[N+1]={30,35,15,5,10,20};
for(int i=0;i<N;i++)
m[i][i]=0;
m[0][N-1]=RecurMatrixChain(P,0,N-1);
return 0;
}
遞歸實現的復雜性
復雜性滿足遞推關系：
由數學歸納法可得：
可見遞歸實現的復雜性雖然較一般算法有改進，但還是較高。分析原因，主要是子問題重復程度高。如下圖所示：
1..4表示計算Ai..j中i=1,j=4的子問題，其子問題包括A1..1，而A1..2，A1..3中都包括子問題A1..1，所以很多子問題被重復計算了多次。
於是，我們想到用自底向上的迭代實現。
算法迭代實現
迭代實現主要思想是子問題由小到大，每個子問題只計算一次，並且把結果保存起來，後來用到這個子問題時，直接代入。
[cpp]
void MatrixChain(int P[],int n)
{
int r,i,j,k,t;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
m[i][j]=0;
//r為當前計算的鏈長（子問題規模）
for(r=2;r<=n;r++){
//n-r+1為最後一個r鏈的前邊界
for(i=0;i<n-r+1;i++){
//計算前邊界為r，鏈長為r的鏈的後邊界
j=i+r-1;
//將鏈ij劃分為A(i) * ( (A(i+1) ... A(j) )
m[i][j]=m[i+1][j]+P[i]*P[i+1]*P[j+1];
//記錄分割位置
s[i][j]=i;
for( k=i+1;k<j-1;k++){
//將鏈ij劃分為( A(i)...A(k) )* ( (A(k+1) ... A(j) )
t=m[i][k]+m[k+1][j]+P[i]*P[i+1]*P[j+1];
if(t<m[i][j]){
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
int main()
{
int P[N+1]={30,35,15,5,10,20};
MatrixChain(P,N);
}
迭代實現的復雜性
行7,9,16的循環為O(n)，外層循環為O(1)，所以算法復雜度W(n)=O(n^3)
迭代過程的一個實例
子問題由小到大的計算過程如下圖所示：
結果打印
再寫一個打印結果，以及打印優化函數備忘錄m和標記函數的s的函數：
[cpp]
void PrintMatrixChain(int s[][N],int i,int j)
{
if (i==j)
{
cout<<"A"<<i+1;
}
else
{
cout<<"(";
PrintMatrixChain(s, i, s[i][j]);
PrintMatrixChain(s, s[i][j]+1, j);
cout<<")";
}
}
void PrintMS(int m[][N],int s[][N],int N)
{
for(int r=0;r<N;r++){
for(int i=0;i<N-r;i++){
int j=i+r;
cout<<"m["<<i+1<<","<<j+1<<"]="<<m[i][j]<<"\t";
}
cout<<endl;
}
for(int r=1;r<5;r++){
for(int i=0;i<N-r;i++){
int j=i+r;
cout<<"s["<<i+1<<","<<j+1<<"]="<<s[i][j]+1<<"\t";
}
cout<<endl;
}
}
一個簡單的測試實例
用一個N=5，P=<30,35,15,5,10,20>的簡單實例，運行上述代碼：
