矩陣連乘問(wèn)題
問(wèn)題描述：
給定n個(gè)矩陣：A1,A2,…,An，其中Ai與Ai+1是可乘的，i=1，2…，n-1。確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣個(gè)數(shù)和每個(gè)矩陣規(guī)模，輸出結(jié)果為計(jì)算矩陣連乘積的計(jì)算次序和最少數(shù)乘次數(shù)。
問(wèn)題分析：
1.分析最優(yōu)解的結(jié)構(gòu)
設(shè)計(jì)求解具體問(wèn)題的動(dòng)態(tài)規(guī)劃算法的第一步是刻畫該問(wèn)題的最優(yōu)解的結(jié)構(gòu)特征。我們將矩陣連乘積AiAi+1…Aj簡(jiǎn)記為A[ i : j ]。考察計(jì)算A[ 1: n]的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，1<=k<n，則其相應(yīng)的完全加括號(hào)形式為((A1…Ak)(Ak+1…An))。以此次序，總的計(jì)算量為A[ 1 : k ]的計(jì)算量加上A[ k+1 : n ]的計(jì)算量， 再加上A[ 1 : k ]和A[ k+1 : n ]相稱的計(jì)算量。
這個(gè)問(wèn)題的關(guān)鍵特征是：計(jì)算A[ 1 :n ]的最優(yōu)次序所包含的計(jì)算矩陣子鏈a[ 1 : k ]和A[ k+1 : n ]的次序也是最優(yōu)的。因此，矩陣連乘積計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可以用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。

2.建立遞歸關(guān)系

從連乘矩陣個(gè)數(shù)為2開始計(jì)算每次的最小乘次數(shù)m[i][j]: m[0][1] m[1][2] m[2][3] m[3][4] m[4][5] //m[0][1]表示第一個(gè)矩陣與第二個(gè)矩陣的最小乘次數(shù)

然后再計(jì)算再依次計(jì)算連乘矩陣個(gè)數(shù)為3:m[0][2] m[1][3] m[2][4] m[3][5]

連乘矩陣個(gè)數(shù)為4：m[0][3] m[1][4] m[2][5]

連乘矩陣個(gè)數(shù)為5：m[0][4] m[1][5]

連乘矩陣個(gè)數(shù)為6：m[0][5] //即最后我們要的結(jié)果
　　　　　　　　　　

m[i][j]給出了最優(yōu)值，即計(jì)算A[i:j]所需的最少數(shù)乘次數(shù)。同時(shí)還確定了計(jì)算A[i:j]的最優(yōu)次序中的斷開位置k，也就是說(shuō)，對(duì)于這個(gè)k有m[i][j]=m[i[k]+m[k+1][j] + Pi-1*Pk*Pj

若將對(duì)應(yīng)于m[i][j]的斷開位置k記為s[i][j]，在計(jì)算最優(yōu)值m[i][j]后，可以遞歸地有s[i][j]構(gòu)造出相應(yīng)的最優(yōu)解。

計(jì)算最優(yōu)值

根據(jù)計(jì)算m[ i ][ j ]的遞歸式，容易寫一個(gè)遞歸算法計(jì)算m[ 1 ][ n ]。但是簡(jiǎn)單地遞歸將好費(fèi)指數(shù)計(jì)算時(shí)間。在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多次。這也是該問(wèn)題可以用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。
用動(dòng)態(tài)規(guī)劃算法解決此問(wèn)題，可依據(jù)其遞歸是以自底向上的方式進(jìn)行計(jì)算。在計(jì)算的過(guò)程中，保存以解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算。

#include<iostream> #include<cstring> using namespace std; const int maxsize = 100; int p[maxsize]{ 30,35,15,5,10,20,25 }; int m[maxsize][maxsize], s[maxsize][maxsize];//m[i][j]存儲(chǔ)最優(yōu)解 int n = 6;void MatrixChain() {int i, r, j, k;for (int i = 1; i <= n; i++) { m[i][i] = 0;//對(duì)角線為0；規(guī)模為1時(shí)；}for (r = 2; r <= n; r++)//矩陣連乘的規(guī)模為r ，從2開始{for (i = 1; i <= n - r + 1; i++)//最大可起始點(diǎn){j = i + r - 1;//j-i=r-1；m[i][j] = 0x7f7f7f7f;//另開始時(shí)m[i][j]為無(wú)窮大；s[i][j] = i;//s[][]存儲(chǔ)各子問(wèn)題的決策點(diǎn)，即一開始k為該點(diǎn)。for (k = i; k < j; k++)//尋找最優(yōu)值{int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];//求出分割點(diǎn)為k時(shí)的乘積if (t < m[i][j])//求出最小值，將分割點(diǎn)s[i][j]設(shè)置為k；{m[i][j] = t;s[i][j] = k;}}}} }void print(int i, int j) {if (i == j)//回歸條件{cout << "A" << i << "";return;}cout << "(";print(i, s[i][j]);print(s[i][j] + 1, j);//遞歸1到s[1][j]cout << ")"; }int main() {MatrixChain();print(1, n);cout << endl;cout << m[1][n] << endl; }

總結(jié)

以上是生活随笔為你收集整理的矩阵连乘问题（c++）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。