矩陣相乘問題描述：給定n個矩陣{A1，A2，...，An}，當然A1到An的任意段都是可乘的，求最小相乘次數。例如有三個矩陣維數分別為：10*100，100*2，2*5；若前兩個相乘，再乘第三個，總的相乘次數=10*100*2+10*2*5=2100；若第二個與第三個先相乘，在乘第一個，總相乘次數=100*2*5+10*100*5=5100；顯然，相乘次序會對計算量有很大影響，如果你在學線性代數的時候，寫了一個矩陣相乘的程序，結果跑到同學那里演示的時候，半天沒運行出來，那就尷尬了！！！
函數調用一般會要傳參，這些參數都是非常有意義。這個題目屬于動態規劃，最重要的一點就是想到一個二維數組m[i][j]，代表矩陣i到矩陣j相乘的最優解，然后就是怎樣給這個有意義的數組置數了，這種數組定義和數組置數若成，則我們要的答案就在m[1][n]中，代表矩陣1到矩陣n相乘的最優解。（如果你很饑渴的想解決這個問題，就直接看代碼吧！！）有人可能會問，為什么會想到這種數組定義，主要有兩個方面：一，學習（高效），看多了自然會想到給數組某種意義，培育一種思想；二、思考與分析，來的緩慢，但是凌駕與學習之上，也是學習的目的，是終極武器，也是基礎武器。。。。
不扯了，回到主題，很明顯如果只有一個矩陣，相乘次數為零；如果有兩個，直接相乘，若第一個矩陣維數q*p，第二個矩陣維數p*r，相乘次數為q*p*r；三個矩陣相乘，為前兩相乘，再乘第三個，和后兩個先相乘，再乘第一個，取其優者；四個矩陣相乘，設第三個矩陣維數r*t，第四個矩陣t*k，維數min{前三個矩陣最優值+q*t*k，前兩個矩陣最優+后兩個矩陣最優+q*r*k，前一個矩陣最優+后三個矩陣最優+q*p*k}；然后。。。
有人可能會問：我可以算出前一個，前兩個，前三個矩陣相乘的最優，但是我怎么算出后一個，后兩個，后三個相乘的最優呢？
其實這個問題又回到了原點，這就是動態規劃的妙處，顯然我們先求出A1到An的任意段長度為2矩陣的最優（直接相乘），然后可以計算出任意段長度為3矩陣的最優；然后。。。然后我們就想了個m[i][j]出來，記錄我們求的的結果；然后再寫代碼，嘗試思想的準確性，當然我們更多的時候是站在先人的肩膀上做驗證工作。。。
代碼如下（參考教科書）：
#include<iostream>
using namespace std;
void chain(int *p,int n,int m[][7],int s[][7])//p維數數組，m最優乘次數組，s記錄劃分方案
{
int j;
for(int i=1;i<=n;i++)
m[i][i]=0;
for(int r=2;r<=n;r++)
{
for(i=1;i<=n-r+1;i++)
{
j=i+r-1;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;k<j;k++)
{
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;
}
}
}
}
for(i=1;i<=n;i++) //我把它翻過來輸出。。。
{
for(j=n;j>=i;j--)
{
cout<<m[i][j]<<' ';
}
cout<<endl;
}
}
void Traceback(int i,int j,int s[][7]) //輸出相乘方案
{
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 B "<<(s[i][j]+1)<<","<<j<<endl;
return;
}
int main()
{
int p[7],m[7][7],s[7][7],n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<=n;i++)
{
scanf("%d",&p[i]);
}
chain(p,n,m,s);
Traceback(1,6,s);
}
return 0;
}
/**//*
p52
測試數據：
6
30 35 15 5 10 20 25
*/
運行結果：
posted on 2010-09-04 11:53
jince 閱讀(2544)
評論(0) 編輯 收藏 引用 所屬分類:
算法設計與分析