矩陣連乘問題

目錄：矩陣連乘問題：描述矩陣連乘問題解析矩陣連乘問題以及對(duì)遞歸式的推導(dǎo)1）直接遞歸思路2）備忘錄思路3）動(dòng)向規(guī)劃思路偽代碼的方式描述算法：1）直接遞歸算法2）備忘錄算法3）動(dòng)向規(guī)劃算法把算法變換成程序?qū)崿F(xiàn)的過程及結(jié)果1）直接遞歸算法程序2）備忘錄算法程序3）動(dòng)向規(guī)劃算法程序描述矩陣連乘問題：給定n個(gè)矩陣{AAA}，其中AA,n-1。察看這n個(gè)矩陣1,2,ni和i1是可乘的，i=1,2,的連乘積A1,A2,An。由于矩陣乘法擁有結(jié)合律，故計(jì)算矩陣的連乘積可以有好多不相同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完好確定，也就是說連乘積已完好加括號(hào)，則可依次序?qū)掖握{(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。完好加括號(hào)的矩陣連乘可遞歸地定義為：（1）單個(gè)矩陣是完好加括號(hào)的；（2）矩陣連乘積A是完好加括號(hào)的，則A可表示為2個(gè)完好加括號(hào)的矩陣連乘B和C的乘積并加括號(hào)，即A=（BC）。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個(gè)p×q的矩陣，B是一個(gè)q×r的矩陣，那么C=A×B就是一個(gè)p×r矩陣。它的計(jì)算是三重循環(huán)的，計(jì)算量是pqr。若是加括號(hào)后矩陣的量是不相同的，因此我們的問題就是要談?wù)撊绾谓o連乘的矩陣加括號(hào)才能使矩陣的計(jì)算量最少。窮舉找尋法：對(duì)于n個(gè)矩陣的連乘積，設(shè)有不相同的計(jì)算次序P(n)。由于可以先在第k個(gè)和第k+1個(gè)矩陣之間將原矩陣序列分為兩個(gè)矩陣子序列，k=1,2,...,n-1；爾后分別對(duì)這兩個(gè)矩陣子序列完好加括號(hào)；最后對(duì)所得的結(jié)果加括號(hào)，獲取原矩陣序列的一種完好加括號(hào)方式。由此可得P(n)的遞歸式以下：n=1P（n）=n1P(k)P(nk)n>1k1解此遞歸方程可得，P(n)=C(n-1),而C(n)是一個(gè)指數(shù)增添的函數(shù)。因此窮舉找尋法不是一個(gè)有效的算法。以下將用三種方法來解決矩陣連乘問題的最優(yōu)加括號(hào)方式以及最優(yōu)解。解析矩陣連乘問題以及對(duì)遞歸式的推導(dǎo)將矩陣連乘積Ai,Ai1,Aj簡(jiǎn)記為A[i:j]。察看計(jì)算A[1:n]的最優(yōu)計(jì)算次序。這個(gè)問題的一個(gè)要點(diǎn)特色是：計(jì)算A[1:n]的最優(yōu)次序包含的計(jì)算矩陣子鏈A[1:k]和A[k+1:n]的次序也是最優(yōu)的。這是由于：定義矩陣A的維數(shù)為p×pi,則A[i:k]的計(jì)算次數(shù)為p×p，ii-1i-1kA[k+1,j]的計(jì)算次數(shù)為pk×pj，而這兩個(gè)總的矩陣最后相乘時(shí)的計(jì)算量是固定的，為pi-1×p×p。因此，矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最kj優(yōu)子構(gòu)造性質(zhì)。（1）、直接遞歸的思路：記計(jì)算A[i:j]，1≤i≤j≤n，所需最少許乘次數(shù)為m[i][j],則原問題的最優(yōu)秀為m[1][n]。由解析得知：m[i][j]可以遞歸的定義為：0min{[][]i=j1][]}m[i][j]=[mikmkji1kji<jikjpppm[i][j]給出了最優(yōu)值，即計(jì)算A[i][j]所需的最少許乘次數(shù)。同時(shí)還確定了計(jì)算A[i：j]的最優(yōu)次序中的斷開地址k，也就是說，對(duì)于這個(gè)k有m[i][j]=

m[i][k]

m[k

1][j]

pi

1pkpj若將對(duì)應(yīng)于m[i][j]的斷開地址s[i][j]構(gòu)造出相應(yīng)的最優(yōu)解。

k記

s[i][j],

在計(jì)算出最優(yōu)值

m[i][j]

后，可遞歸地由可以證明該算法的計(jì)算時(shí)間

T(n)

有指數(shù)下界，由算法的遞歸部分可得：O(1)

n=1T(n)

≥n11+(T(k)T(nk)1)n>1k1因此，當(dāng)n>1時(shí)，T(n)≥n+2n1T(k)k1據(jù)此，可用數(shù)學(xué)歸納法證明T(n)≥2n-1=(2n)。直接遞歸法的計(jì)算時(shí)間隨n的增添指數(shù)增長(zhǎng)。（2）、備忘錄方法的思路：備忘錄方法為每個(gè)子問題建立一個(gè)記錄項(xiàng)，初始化時(shí)，該記錄項(xiàng)存入一個(gè)特其他值，表示該問題還沒有求解。在求解過程中，對(duì)每個(gè)待求的子問題，第一查察其相應(yīng)的記錄項(xiàng)。若記錄項(xiàng)中儲(chǔ)藏的是初始化時(shí)存入的特別值，則表示該問題第一次遇到，此時(shí)計(jì)算出該子問題的解，并保存在相應(yīng)的記錄項(xiàng)中，以備今后查察。若記錄項(xiàng)中儲(chǔ)藏的不是初始化存入的特別值，（比方初始化為-1，解答后賦值為0），則表示該問題已被計(jì)算過，其相應(yīng)的記錄項(xiàng)中儲(chǔ)藏的應(yīng)該是該子問題的解答。此時(shí)，只要從記錄相中取出該子問題的解答即可，而不用重新計(jì)算。備忘錄方法的計(jì)算量：由于是要計(jì)算m[i][j],因此只要從n個(gè)變量中任意選出2個(gè)分別作為i，j，則共有Cn2種選法，即有Cn2個(gè)子問題；當(dāng)i=j時(shí)有n種選法，因此總的子問題就為：Cn2+n=n(n1)個(gè)。每填入一個(gè)記錄項(xiàng)，就要開銷O（n）的時(shí)間，因此備忘錄方法的時(shí)2間復(fù)雜度為O(n3)。（3）、動(dòng)向規(guī)劃方法的思路：（以6個(gè)矩陣相乘為例）m[i][j]123456102x03xx04xxx05xxxx06xxxxx0注意，在m[i][j]中，若是i>j是沒有意義的，因此在表格中都即為x；而且，若是i=j，則代表單個(gè)矩陣，因此m[i][i]=1.依照直接遞歸的方法的思路，若是要求m[i][j],就必定要求m[i][k]和m[k+1][j],依照m[i][j]的矩陣，則若是要求解m[1][2]，則需要知道m(xù)[1][1]和m[1][2]；若是要求解m[1][3]，則要知道m(xù)[1][1]、m[1][2]和m[1][1]和m[2][3];以此類推。經(jīng)過此規(guī)律可以總結(jié)出要求某一個(gè)元素，就要知道其左方的所有元素的值和其下方的所有元素的值。m[i][j]123456102x03xx04xxx05xxxx06xxxxx0動(dòng)向規(guī)劃就是依照上圖所畫的形式進(jìn)行求解，從左下方求到右上方。動(dòng)向規(guī)劃算法的計(jì)算量主要取決于程序中對(duì)行、列和加括號(hào)的地址k的三重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1),而三重循環(huán)的總次數(shù)為O(n3)。因此該算法的計(jì)算時(shí)間上界為O(n3)。和備忘錄的算法的時(shí)間復(fù)雜度相同，都比直接遞歸的窮舉找尋法有效得多。偽代碼的方式描述算法：（1）直接遞歸算法：intRecurMatrixChain(inti,intj){if(i==j)return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];intn;忘錄算法"<<endl;cout<<"2.直接遞歸算法"<<endl;cout<<"3.動(dòng)向規(guī)劃算法"<<endl;cout<<"4.重新輸入矩陣"<<endl;cout<<"5.退出程序"<<endl;cout<<endl;cout<<"請(qǐng)輸入選擇的編號(hào)：";cin>>choice;cout<<endl;while(choice!=5){switch(choice){case1:LookupChain(1,n);cout<<"動(dòng)向規(guī)劃算法："<<endl;cout<<"矩陣連乘的最優(yōu)值為："<<m[1][n]<<endl;cout<<"矩陣連乘的最優(yōu)解為：";Traceback(1,n);cout<<endl;break;case2:RecurMatrixChain(0,n);cout<<"動(dòng)向規(guī)劃算法："<<endl;cout<<"矩陣連乘的最優(yōu)值為："<<m[1][n]<<endl;cout<<"矩陣連乘的最優(yōu)解為：";Traceback(1,n);cout<<endl;break;case3:MatrixChain( );cout<<"動(dòng)向規(guī)劃算法："<<endl;cout<<"矩陣連乘的最優(yōu)值為："<<m[1][n]<<endl;cout<<"矩陣連乘的最優(yōu)解為：";Traceback(1,n);cout<<endl;break;case4:gotoL;break;case5:choice=4;break;default:break;}cout<<endl;cout<<"請(qǐng)選擇矩陣連乘的算法:"<<endl;cout<<"1.