動態(tài)規(guī)劃矩陣連乘算法(參考版)
2025-07-25 00:49本頁面
【正文】 依次類推，根據(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])。 m[5:6]=m[5][5]+m[6][6]+p[4]*p[5]*p[6]的值； m[4:5]=m[4:4]+m[5][5]+p[3]*p[4]*p[5]。 m[3:4]=m[3:3]+m[4][4]+p[2]*p[3]*p[4]。 m[2:3]=m[2:2]+m[3:3]+p[1]*p[2]*p[3]。 當(dāng)R=2時，先迭代計算出： }上述迭代算法的運行過程如下圖所示： coutMultiply Ai,s[i][j]。 Traceback(i,s[i][j],s)。 } } } } return m[1][L1]。 if(tm[i][j]) { m[i][j] = t。 kj。//將鏈ij劃分為A(i) * ( A[i+1:j] ) s[i][j] = i。 i++)//nr+1為最后一個r鏈的前邊界 { int j = i+r1。 r++) //r為當(dāng)前計算的鏈長（子問題規(guī)模） { for(int i=1。 } for(int r=2。 i=n。 return 0。 cout矩陣最優(yōu)計算次序為：endl。 m[i] = new int[L]。iL。 int **m = new int *[L]。//構(gòu)造最優(yōu)解int main(){ int p[L]={30,35,15,5,10,20,25}。int MatrixChain(int n,int **m,int **s,int *p)。//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。在計算過程中，保存已解決的子問題的答案。 動態(tài)規(guī)劃迭代實現(xiàn)否則與直接遞歸算法一樣遞歸計算，并將計算結(jié)果存入m[i][j]中返回。}算法通過數(shù)組m記錄子問題的最優(yōu)值，m初始化為0，表明相應(yīng)的子問題還沒有被計算。 coutMultiply Ai,s[i][j]。 Traceback(i,s[i][j],s)。 return u。 s[i][j] = k。 k++) { int t = LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + p[i1]*p[k]*p[j]。 for(int k=i+1。 } int u = LookupChain(i,i,m,s,p) + LookupCha
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1