矩陣連乘問題

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

m[i][k]

m[k

1][j]

pi

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

k記

s[i][j],

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

m[i][j]

后，可遞歸地由可以證明該算法的計算時間

T(n)

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

n=1T(n)

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