矩陣連乘試驗報告

1、華北電力大學科技學院實驗報告實驗名稱課稈名廉廿算機算法玻廿與分析專業(yè)甌軟件12K1學 號：4指導老輛：X老師學生XX： X旭成 瓠實驗日期：2014.11.14一、實驗內(nèi)容拒陣連乘間題，給定個矩陣AA，,An,其中A與Ad是可乘ff, i=1,2,3.,n-1o 考察這個矩陣的連乘 AA2,.,An二、主要思想由于矩陣乘法滿足結(jié)合律，故廿算矩陣的連乘枳可以有許鄉(xiāng)不 同的廿算次序。這種廿算次序可以用加括號的方式來確定。若一個 矩陣連乘枳的汁算次序完全確定，也就是說該連乘枳已經(jīng)完全加牯 號，則可依此次序反復調(diào)用2個矩陣相乘的標準算法廿算出矩陣連 乘枳。完全加括號的矩陣連乘枳可遞歸的定義為:單個矩陣

2、是完全加括號的；(2)矩陣連乘枳A是完全加括號舸，則A可表示為2個完全加括號的 矩陣連乘枳B和C的乘枳并加括號，BP A=(BC)O運用動態(tài)規(guī)劃法解矩陣連乘枳的最優(yōu)廿算次序間題。按以下幾個步驟進行1、分橋最優(yōu)解的結(jié)構(gòu)設廿求解具體間題的動態(tài)規(guī)則算法的第1步是刻畫該間題的最優(yōu)解的結(jié)構(gòu)特征。為方便起見，將矩陣連乘枳簡記為Ai:jo考察廿算A1:n的最優(yōu)廿算次序。設Stit算次序矩陣在Ak和A由之間將矩陣SKiff,，則其相應的完全加括號方式為(A1.Ak)(Ak+1.An)o依此次序,先廿算A1:k和Ak+1:n,然后將廿算結(jié)果相乘得到A1 :no2、建立遞歸關(guān)系設廿動態(tài)規(guī)劃算法的第二步是遞舊定義最

3、優(yōu)值。對于拒陣連乘枳 的最優(yōu)廿算次序間題，設計算Ai:j,所需的最少數(shù)乘次數(shù)為mij, 原間題的最優(yōu)值為m1no當 i=j Bt,Ai:j=A,為單-拒陣，無需廿算，因此 mii=0,i=1,2,.no 當i<j時，可和用最優(yōu)子結(jié)構(gòu)性質(zhì)來廿算mij。mij=mik+mk+1j+pi_lpkpjo由于在廿算時并不知道斷開點k的位 置，所以kjj未定。3、廿算最優(yōu)值根據(jù)計算mij的遞歸式，容易寫一個遞歸算法廿算m1no動 態(tài)規(guī)則法解決此間題，可依據(jù)遞歸式以自底向上的方式進行計算,在 廿算過程中保存已解決的子間題答案。每f子問題只it算一次，而在 后面需要時只要簡單査一下，從而避免大量的重復廿

