動(dòng)態(tài)規(guī)劃矩陣連乘算法-文庫(kù)吧
2025-07-07 00:49 本頁(yè)面
【正文】 即最優(yōu)的加括號(hào)方式應(yīng)為(A[i:k])(A[k+1:j)。因此，從s[1][n]記錄的信息可知計(jì)算A[1:n]的最優(yōu)加括號(hào)方式為(A[1:s[1][n]])(A[s[1][n]+1:n])，進(jìn)一步遞推，A[1:s[1][n]]的最優(yōu)加括號(hào)方式為(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]])。同理可以確定A[s[1][n]+1:n]的最優(yōu)加括號(hào)方式在s[s[1][n]+1][n]處斷開(kāi)...照此遞推下去，最終可以確定A[1:n]的最優(yōu)完全加括號(hào)方式，及構(gòu)造出問(wèn)題的一個(gè)最優(yōu)解。 窮舉法 列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下： 以上遞推關(guān)系說(shuō)明，P(n)是隨n的增長(zhǎng)呈指數(shù)增長(zhǎng)的。因此，窮舉法不是一個(gè)多項(xiàng)式時(shí)間復(fù)雜度算法。 重疊遞歸 從以上遞推關(guān)系和構(gòu)造最優(yōu)解思路出發(fā)，即可寫(xiě)出有子問(wèn)題重疊性的遞歸代碼實(shí)現(xiàn)：//3d11 重疊子問(wèn)題的遞歸最優(yōu)解//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。 const int L = 7。int RecurMatrixChain(int i,int j,int **s,int *p)。//遞歸求最優(yōu)解void Traceback(int i,int j,int **s)。//構(gòu)造最優(yōu)解int main(){ int p[L]={30,35,15,5,10,20,25}。 int **s = new int *[L]。 for(int i=0。iL。i++) { s[i] = new int[L]。 } cout矩陣的最少計(jì)算次數(shù)為：RecurMatrixChain(1,6,s,p)endl。 cout矩陣最優(yōu)計(jì)算次序?yàn)椋篹ndl。 Traceback(1,6,s)。 return 0。}int RecurMatrixChain(int i,int j,int **s,int *p){ if(i==j) return 0。 int u = RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+p[i1]*p[i]*p[j]。 s[i][j] = i。 for(int k=i+1。 kj。 k++) { int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + p[i1]*p[k]*p[j]。 if(tu) { u=t。 s[i][j]=k。 } } return u。}
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1