1、動態(tài)規(guī)劃法解矩陣連乘問題實驗內(nèi)容給定n個矩陣A1,A2,.An，其中Ai與Ai+1是可乘的，i=1,2,3。，n-1。我們要計算這n個矩陣的連乘積。由于矩陣乘法滿足結(jié)合性，故計算矩陣連乘積可以有許多不同的計算次序。這種計算次序可以用加括號的方式確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則我們可依此次序反復調(diào)用2個矩陣相乘的標準算法計算出矩陣連乘積。解題思路將矩陣連乘積A(i)A(i+1)A(j)簡記為Ai:j，這里 i <= j。考察計算Ai:j的最優(yōu)計算次序。設這個計算次序在矩陣A(k)和A(k+1)之間將矩陣鏈斷開，i <= k < j, 則

2、其相應完全加括號方式為(A(i)A(i+1)A(k) * (A(k+1)A(k+2)A(j)。特征：計算Ai:j的最優(yōu)次序所包含的計算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。設計算Ai:j，1 <= i <= j <= n，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n 當i = j時，Ai:j=Ai，因此，mi,i = 0，i = 1,2,n當i < j時，mi,j = mi,k + mk+1,j + p(i-1)p(k)p(j)這里A(i)的維數(shù)為p(i-1)*(i)(注：p(i-1)為矩陣A(

3、i)的行數(shù)，p(i)為矩陣Ai的列數(shù))實驗實驗代碼#include <iostream>#include <vector>using namespace std ;class matrix_chainpublic: matrix_chain(const vector<int> & c) cols = c ; count = cols.size () ; mc.resize (count) ; s.resize (count) ; for (int i = 0; i < count; +i) mci.resize (count) ; si.res

4、ize (count) ; for (i = 0; i < count; +i) for (int j = 0; j < count; +j) mcij = 0 ; sij = 0 ; 1 / 5 / 記錄每次子問題的結(jié)果 void lookup_chain () _lookup_chain (1, count - 1) ; min_count = mc1count - 1 ; cout << "min_multi_count = "<< min_count << endl ; / 輸出最優(yōu)計算次序 _trackback (1

5、, count - 1) ; / 使用普通方法進行計算 void calculate () int n = count - 1; / 矩陣的個數(shù) / r 表示每次寬度 / i,j表示從從矩陣i到矩陣j / k 表示切割位置 for (int r = 2; r <= n; + r) for (int i = 1; i <= n - r + 1; + i) int j = i + r - 1 ; / 從矩陣i到矩陣j連乘，從i的位置切割，前半部分為0 mcij = mci+1j + colsi-1 * colsi * colsj ; sij = i ; for (int k = i +

6、 1; k < j; + k) int temp = mcik + mck + 1j + colsi-1 * colsk * colsj ; if (temp < mcij) mcij = temp ; sij = k ; / for k / for i / for r min_count = mc1n ; cout << "min_multi_count = "<< min_count << endl ; / 輸出最優(yōu)計算次序 _trackback (1, n) ; private: int _lookup_chain (i

7、nt i, int j) / 該最優(yōu)解已求出，直接返回 if (mcij > 0) return mcij ; if (i = j) return 0 ; / 不需要計算，直接返回 / 下面兩行計算從i到j按照順序計算的情況 int u = _lookup_chain (i, i) + _lookup_chain (i + 1, j) + colsi-1 * colsi * colsj ; sij = i ; for (int k = i + 1; k < j; + k) int temp = _lookup_chain(i, k) + _lookup_chain(k + 1, j

8、) + colsi - 1 * colsk * colsj ; if (temp < u) u = temp ; sij = k ; mcij = u ; return u ; void _trackback (int i, int j) if (i = j) return ; _trackback (i, sij) ; _trackback (sij + 1, j) ; cout <<i << "," << sij << " " << sij + 1 << ",&q

9、uot; << j << endl; private: vector<int> cols ; / 列數(shù) int count ; / 矩陣個數(shù) + 1 vector<vector<int> > mc; / 從第i個矩陣乘到第j個矩陣最小數(shù)乘次數(shù) vector<vector<int> > s; / 最小數(shù)乘的切分位置 int min_count ; / 最小數(shù)乘次數(shù) ;int main() / 初始化 const int MATRIX_COUNT = 6 ; vector<int> c(MATRIX_COUNT + 1) ; c0 = 30 ; c1 = 35 ; c2 = 15 ; c3 = 5 ; c4 = 10 ; c5 = 20 ; c6 = 25 ; matrix_chain mc (c) ; / mc.calculate () ; mc.lookup_chain () ; return 0 ;實驗結(jié)果實驗驗證連乘矩陣假如為：計算過程為：從m可知最小連乘次數(shù)為m16 =