2023年矩陣連乘實驗報告

華北電力大學(xué)科技學(xué)院實驗報告實驗名稱矩陣連乘問題課程名稱計算機算法設(shè)計與分析專業(yè)班級:。軟件12K188。學(xué)生姓名:吳旭學(xué)號：，成績：指導(dǎo)老師：。劉老師實驗日期：指導(dǎo)老師：。劉老師實驗日期：2023.11.14環(huán)節(jié)。完畢實驗后，我認(rèn)為建立遞歸關(guān)系是很關(guān)鍵的一步，同時也是整個動態(tài)規(guī)劃算法的精髓。掌握了遞歸的思想，就可以完畢很多不必要的反復(fù)計算。具體到矩陣連乘問題，關(guān)鍵是解決斷開點k的位置和最少數(shù)乘次數(shù)?？傮w來說,這次實驗不僅讓我基本掌握遞歸的思想，并且進(jìn)一步提高了自己的自學(xué)能力和編程能力，代碼運用C語言寫出，可以很好的體會C語言和C++的不同點和相同點。我也體會到,想要理解一個新的算法，必須要通過自己不斷的編寫程序，不斷的思考才干真正的領(lǐng)悟,因此我會不斷朝著這個方向努力。一、實驗內(nèi)容矩陣連乘問題，給定〃個矩陣{AiA,...,An},其中Ai與Ai+I是可乘的，i=l,2,3...,n?l?？疾爝@〃個矩陣的連乘Ai,A2,…，二、重要思想由于矩陣乘法滿足結(jié)合律，故計算矩陣的連乘積可以有許多不同的計算順序。這種計算順序可以用加括號的方式來擬定。若一個矩陣連乘積的計算順序完全擬定，也就是說該連乘積已經(jīng)完全加括號，則可依此順序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積。完全加括號的矩陣連乘積可遞歸的定義為：(1)單個矩陣是完全加括號的；(2)矩陣連乘積A是完全加括號的，則A可表達(dá)為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)。運用動態(tài)規(guī)劃法解矩陣連乘積的最優(yōu)計算順序問題。按以下幾個環(huán)節(jié)進(jìn)行分析最優(yōu)解的結(jié)構(gòu)設(shè)計求解具體問題的動態(tài)規(guī)劃算法的第1步是刻畫該問題的最優(yōu)解的結(jié)構(gòu)特性。為方便起見，將矩陣連乘積簡記為A[i:j]?？疾煊嬎鉇[1:n]的最優(yōu)計算順序。設(shè)這個計算順序矩陣在Ak和Ak+i之間將矩陣鏈斷開，l〈kWn,則其相應(yīng)的完全加括號方式為((Ai…Ak)(Ak+i...An))o依此順序,先計算A[l:k]和A[k+1:n],然后將計算結(jié)果相乘得到A[l:n]0建立遞歸關(guān)系設(shè)計動態(tài)規(guī)劃算法的第二步是遞歸定義最優(yōu)值。對于矩陣連乘積的最優(yōu)計算順序問題，設(shè)計算A[i:j],iWiMjMn,所需的最少數(shù)乘次數(shù)為mEi][j],原問題的最優(yōu)值為當(dāng)i=j時，A[i:j]=Ai為單一矩陣，無需計算，因此m[i][i]=0,i=l,2,...no當(dāng)ivj時，可運用最優(yōu)子結(jié)構(gòu)性質(zhì)來計算mm[i][j]=m[i][k]+m[k+l][j]+pi-ipkPjo由于在計算時并不知道斷開點k的位置，所以k尚未定。計算最優(yōu)值根據(jù)計算m[i][j]的遞歸式，容易寫一個遞歸算法計算m[l][n]o動態(tài)規(guī)劃法解決此問題，可依據(jù)遞歸式以自底向上的方式進(jìn)行計算,在計算過程中保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡樸查一下，從而避免大量的反復(fù)計算，最終得到多項式時間的算法matrixChain。(見實驗代碼部分)構(gòu)造最優(yōu)解算法matrixChain只計算出最優(yōu)值，并沒有給出最優(yōu)解。但是matrixChain已經(jīng)記錄了構(gòu)造最優(yōu)解所需的所有信息。S[i][j]中的數(shù)表白，計算矩陣鏈A[i:j]的最佳方式應(yīng)在矩陣Ak和Ak+i之間斷開，最優(yōu)加括號方式為(A[i:k])(A[k+l:j])o依次構(gòu)造最優(yōu)解。(算法見實驗代碼部分）三、實驗結(jié)果輸入矩陣的個數(shù)＜注：小于100〉：4”輸入A1的件35嘛入A2的彳彳：15端入A3的牛5XXMWX*歹|J：10卜輸入A4的件10*-M*M**-M*^||：20其子如下：<<Alfi2XA3A4>>最少技乘次數(shù)為7125Pressanykeytocontinue四、結(jié)果驗證對實驗結(jié)果進(jìn)行驗證,4個矩陣分別是Ai[35*l5],A2[15*5],A3[5*10],A4[10*20]。依遞歸式有：0+2500+35x15x20=M[l][4]=min+1000+35x5x20=7125.4375+0+35x10x20=11375=7125且k=3o計算結(jié)果對的，證明所編寫的程序可對的算出最優(yōu)解。五、實驗代碼#include<stdio.h>#dcfincN100//定義最大連乘的矩陣個數(shù)是100voidmatrixChain(intp[],intm[N+1][N+1],ints[N+1][N+1])/*用二維數(shù)組來存儲Ai*.....Aj的最少數(shù)乘次數(shù)，用來存儲使Ai.....Aj獲得最少數(shù)乘次數(shù)相應(yīng)的斷開位置k,需要注意的是此處的N+1非常關(guān)鍵，雖然只用到的行列下標(biāo)只從1到N,但是下標(biāo)。相應(yīng)的元素默認(rèn)也屬于該數(shù)組，所以數(shù)組的長度就應(yīng)當(dāng)為N+1*/(Antn=N;//定義m,s數(shù)組的都是n*n的.不用行列下標(biāo)為()的元素，但涉及在該數(shù)組中for(inti=1；iV=n;i++)m/*將矩陣m的對角線位置上元素所有置0,此時應(yīng)是r=1的情況，表達(dá)先計算第一層對角線上個元素的值切for(intr=2;r<=n；r++)//r表達(dá)斜對角線的層數(shù)，從2取到n(gfor(inti=l;i<=n-r+1;i++)//i表達(dá)計算第r層斜對角線上第i行元素的值00|-intj=i+r-l;//j表達(dá)當(dāng)斜對角線層數(shù)為r,行下標(biāo)為i時的列下標(biāo)am[i][j]=m[i+1]|j]+p[i-1]*p[i]*pU]；〃計算當(dāng)斷開位置為i時相應(yīng)的數(shù)乘次數(shù)°s[i][j]=i；//斷開位置為i。for(intk=i+l;k<j;k++)00(?！癷ntt=m[i][kj+m[k+1J[jj+p[k；/*計算斷開位置k為從i至Ijj(不涉及i和j)的所有取值相應(yīng)的。。(Ai*.....*Ak)*(Ak+1*.....Aj)的數(shù)乘次數(shù)*/:t；//將Ai*....Aj的最少數(shù)乘次數(shù)存入m[i][將s[i][j]=k;//將相應(yīng)的斷開位置k存入s[i][j]00000。}000}。}}voidtraceback(inti,intj,ints[][N+l])//用遞歸來實現(xiàn)輸出得到最小數(shù)乘次數(shù)的表達(dá)式(if(i==j){。叩rintf(“A%d"，i)；oeIse。printf("(");traceback(i,s[i][j],s);??traceback(s[i][j]+l,j,s);printf(H)");))voidmain()(intn;//用來存儲矩陣的個數(shù)Mntq[2*N];/*用q數(shù)組來存儲最原始的輸入(各矩陣的行和列)，重要目的是為了檢查這N個矩陣是否滿足連乘的條件*/intp[N+l],flag=14用p[i-1],p[i]數(shù)組來存儲A的階數(shù),flag用來判斷這N個矩陣是否滿足連乘*/intm[N+l][N+1];//用m[i][j]二維數(shù)組來存儲Ai*……Aj的最小數(shù)乘次數(shù)ints[N+l][N+l];//用s來存儲使AiAj獲得最小數(shù)乘次數(shù)相應(yīng)的斷開位置kOprinlf("輸入矩陣的個數(shù)(注：小于100):“);scant("％d”,&n);for(inti=0;i<=2*n—I;i++)//各矩陣的階數(shù)的輸入先存入數(shù)組q中接受檢查ooif(i%2==0)00|oprintf("\nM);。printf("*輸入A%d的行:”,(i/2)+1);00|。空Ise°{。oprintf(”********列:”)；}oscanf(H%d';&q[i])；}for(i=1;i<=2*n—2；i++)//矩陣連乘條件的檢查。if(i%2!=0&&q[i]!=q[i+1])00|flag=0;。break；0)0)?fbr(intj=l;j<=n-1;j++)if(flag!=O)P[0]=q[()];。叩[n]=qf2*n-l];matrixCha