注：當(dāng)時(shí)在學(xué)矩陣連乘的時(shí)候，在網(wǎng)上發(fā)現(xiàn)這篇文章總結(jié)的不錯(cuò)，便摘抄了下來(lái)，今天與大家共享。同時(shí)望原創(chuàng)不要見(jiàn)怪！

動(dòng)態(tài)規(guī)劃之矩陣連乘

給定n個(gè)矩陣{A1,A2,…,An}，其中Ai與Ai+1是可乘的，i=1,2,…,n-1。考察這n個(gè)矩陣的連乘積A1A2…An。由于矩陣乘法滿足結(jié)合律，故計(jì)算矩陣的連乘積可以有許多不同的計(jì)算次序，這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法（有改進(jìn)的方法，這里不考慮）計(jì)算出矩陣連乘積。若A是一個(gè)p×q矩陣，B是一個(gè)q×r矩陣，則計(jì)算其乘積C=AB的標(biāo)準(zhǔn)算法中，需要進(jìn)行pqr次數(shù)乘。

矩陣連乘積的計(jì)算次序不同，計(jì)算量也不同，舉例如下：

先考察3個(gè)矩陣{A1,A2,A3}連乘，設(shè)這三個(gè)矩陣的維數(shù)分別為10×100，100×5，5×50。若按（（A1A2）A3）方式需要的數(shù)乘次數(shù)為10×100×5＋10×5×50＝7500，若按（A1（A2A3））方式需要的數(shù)乘次數(shù)為100×5×50＋10×100×50＝75000。

下面使用動(dòng)態(tài)規(guī)劃法找出矩陣連乘積的最優(yōu)計(jì)算次序。

1，??設(shè)矩陣連乘積AiAi+1…Aj簡(jiǎn)記為A[i:j]，設(shè)最優(yōu)計(jì)算次序在Ak和Ak+1之間斷開(kāi)，則加括號(hào)方式為：

（（AiAi+1…Ak）（Ak+1…Aj））

則依照這個(gè)次序，先計(jì)算A[i:k]和A[K+1:j]然后再將計(jì)算結(jié)果相乘，計(jì)算量是：

A[i:k]的計(jì)算量加上A[K+1:j]的計(jì)算量再加上它們相乘的計(jì)算量。

問(wèn)題的一個(gè)關(guān)鍵是：計(jì)算A[i:j]的最優(yōu)次序所包含的兩個(gè)子過(guò)程（計(jì)算A[i:k]和A[K+1:j]）也是最優(yōu)次序。

2，??設(shè)計(jì)算A[i:j]所需的最少數(shù)乘次數(shù)為m[i][j]。

i=j時(shí)為單一矩陣，則m[i][i]=0，

i<j時(shí)，設(shè)最優(yōu)計(jì)算次序在Ak和Ak+1之間斷開(kāi)，則m[i][j]=m[i][k]+m[k+1][j]+pipk+1pj+1，其中p表示數(shù)組的維數(shù)，例如A0到A5共6個(gè)數(shù)組（為了C語(yǔ)言的描述方便，下標(biāo)從0開(kāi)始），他們表示如下：

//p[0]:第一個(gè)矩陣的行數(shù)

????//p[1]:第一個(gè)矩陣的列數(shù)，第二個(gè)矩陣的行數(shù)

????//p[2]:第二個(gè)矩陣的列數(shù)，第三個(gè)矩陣的行數(shù)

k此時(shí)并未確定，需要從i到j-1遍歷以尋找一個(gè)最小的m[i][j]。我們把這個(gè)最小的k放在s[i][j]。

?

以下是完整實(shí)現(xiàn)代碼，以一個(gè)具體的例子實(shí)現(xiàn)，稍加修改即可通用。

#include?<iostream>

using?namespace?std;

//

//MatrixChain計(jì)算m[i][j]所需的最少數(shù)乘次數(shù)

//并記錄斷開(kāi)位置s[i][j]

//

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

