矩陣乘法最優(yōu)算法

1、動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)姓名：趙成兵學(xué)號(hào)：20062353班級(jí)：軟件工程2班1. 問題描述多個(gè)矩陣做乘法時(shí)最多的操作是做乘法運(yùn)算，矩陣乘法是滿足結(jié)合律的，不同的結(jié)合方式乘法運(yùn)算次數(shù)相差非常大，在矩陣的階較大和矩陣數(shù)目很大時(shí)，這成為制約程序效率的關(guān)鍵，窮舉找出最優(yōu)結(jié)合方式顯然是無效的，結(jié)合方式非常的多。所以利用動(dòng)態(tài)規(guī)劃解決此問題，給出最少的乘法次數(shù)。2算法設(shè)計(jì)思想及描述動(dòng)態(tài)規(guī)劃思想類似于分治，總是把規(guī)模較大的問題分解成小的問題加以求解，原問題的解依賴于子問題的解，還有一個(gè)顯著特征就是原問題最優(yōu)解的條件就是子問題的最優(yōu)。不同的地方就是子問題樹中的子問題大量重復(fù)出現(xiàn)。為減少運(yùn)算，總是在第一次遇到時(shí)計(jì)算并保存

2、計(jì)算結(jié)果，以后遇到直接使用即可。動(dòng)態(tài)規(guī)劃求解算法，通常按以下幾個(gè)步驟進(jìn)行。（1） 分析最優(yōu)解性質(zhì)，刻畫其結(jié)構(gòu)特征（2） 遞歸定義最優(yōu)值（3） 自底向上的方式計(jì)算最優(yōu)解（4） 根據(jù)計(jì)算最優(yōu)值得到的信息，構(gòu)造一個(gè)最優(yōu)解本問題是最小乘次數(shù)，定義最優(yōu)結(jié)構(gòu)說明：當(dāng)i等于j時(shí)，取mij為0，否則取另外一個(gè)值，這時(shí)遞歸算最優(yōu)乘次基礎(chǔ)。3 算法分析動(dòng)態(tài)規(guī)劃算法可以解決的問題有一個(gè)特點(diǎn)，就是問題本身的最優(yōu)是在子問題的最優(yōu)方案基礎(chǔ)上的。這個(gè)算法只是給出了給定矩陣序列乘積所要計(jì)算的最少次數(shù)，并沒有給出給出如何最終的每次計(jì)算結(jié)合方式，但是在每次構(gòu)造最優(yōu)解時(shí)，數(shù)組result保存了截?cái)帱c(diǎn)的位置，即每次計(jì)算時(shí)結(jié)合斷開的下

3、標(biāo)k，通過遞歸到最后只剩2個(gè)數(shù)組時(shí)所有的矩陣相乘的結(jié)合方式就確定下來。即間接給出了如何計(jì)算的方案?？捎脛?dòng)態(tài)規(guī)劃算法求解的問題還具備另外一個(gè)要素就是子問題的重疊性質(zhì)，在遞歸 算法自頂向下求解問題時(shí)，每次產(chǎn)生的子問題不是新問題，有些子問題被反復(fù)計(jì)算多次。正是這樣，只是在第一次遇到問題時(shí)計(jì)算并保存結(jié)果，以后直接使用，這個(gè)算法只需多項(xiàng)式的事件，效率較高。矩陣乘法最優(yōu)算法代碼。（最終版）#include "stdio.h"#define N 50#define M 50#define O 50#define MAX 65535/為保持一定兼容性，相乘次數(shù)不應(yīng)超過整數(shù)的表示范圍void

4、 main()int aN,mmNM,resultNM;/mmij數(shù)組保存的是最少相乘次數(shù),其中i是開始的數(shù)組，j是最優(yōu)的數(shù)組，i從1開始有效int i,j,k,t,l,temp,rr;int n;printf("input the number of arrays:n");scanf("%d",&rr);printf("input the right xishu:n");/輸入的時(shí)候重復(fù)的數(shù)據(jù)只輸入一次for(i=0;i<rr+1;i+)scanf("%d",&ai); n=rr;for(i

5、=1;i<=n;i+)mmii=0;/數(shù)組本身和自己相乘，最少次數(shù)為0次for(l=2;l<=n;l+)for(i=1;i<=n-l+1;i+)j=i+l-1;mmij=MAX;/開始時(shí)賦值為最大值，無窮大的意思for(k=i;k<=j-1;k+)temp=mmik+mmk+1j+ai-1*ak*aj;/if(temp<mmij)mmij=temp;/取得最小的次數(shù)resultij=k;/保存每次截?cái)嗟奈恢?，非常重?printf("the most proper times is:%dn",mm1n);4 運(yùn)行環(huán)境Windows XP系統(tǒng)，VC+6.05 程序結(jié)果分析說明，輸入的行和列時(shí)遇到重復(fù)的數(shù)只輸入一次即可，這就是為什么程序運(yùn)行例子中8個(gè)矩陣相乘，輸入的是9的數(shù)據(jù)的原因了。值得注意的是，編程中使用的數(shù)據(jù)是int 類型的，所以矩陣個(gè)數(shù)不能太大，不