動態(tài)規(guī)劃矩陣連乘算法(文件)
【正文】 }include include iostream using namespace std。void Traceback(int i,int j,int **s)。 for(int i=0。 } cout矩陣的最少計算次數(shù)為：MemoizedMatrixChain(6,m,s,p)endl。}int MemoizedMatrixChain(int n,int **m,int **s,int *p){ for(int i=1。 j++) { m[i][j]=0。 } int u = LookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+p[i1]*p[i]*p[j]。 k++) { int t = LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + p[i1]*p[k]*p[j]。 return u。 coutMultiply Ai,s[i][j]。否則與直接遞歸算法一樣遞歸計算，并將計算結(jié)果存入m[i][j]中返回。 //3d12 矩陣連乘 動態(tài)規(guī)劃迭代實現(xiàn)//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25//p[06]={30,35,15,5,10,20,25}include include iostream using namespace std。//構(gòu)造最優(yōu)解int main(){ int p[L]={30,35,15,5,10,20,25}。iL。 cout矩陣最優(yōu)計算次序為：endl。 i=n。 r++) //r為當(dāng)前計算的鏈長（子問題規(guī)模） { for(int i=1。//將鏈ij劃分為A(i) * ( A[i+1:j] ) s[i][j] = i。 if(tm[i][j]) { m[i][j] = t。 Traceback(i,s[i][j],s)。}上述迭代算法的運行過程如下圖所示： m[2:3]=m[2:2]+m[3:3]+p[1]*p[2]*p[3]。m[3:4]=m[3:3]+m[4][4]+p[2]*p[3]*p[4]。m[4:5]=m[4:4]+m[5][5]+p[3]*p[4]*p[5]。m[5:6]=m[5][5]+m[6][6]+p[4]*p[5]*p[6]的值； 依次類推，根據(jù)之前計算的m值，迭代計算最優(yōu)解。 ......m[2:4]=min(m[2:2]+m[3:4]+p[1]*p[2]*p[4],m[2:3]+m[4:4]+p[1]*p[3]*p[4])。m[1:3]=min(m[1:1]+m[2:3]+p[0]*p[1]*p[3],m[1:2]+m[3:3]+p[0]*p[2]*p[3])。 當(dāng)R=2時，先迭代計算出： coutMultiply Ai,s[i][j]。 } } } } return m[1][L1]。 kj。 i++)//nr+1
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1