動態(tài)規(guī)劃矩陣連乘算法(編輯修改稿)
2024-08-18 00:49 本頁面
【文章內(nèi)容簡介】 void Traceback(int i,int j,int **s){ if(i==j) return。 Traceback(i,s[i][j],s)。 Traceback(s[i][j]+1,j,s)。 coutMultiply Ai,s[i][j]。 cout and A(s[i][j]+1),jendl。}1. 用算法RecurMatrixChain(1,4,s,p)計(jì)算a[1:4]的計(jì)算遞歸樹如下圖所示： 2.3.4. 從上圖可以看出很多子問題被重復(fù)運(yùn)算?？梢宰C明，該算法的計(jì)算時(shí)間T(n)有指數(shù)下界。設(shè)算法中判斷語句和賦值語句為常數(shù)時(shí)間，則由算法的遞歸部分可得關(guān)于T(n)的遞歸不等式：5.6. 用數(shù)學(xué)歸納法可以證明，因此，算法RecurMatrixChain的計(jì)算時(shí)間也隨n指數(shù)增長。7. 備忘錄遞歸算法8. 備忘錄方法用表格保存已解決的子問題答案，在下次需要解決此子問題時(shí)，只要簡單查看該子問題的解答，而不必重新計(jì)算。備忘錄方法為每一個(gè)子問題建立一個(gè)記錄項(xiàng)，初始化時(shí)，該記錄項(xiàng)存入一個(gè)特殊的值，表示該子問題尚未求解。在求解的過程中，對每個(gè)帶求的子問題，首先查看其相應(yīng)的記錄項(xiàng)。若記錄項(xiàng)中存儲的是初始化時(shí)存入的特殊值，則表示該問題是第一次遇到，此時(shí)計(jì)算出該子問題的解，并將其保存在相應(yīng)的記錄項(xiàng)中，以備以后查看。若記錄項(xiàng)中存儲的已不是初始化時(shí)存入的特殊值，則表示該子問題已被計(jì)算過，相應(yīng)的記錄項(xiàng)中存儲的是該子問題的解答。此時(shí)從記錄項(xiàng)中取出該子問題的解答即可，而不必重新計(jì)算。//3d12 矩陣連乘 備忘錄遞歸實(shí)現(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。 const int L = 7。int LookupChain(int i,int j,int **m,int **s,int *p)。int MemoizedMatrixChain(int n,int **m,int **s,int *p)。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]。 int **m = new int *[L]。 for(int i=0。iL。i++) { s[i] = new int[L]。 m[i] = new int[L]。 } cout矩陣的最少計(jì)算次數(shù)為：MemoizedMatrixChain(6,m,s,p)endl。 cout矩陣最優(yōu)計(jì)算次序?yàn)椋篹ndl。 Traceback(1,6,s)。 return 0。}int MemoizedMatrixChain(int n,int **m,int **s,int *p){ for(int i=1。 i=n。 i++) { for(int j=1。 j=n。 j++) { m[i][j]=0。 } } re
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1