矩陣相乘的算法設(shè)計(jì)

《矩陣相乘的算法設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程實(shí)驗(yàn)報(bào)告課題矩陣相乘的算法設(shè)計(jì)專業(yè)班級(jí)網(wǎng)工專業(yè)1405班學(xué)號(hào)14144501352姓名陳曉露指導(dǎo)教師陶躍進(jìn)目錄一、問題描述二、問題分析1、分析最優(yōu)解的結(jié)構(gòu)2、建立遞歸關(guān)系3、遞歸實(shí)現(xiàn)的復(fù)雜性4、算法迭代實(shí)現(xiàn)三、結(jié)果輸出四、實(shí)驗(yàn)總結(jié)一、問題描述給定n個(gè)矩陣｛A1，A2，...，An｝，其中這n個(gè)矩陣是可相乘的，i＝1，2，...，n-1。算出這n個(gè)矩陣的相乘積A1A2。。。An。補(bǔ)充：如果兩個(gè)矩陣A和B是可相乘的，那么A的列數(shù)要和B的行數(shù)是相同的，否則，這兩個(gè)矩陣是不可相乘的。它們的相乘結(jié)果矩陣C的行

2、數(shù)是A的行數(shù)，而列數(shù)是B的列數(shù)。設(shè)A1,A2,…,An為矩陣序列，Ai為Pi-1×Pi階矩陣，i=1,2,…,n.確定乘法順序使得元素相乘的總次數(shù)最少.輸入：向量P=實(shí)例：?P=<10,100,5,50>?A1:10×100,A2:100×5,A3:5×50乘法次序：(A1A2)A3:10×100×5+10×5×50=7500A1(A2A3):10×100×50+100×5×50=75000搜索空間的規(guī)模先將矩陣鏈加括號(hào)分為兩部分，即P=A1*A2*...*An=（A1*A2...*Ak）*（Ak

3、+1*...An），則有f(n)=f(1)*f(n-1)+f(2)*f(n-2)+...+f(n-1)*f(1)種方法。動(dòng)態(tài)規(guī)劃算法輸入P=，Ai..j表示乘積AiAi+1…Aj的結(jié)果，其最后一次相乘是：m[i,j]表示得到Ai..j的最少的相乘次數(shù)。遞推方程：為了確定加括號(hào)的次序，設(shè)計(jì)表s[i,j],記錄求得最優(yōu)時(shí)最一位置。二、問題分析由于矩陣乘法滿足結(jié)合律，故連乘積的計(jì)算可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一個(gè)矩陣連乘積的計(jì)算次序已完全確定，也就是說(shuō)該連乘積已完全

4、加括號(hào)，則我們可以通過(guò)反復(fù)調(diào)用兩個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。1.分析最優(yōu)解的結(jié)構(gòu)為了方便起見，我們將矩陣連乘AiAi+1。。。Aj記為A[i:j]。經(jīng)分析，計(jì)算A[1:n]的一個(gè)最優(yōu)次序所包含的計(jì)算矩陣子鏈A[1:k]和A[k:n]的次序也是最優(yōu)的。因此，矩陣連乘計(jì)算次序問題的最優(yōu)解包含著子問題的最優(yōu)解。2.建立遞歸關(guān)系用矩陣m[n][n]來(lái)存放A[i:j]相乘的計(jì)算次數(shù)，用p[n+1]用來(lái)存放矩陣的行數(shù)和列數(shù)。const?int?N=5;??int?m[N][N];?//m[i][j]存儲(chǔ)Ai到Aj的最小乘法

5、次數(shù)??int?s[N][N];//s[i][j]存儲(chǔ)Ai到Aj之間加括號(hào)的位置????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

6、,k+1,j)+P[i]*P[k+1]*P[j+1];??????????????if(q

7、]=0;??????m[0][N-1]=RecurMatrixChain(P,0,N-1);??????return?0;??}?3.遞歸實(shí)現(xiàn)的復(fù)雜性復(fù)雜性滿足遞推關(guān)系：可見遞歸實(shí)現(xiàn)的復(fù)雜性雖然較一般算法有改進(jìn)，但還是較高。分析原因，主要是子問題重復(fù)程度高。如下圖所示：?1..4表示計(jì)算Ai..j中i=1,j=4的子問題，其子問題包括A1..1，而A1..2，A1..3中都包括子問題A1..1，所以很多子問題被重復(fù)計(jì)算了多次。于是，我們想到用自底向上的迭代實(shí)現(xiàn)。4.算法迭代實(shí)現(xiàn)迭代實(shí)現(xiàn)主要思想是子問題由小到大，每個(gè)子問題

8、只計(jì)算一次，并且把結(jié)果保存起來(lái)，后來(lái)用到這個(gè)子問題時(shí)，直接代入。void?MatrixChain(int?P[],int?n)??{??????int?r,i,j,k,t;??????for(i=0;i