【本文原創於Paul的博客園技術博客。】
【本文歡迎轉載，轉載請以鏈接形式注明出處。】
【本博客所有文章都經博主精心整理，請尊重我的勞動成果。】
【C++】 動態規劃—矩陣鏈乘
1、問題描述
給定n個矩陣構成的一個鏈給定｛A1,A2,…,An｝,其中i=1，2，...,n.矩陣Ai的維數為pi-1*pi，如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少。
2、最優子結構
對乘積A1A2...An的任意加括號方法都會將序列在某個地方分成兩部分，也就是最後一次乘法計算的地方，我們將這個位置記為k，也就是說首先計算A1...Ak和Ak+1...An，然後再將這兩部分的結果相乘。
最優子結構如下：假設A1A2...An的一個最優加括號把乘積在Ak和Ak+1間分開，則前綴子鏈A1...Ak的加括號方式必定為A1...Ak的一個最優加括號，後綴子鏈同理。
一開始並不知道k的確切位置，需要遍歷所有位置以保證找到合適的k來分割乘積。
3、狀態轉移方程
4、代碼實現
1 #include<iostream>
2 using namespace std;
3 //p為矩陣鏈，p[0],p[1]代表第一個矩陣，p[1],p[2]代表第二個矩陣，length為p的長度
4 //所以如果有六個矩陣，length=7，m為存儲最優結果的二維矩陣，t為存儲選擇最優結果路線的
5 //二維矩陣
6 void MatrixChainOrder(int *p,int (*m)[10],int (*t)[10],int length)
7 {
8 int n=length-1;
9 int i,j,k,q,num=0;
10 //A[i][i]只有一個矩陣，所以相乘次數為0，即m[i][i]=0;
11 for(i=1;i<length;i++)
12 {
13 m[i][i]=0;
14 }
15 //i代表矩陣鏈的長度，i=2表示有兩個矩陣相乘時如何劃分
16 for(i=2;i<=n;i++)
17 {
18 //j表示從第j個矩陣開始的i個矩陣如何劃分是最優
19 for(j=1;j<=n-i+1;j++)
20 {
21 //k為從第j個數i個矩陣就是k，從j到k表示他們之間的i個矩陣如何劃分
22 k=j+i-1;
23 //m[j][k]存儲了從j到k使用最佳劃分所得到的最優結果
24 m[j][k]=0x7fffffff;
25 //q為介於j到k-1之間的數，目的是利用q對j到k之間的矩陣進行試探性的劃分，
26 //從而找到最優劃分，這是一種遍歷性的試探。
27 for(q=j;q<=k-1;q++)
28 {
29 num=m[j][q]+m[q+1][k]+p[j-1]*p[q]*p[k];
30 if(num<m[j][k])
31 {
32 m[j][k]=num;
33 t[j][k]=q;
34 }
35 }
36 }
37 }
38 }
39 void PrintAnswer(int(*t)[10],int i,int j)
40 {
41 if(i==j)
42 {
43 cout<<"A"<<i;
44 }
45 else
46 {
47 cout<<"(";
48 PrintAnswer(t,i,t[i][j]);
49 PrintAnswer(t,t[i][j]+1,j);
50 cout<<")";
51 }
52
53 }
54 int main()
55 {
56 int p[7]={30,35,15,5,10,20,25};
57 int m[10][10],t[10][10];
58 MatrixChainOrder(p,m,t,7);
59 MatrixChainOrder(p,m,t,7);
60 PrintAnswer(t,1,6);
61 cout<<endl;
62 return 0;
63 }
