動態(tài)規(guī)劃矩陣連乘

實驗三：動態(tài)規(guī)劃法【實驗?zāi)康摹繎?yīng)用動態(tài)規(guī)劃算法思想求解矩陣連乘的順序問題?！緦嶒炐再|(zhì)】驗證性實驗?！緦嶒炓蟆繎?yīng)用動態(tài)規(guī)劃算法的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)求解此問題。分析動態(tài)規(guī)劃算法的基本思想，應(yīng)用動態(tài)規(guī)劃策略寫出算法及相應(yīng)的程序，求解此題。要讀懂讀透A[i,j]，A[1,n]=A[1,k]×A[k+1,n]，m[i][j]，s[i][j]各式所表達的含義并正確加以應(yīng)用。m[i][j]的遞歸定義：0（i=j）m[i][j]=min{m[i][k]＋m[k+1][j]+ni-1nknj（i<j）要求完成：⑴算法描述⑵寫出程序代碼⑶完成調(diào)試⑷進行過程與結(jié)果分析?！緦嶒瀮?nèi)容】對于下列所描述的問題，給出相應(yīng)的算法描述，并完成程序?qū)崿F(xiàn)與時間復(fù)雜度的分析。該問題描述為：一般地，考慮矩陣A1，A2，…，An的連乘積，它們的維數(shù)分別為d0,d1,…,dn,即Ai的維數(shù)為di-1×di(1≤i≤n)。確定這n個矩陣的乘積結(jié)合次序，使所需的總乘法次數(shù)最少。對應(yīng)于乘法次數(shù)最少的乘積結(jié)合次序為這n個矩陣的最優(yōu)連乘積次序。按給定的一組測試數(shù)據(jù)對根據(jù)算法設(shè)計的程序進行調(diào)試：6個矩陣連乘積A=A1×A2×A3×A4×A5×A6，各矩陣的維數(shù)分別為：A1：10×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。完成測試?！菊{(diào)試分析和心得體會】運行依算法寫出的程序并分析算法實現(xiàn)的時間復(fù)雜度情況。#include<iostream.h>#include<iomanip.h>classMatrixChain{public: MatrixChain(intmSize,int*q);//構(gòu)造函數(shù) ~MatrixChain(){} //析構(gòu)函數(shù) intMChain(); //動態(tài)規(guī)劃法求解// intLookupChain(); //備忘錄法 voidTraceback(); //構(gòu)造最優(yōu)解的公有函數(shù) voiddisplay(); //顯示private: voidTraceback(inti,intj); //構(gòu)造最優(yōu)解的私有遞歸// intLookupChain(inti,intj); //備忘錄的私有遞歸 int*p,**m,**s,n;};MatrixChain::MatrixChain(intmSize,int*q){ n=mSize; p=q; m=newint*[10];//二維數(shù)組初始化 for(inti=0;i<10;i++)m[i]=newint[10]; s=newint*[10]; //二維數(shù)組初始化 for(intj=0;j<10;j++)s[j]=newint[10];}intMatrixChain::MChain()//求A[0:N-1]的最優(yōu)解{ for(inti=0;i<n;i++) { m[i][i]=0;//初始化 s[i][i]=0; } for(intr=2;r<=n;r++) for(inti=0;i<=n-r;i++) { intj=i+r-1; m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for(intk=i+1;k<j;k++) { intt=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]; if(t<m[i][j]) { m[i][j]=t; s[i][j]=k; } } } returnm[0][n-1];}voidMatrixChain::Traceback(inti,intj){ if(i==j) { cout<<"A"<<i; return; } if(i<s[i][j]) cout<<"("; Traceback(i,s[i][j]); if(i<s[i][j]) cout<<")"; if(s[i][j]+1<j) cout<<"("; Traceback(s[i][j]+1,j); if(s[i][j]+1<j) cout<<")";}voidMatrixChain::Traceback(){ cout<<"("; Traceback(0,n-1);//遞歸調(diào)用 cout<<")";}/*intMatrixChain::LookupChain(inti,intj)//備忘錄法實現(xiàn){ if(m[i][j]>0) returnm[i][j]; if(i==j) return0; intu; u=LookupChain(i+1,j)+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for(intk=i+1;k<j;k++) { intt; t=LookupChain(i,k)+LookupChain(k+1,j)+p[i]*p[k+1]*p[j+1]; if(t<u) { u=t; s[i][j]=k; } } m[i][j]=u; returnu;}intMatrixChain::LookupChain(){ returnLookupChain(0,n-1);}*/voidMatrixChain::display(){ cout<<endl<<"矩陣連乘A[i:j]所需的最少數(shù)乘次數(shù)m[i][j]："<<endl; for(inti=0;i<n;i++) { cout<<endl; for(intj=0;j<n;j++) if(j<i) cout<<""; else cout<<m[i][j]<<""; } cout<<endl<<"矩陣連乘A[i:j]所需的最少數(shù)乘次數(shù)斷點s[i][j]："<<endl; for(i=0;i<n;i++) { cout<<endl; for(intj=0;j<n;j++) if(j<i) cout<<""; else cout<<s[i][j]<