{

?????for(int?i=0;i<n;i++)

?????????m[i][i]=0;//單個(gè)矩陣相乘，所需數(shù)乘次數(shù)為0

?

?????//以下兩個(gè)循環(huán)是關(guān)鍵之一，以6個(gè)矩陣為例(為描述方便，m[i][j]用ij代替)

?????//需按照如下次序計(jì)算

?????//01?12?23?34?45

?????//02?13?24?35

?????//03?14?25

?????//04?15

?????//05

?????//下面行的計(jì)算結(jié)果將會(huì)直接用到上面的結(jié)果。例如要計(jì)算14，就會(huì)用到12，24；或者13，34等等

?????for(int?r=1;r<n;r++)

?????{

?????????for(int?i=0;i<n-r;i++)

?????????{

??????????????int?j=i+r;

??????????????//首先在i斷開(kāi)，即（Ai*（Ai+1...Aj））

??????????????m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i+1]*p[j+1];

??????????????s[i][j]=i;

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

??????????????{

???????????????????//然后在k（從i+1開(kāi)始遍歷到j(luò)-1）斷開(kāi)，即（（Ai...Ak)*（Ak+1...Aj））

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

???????????????????if(t<m[i][j])//找到更好的斷開(kāi)方法

???????????????????{

???????????????????????m[i][j]=t;//記錄最少數(shù)乘次數(shù)

???????????????????????s[i][j]=k;//記錄斷開(kāi)位置

???????????????????}

??????????????}

?????????}

?????}

?????//如果使用下面注釋的循環(huán)，則是按照如下次序計(jì)算

?????//01?02?03?04?05

?????//12?13?14?15

?????//23?24?25

?????//34?35

?????//45

?????//當(dāng)要計(jì)算時(shí)14，會(huì)用到12，24，而此時(shí)24并沒(méi)有被計(jì)算出來(lái)。

/*

?????for(int?i=0;i<n;i++)

?????{

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

?????????{

??????????????m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i+1]*p[j+1];

??????????????s[i][j]=i;

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

??????????????{

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

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

???????????????????{

???????????????????????m[i][j]=t;

???????????????????????s[i][j]=k;

???????????????????}

??????????????}

?????????}

?????}

?????*/

}

//

//Traceback打印A[i:j]的加括號(hào)方式

//

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

{

?????//s[i][j]記錄了斷開(kāi)的位置，即計(jì)算A[i:j]的加括號(hào)方式為：

?????//(A[i:s[i][j]])*(A[s[i][j]+1:j])

?????if(i==j)return;

?????Traceback(i,s[i][j],s);//遞歸打印A[i:s[i][j]]的加括號(hào)方式

?????Traceback(s[i][j]+1,j,s);//遞歸打印A[s[i][j]+1:j]的加括號(hào)方式

?

?????//能走到這里說(shuō)明i等于s[i][j]，s[i][j]+1等于j

?????//也就是說(shuō)這里其實(shí)只剩下兩個(gè)矩陣，不必再分了

?????cout<<"A"<<i<<"和A"<<(s[i][j]+1)<<"相乘"<<endl;???

}

?

int?_tmain(int?argc,?_TCHAR*?argv[])

{

?????int?n=6;//矩陣的個(gè)數(shù)

?????int?*p=new?int[n+1];

?????//p[0]:第一個(gè)矩陣的行數(shù)

?????//p[1]:第一個(gè)矩陣的列數(shù)，第二個(gè)矩陣的行數(shù)

?????//p[2]:第二個(gè)矩陣的列數(shù)，第三個(gè)矩陣的行數(shù)

?????p[0]=30;

?????p[1]=35;

?????p[2]=15;

?????p[3]=5;

?????p[4]=10;

?????p[5]=20;

?????p[6]=25;

?

?????int?**m,**s;

?????m=new?int*[n];

?????for(?int?i=0;i<n;i++)

?????????m[i]=new?int[n];

?

?????s=new?int*[n];

?????for(int?i=0;i<n;i++)

?????????s[i]=new?int[n];??

?

?????MatrixChain(p,n,m,s);

?????Traceback(0,n-1,s);

for(int?i=0;i<n;i++)??

?????????{??

??????????????delete?[]m[i];

??????????????m[i]=NULL;

??????????????delete?[]s[i];

??????????????s[i]=NULL;

?????????}??

?????????delete?[]m;??

?????????m=NULL;?

?????????delete?[]s;??

?????????s?=?NULL;

?????????delete?[]p;??

?????????p?=?NULL;?

?????return?0;

}

打印結(jié)果是：

A1和A2相乘

A0和A1相乘

A3和A4相乘

A3和A5相乘

A0和A3相乘

實(shí)際上要表達(dá)的是如下加括號(hào)方式：

（（A0（A1A2））（（A3A4）A5））

加了括號(hào)之后用第一個(gè)來(lái)代替，例如（A1A2）可看作A1，這個(gè)結(jié)果的數(shù)乘次數(shù)是15125。

?

具體實(shí)例見(jiàn)：

NYOJ 460 項(xiàng)鏈

NYOJ 536 開(kāi)心的mdd

總結(jié)

以上是生活随笔為你收集整理的动态规划之矩阵连乘讲解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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