4、算，最終得到多 項式時間的算法matrixChaino (見實驗代碼部分)4、構(gòu)造量優(yōu)解算法matrixchain只廿算出最優(yōu)值，并沒有給出最優(yōu)解。但是 matrixchain已經(jīng)記錄了構(gòu)造最優(yōu)解所需的全部信息。Sij中的數(shù)表明，計算矩陣鏈Ai:j的最佳方式應在矩陣幾和Ak+i之間斷開,最優(yōu)加 括號方式為(Ai:k)(Ak+1:j)o依次構(gòu)造最優(yōu)解。(算法見實驗代碼部分)實驗結(jié)果、結(jié)果驗證理輕卑色上趕字：小于詢：4唏入FU的行35*«啪入A4的行斗0 M*M*M*M| | : 20式子如下,.C(fllfl2>Cft3fi4»最少數(shù)乘次數(shù)為刃25.Press any

5、key to continue>«*歹 I ：15黃輸入A2的行二15列:5浜輸入A3的行二5：10對實驗結(jié)果進行驗證，4個矩陣分別是A,35*15, M15*5,A35*10, A410*20o 依遞 I月式有:0 + 2500 + 35 x 15 x 20 = 1300o 2625 十 1000 4- 35x5 x 20 = 7125 M14=minl4375 +0 + 35 x lo x 20 = 11375=7125且 k=3o廿算結(jié)果正確，證明所編寫的程序可正確算出最優(yōu)解。五、實驗代碼#include<stdio.h>#define N 100定義最XX乘

6、的矩陣個數(shù)是100void matrixChain(int p,int mN+1N+1,int sN+1N+1)/* 用 二維數(shù)組來存B Ai*.Aj的最少數(shù)乘次數(shù)，用sij來存儲使Ai.Aj獲得最少數(shù)乘次數(shù)對應的Biff EI k,需要注意的是 此處的N+1非常關(guān)建，雖然只用到的行列下標只從1到N,但是下標0對應的元素默認也揚于該數(shù)組，所以數(shù)組的長度就應該為N+1*/int n=N; 定義m,s數(shù)組的制是nF的,不用斤列下標為0的元素，但包桔在 該數(shù)組中forfint i=1;i<=n;i+)mii=0;/*«®Km的對角線位置上元素全部置0,此時應是匕1的悄況,表

7、示先it算第一層對角線上個元素的值*/forfint r=2;r<=n;r+)/r表示斜對角線的層數(shù)，H 2取到n(for(inti=1;i<=n-r+1;i+)/i表示it算第r層斜對角線上第i行元素的值int j=i+r-1 ;/j表示當斜對角線層數(shù)為r, 亍下標為i時的列下標mij=mi+1j+pi-1*pi*pj;/it 算當斷開位置為 i 時對應的數(shù)乘次數(shù)for (int k=i+1;k<j;k+)intt=mik+mk+1j+pi-1*pk*pj;/*it 算 Bi 開也置 k 為從 i 到 j (不包括i和j)的所有取值對應的(Ai*.*Ak) * ( Ak+1

8、 *.Aj)的數(shù)乘次數(shù)”/if(t<mij)mij=t;/« Ai*.Aj 的最少數(shù)乘次數(shù)存入 mijsij=k;/對應的Bfi開位置k存入sij式(if(i=j)Iprintf('A%d",i);else(printfCC)；traceback(i,sij,s);traceback(sij+1,j,s);Pintf(T);void main()int n;用來存儲矩陣的個數(shù)int q2*N;/*用q數(shù)組來存儲最原始的輸入(各矩陣的行和列),主要目的是 為了檢SHN個矩暉是否滿足連乘的條件"/intpN+1,flag=1;/*用pi-1,pi數(shù)組來存

9、儲A的階數(shù)，flag用來判斷這N個矩 陣是否滿足連乘*/intmN+1N+1;/用mijZ維數(shù)組來存儲Ai*.Aj的最小數(shù)乘次數(shù)int sN+1N+1;/用sij來存儲使Ai.Aj獲得最小數(shù)乘次數(shù)對應的斷開位 置kprintfC1輸入矩陣的個數(shù)(注:小干100)：");scanf("%d",&n);forfinti=0;i<=2*n-1;i+)/&矩陣的階數(shù)的輸入先存入數(shù)組q中接受槍驗(if(i%2=0)printfCn");printfC* 輸人 A%d 的行:",(”2)+1)；elseprintfC* 列 J；sca

10、nf(d=coq 三 XforT二介2*2寸+)、注專商潘渝一十3診啟(if(i%2ll0QQqmlrq=+二)f_a?o_ break-一for(=lr-1 亍 1 j+)(pm£2wiaadlro)(ff pmnqE 亍二 maMxchain(pm-sxtraceback(1,n,s);printf("n');printfCt 少數(shù)乘次數(shù)為%dn；m1n);else(printfC g%d個矩陣不能連乘!n",n);Ax實驗心得通過本次實驗，我較為透徊的理解了動態(tài)規(guī)則算法的幾個基本 步驟。完成實驗后，我認為建立遞舊關(guān)系是很關(guān)鍵的一步，同時也 是整個動態(tài)規(guī)則算法的精箭。掌握了遞舊舸思想，就可以完成很務不助要的重復廿算。貝休到矩陣連乘間題，關(guān)儺