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

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

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

3、標k，通過遞歸到最后只剩2個數(shù)組時所有的矩陣相乘的結(jié)合方式就確定下來。即間接給出了如何計算的方案?？捎脛討B(tài)規(guī)劃算法求解的問題還具備另外一個要素就是子問題的重疊性質(zhì)，在遞歸 算法自頂向下求解問題時，每次產(chǎn)生的子問題不是新問題，有些子問題被反復計算多次。正是這樣，只是在第一次遇到問題時計算并保存結(jié)果，以后直接使用，這個算法只需多項式的事件，效率較高。矩陣乘法最優(yōu)算法代碼。（最終版）#include "stdio.h"#define N 50#define M 50#define O 50#define MAX 65535/為保持一定兼容性，相乘次數(shù)不應超過整數(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ù)據(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;/開始時賦值為最大值，無窮大的意思for(k=i;k<=j-1;k+)temp=mmik+mmk+1j+ai-1*ak*aj;/if(temp<mmij)mmij=temp;/取得最小的次數(shù)resultij=k;/保存每次截斷的位置，非常重要 printf("the most proper times is:%dn",mm1n);4 運行環(huán)境Windows XP系統(tǒng)，VC+6.05 程序結(jié)果分析說明，輸入的行和列時遇到重復的數(shù)只輸入一次即可，這就是為什么程序運行例子中8個矩陣相乘，輸入的是9的數(shù)據(jù)的原因了。值得注意的是，編程中使用的數(shù)據(jù)是int 類型的，所以矩陣個數(shù)不能太大，不