矩陣連乘問題《算法分析與設計》

1、設計性實驗報告 課程名稱：算法分析與設計實驗題目：矩陣連乘問題組 長：成 員 一：成 員 二：成 員 三：系 別：數(shù)學與計算機科學系專業(yè)班級：指導教師：實驗日期： 一、實驗目的和要求實驗目的熟悉動態(tài)規(guī)劃算法設計思想和設計步驟，掌握基本的程序設計方法，培養(yǎng)學生用計算機解決實際問題的能力。實驗要求1、根據(jù)實驗內(nèi)容，認真編寫源程序代碼、上機調(diào)試程序，書寫實驗報告。2、本實驗項目考察學生對教材中核心知識的掌握程度和解決實際問題的能力。3、實驗項目可以采用集中與分散實驗相結(jié)合的方式進行，學生利用平時實驗課時間和課外時間進行實驗，要求在學期末形成完整的項目程序設計報告。二、實驗內(nèi)容提要矩陣連乘問題給定n個

2、矩陣A1,A2,An， 其中，Ai與Ai+1是可乘的，i=1,2，n-1?？疾檫@n個矩陣的連乘積A1,A2,An。由于矩陣乘法滿足結(jié)合律，故計算矩陣的連乘積可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調(diào)用2個矩陣相乘的標準算法計算出矩陣連乘積。完全加括號的矩陣連乘積可遞歸地定義為：（1）單個矩陣是完全加括號的；（2）矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=（BC）。三、實驗步驟下面考慮矩陣連乘積的最優(yōu)計算次序問題的動態(tài)規(guī)劃方法。（1）分析

3、最優(yōu)解的結(jié)構(gòu)（最優(yōu)子結(jié)構(gòu)性質(zhì)） 設計求解具體問題的動態(tài)規(guī)劃算法的第一步是刻畫該問題的最優(yōu)解結(jié)構(gòu)特征。對于矩陣乘積的最優(yōu)計算次序問題也不例外。首先，為方便起見，降矩陣乘積Ai Ai+1Aj簡記為Ai:j。考查計算A1：n的最優(yōu)計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，1=kn,則其相應的完全加括號方式為（A1Ak）（Ak+1An）即依此次序，先計算A1：k和 Ak+1：n，然后將計算結(jié)果相乘得到A1：n。依此計算次序，總計算量為A1：k的計算量加上Ak+1:n的計算量，再加上A1:k和Ak+1:n相乘的計算量。這個問題的一個關鍵特征是：計算A1:n的最優(yōu)次序所包含的計算矩陣子

4、鏈A1:k和Ak+1:n的次序也是最優(yōu)的。事實上，若有一個計算A1:k的次序需要的計算量更少，則用此次序替換原來計算A1:k的次序，得到的計算A1:n的計算量將比按最優(yōu)次序計算所需計算量更少，這是一個矛盾。同理可知，計算A1:n的最優(yōu)次序所包含的計算矩陣子鏈Ak+1:n的次序也是最優(yōu)的。因此，矩陣連乘積計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。（2）建立遞歸關系對于矩陣連乘積的最優(yōu)計算次序問題，設計算Ai:j,1=i=n,所需的最少數(shù)乘次數(shù)為mij,則原問題的最優(yōu)值為嗎m1n。當i=j時，Ai:j=Ai為

5、單一矩陣，無需計算，因此，mii=0,i=1,2,.,n 。當ij時，可利用最優(yōu)子結(jié)構(gòu)性質(zhì)計算mij。事實上，若計算Ai:j的最優(yōu)次序在Ak和Ak+1之間斷開，i=kj,則mij=mik+mk+1j+pi-1*pk*pj。由于在計算時并不知道斷開點k的位置，所以k還未定。不過k的位置只有j-i種可能，即k屬于i，i+1，.，j-1。因此，k是這j-i個位置中使計算量達到最小的那個位置。從而mij可以遞歸地定義為當i=j，mij=0;當ij，mij=minmik+mk+1j+pi-1*pk*pj,i=kjmij給出了最優(yōu)值，即計算Ai:j所需的最少數(shù)乘次數(shù)。同時還確定了計算Ai:j的最優(yōu)次序中的

6、斷開位置k，也就是說，對于這個k有mij=mik+mk+1j+pi-1*pk*pj若將對應于mij的斷開位置k記為sij,在計算出最優(yōu)值mij后，可遞歸地有sij構(gòu)造出相應的最優(yōu)解。（3）計算最優(yōu)值根據(jù)計算mij的遞歸式，容易寫一個遞歸算法計算min。.稍后將看到，簡單的遞歸計算將耗費指數(shù)計算時間。注意到在遞歸計算過程中，不同的子問題個數(shù)只有（n2）個。事實上，對于1=i=j=n不同的有序?qū)Γ╥,j）對應于不同的子問題。因此，不同的子問題的個數(shù)最多只有n*(n-1)/2+n=（n2）個。由此可見，在遞歸計算時，許多子問題被重復計算多次。這也是該問題可以動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃

7、算法解此問題，可依據(jù)其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面計算時只需簡單查一下，從而避免大量重復計算，最終得到多項式時間的算法。下面給出的動態(tài)規(guī)劃算法matrixChain中，輸入?yún)?shù)p0,p1,p2.,pn存儲于數(shù)組p中。算法除了輸出最優(yōu)值數(shù)組m外還輸出記錄最優(yōu)斷開位置的數(shù)組s。算法matrixChain，首先計算出mii=0,i=1,2,.,n。然后，根據(jù)遞歸式，按矩陣鏈長遞增的方式依次計算mii+1,i=1,2,.,n-1,(矩陣鏈長度為2)；mii+2,i=1,2,.n-2,(矩陣鏈長為3)；.。在計算mij時，只用到已計

8、算出的mik和mk+1j。（4）構(gòu)造最優(yōu)解動態(tài)規(guī)劃算法的第四步屎構(gòu)造問題的最優(yōu)解。算法matrixChain只是計算出了最優(yōu)值，并未給出最優(yōu)解。也就是說，通過算法matrixChain的計算，只知道最少數(shù)乘次數(shù)，還不知道具體應按什么次序做矩陣乘法才能達到最少的數(shù)乘次數(shù)。事實上，算法matrixChain已記錄了構(gòu)造最優(yōu)解所需要的全部信息。Sij中的數(shù)k表明計算矩陣鏈Ai:j的最佳方式應在矩陣Ak和Ak+1之間斷開，即最優(yōu)的加括號方式應為（Ai:k）（Ak+1:j）。因此，從是1n記錄的信息可知計算A1:n的最優(yōu)加括號方式為（A1:s1n）（As1n+1:n）.而A1：s1n的最優(yōu)加括號方式為（

9、A1:s1s1n）(As1s1n+1:s1s1n).同理可知確定As1n+1:n的最優(yōu)加括號方式為是ss1n+1n出斷開，照此遞推下去，最終可以確定A1:n的最優(yōu)完全加括號方式，即構(gòu)造出問題的一個最優(yōu)解。下面的算法traceback按算法matrixChain計算出的斷點矩陣s指示的加括號方式輸出計算Ai:j的最優(yōu)計算次序。void traceback (int i,int j,int sN+1)/用遞歸來實現(xiàn)輸出得到最小數(shù)乘次數(shù)的表達式if (i=j)printf (A%d,i);elseprintf (); traceback (i,sij,s); traceback(sij+1,j,s)

10、; printf ();要輸出A1:n的最優(yōu)計算次序只要調(diào)用上面的traceback（1,n,s）即可。對于上面所舉得例子，通過調(diào)用算法traceback（1,6，s），可輸出最優(yōu)計算次序(A1(A2A3)(A4A5)A6)。四、實驗實施的條件計算機機房，微型計算機，Visual C+ 6.0軟件或C#。五、程序代碼下面是算法的完整程序代碼。版本：c語言版本； 開發(fā)人員：王東亮、唐浩、陶勝、趙強#include #define N 100/定義最大連乘的矩陣個數(shù)為100個void matrixChain (int p,int mN+1N+1,int sN+1N+1)/*用mij二維數(shù)組來存儲A

11、i*.Aj的最小數(shù)乘次數(shù)，用sij來存儲使Ai.Aj獲得最小數(shù)乘次數(shù)對應的斷開位置k，需要注意的是此處的N+1非常關鍵，雖然只用到的行列下標只從1到N但是下標0對應的元素默認也屬于該數(shù)組，所以數(shù)組的長度就應該為N+1*/int n=N;/定義m,s數(shù)組的都是n*n的，不用行列下標為0的元素，但包括在該數(shù)組中for (int i=1;i=n;i+)mii=0; /*將矩陣m的對角線位置上元素全部置0，此時應是r=1的情況，表示先計算第一層對角線上個元素的值*/for (int r=2;r=n;r+)/r表示斜對角線的層數(shù)，從2取到nfor (int i=1;i=n-r+1;i+)/i表示計算第r

12、層斜對角線上第i行元素的值int j=i+r-1;/j表示當斜對角線層數(shù)為r，行下標為i時的列下標mij=mi+1j+pi-1*pi*pj;/計算當斷開位置為i時對應的數(shù)乘次數(shù)sij=i;/斷開位置為ifor (int k=i+1;kj;k+)int t=mik+mk+1j+pi-1*pk*pj;/*計算當斷開位置k為從i到j（不包括i和j）的所有取值對應的(Ai*.*Ak)*(Ak+1*.Aj)的數(shù)乘次數(shù)*/if (tmij)mij=t;/將Ai*.Aj的最小數(shù)乘次數(shù)存入mijsij=k;/將對應的斷開位置k存入sijvoid traceback (int i,int j,int sN+1)

13、/用遞歸來實現(xiàn)輸出得到最小數(shù)乘次數(shù)的表達式if (i=j)printf (A%d,i);elseprintf (); traceback (i,sij,s); traceback(sij+1,j,s); printf ();void main ()int n;/用來存儲矩陣的個數(shù)int q2*N;/*用q數(shù)組來存儲最原始的輸入（各矩陣的行和列），主要目的是為了檢驗這N個矩陣是否滿足連乘的條件*/int pN+1,flag=1;/*用pi-1,pi數(shù)組來存儲A的階數(shù)，flag用來判斷這N個矩陣是否滿足連乘*/int mN+1N+1;/ 用mij二維數(shù)組來存儲Ai*.Aj的最小數(shù)乘次數(shù)int sN

14、+1N+1;/ 用sij來存儲使Ai.Aj獲得最小數(shù)乘次數(shù)對應的斷開位置kprintf (請輸入矩陣的個數(shù)（小于100）:);scanf (%d,&n);for (int i=0;i=2*n-1;i+)/各矩陣的階數(shù)的輸入先存入數(shù)組q中接受檢驗if (i%2=0)printf (*n);printf (*請輸入A%d的行:,(i/2)+1);elseprintf (列*:); scanf (%d,&qi);for (i=1;i=2*n-2;i+)/矩陣連乘條件的檢驗 if (i%2!=0&qi!=qi+1)flag=0;break;for (int j=1;j=n-1;j+)pj=q2*j;i

15、f (flag!=0) p0=q0; pn=q2*n-1; matrixChain (p,m,s); printf (式子如下:n); traceback(1,n,s); printf (n); printf (最小數(shù)乘次數(shù)為%dn,m1n);elseprintf (這%d個矩陣不能連乘!n,n);實驗結(jié)果：一、輸入正確的情況：二、輸入有誤的情況：六、編程體會經(jīng)過了幾天的連續(xù)研究，終于小有收獲，也漸漸理解了動態(tài)規(guī)劃的基本思想，動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)

16、分解得到的子問題往往不是相互獨立的。若用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要耗費指數(shù)時間。然而，不同子問題的數(shù)目常常只有多項式量級。在分治法求解時，有些子問題被重復計算了多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。為了達到這個目的，可以用一個表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃的基本思想。具體的動態(tài)規(guī)劃算法是多種多樣的，但它們具有相同的填表格式。動態(tài)規(guī)劃算法適用于解最優(yōu)化問題。通?？梢园匆韵虏襟E設計動態(tài)規(guī)劃算法：

17、（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（2）遞歸地定義最優(yōu)值；（3）以自底向上的方式計算出最優(yōu)值；（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。雖然已經(jīng)了解了動態(tài)規(guī)劃算法的基本思想，而且也參考了書上的算法，但是實際的情況卻并不是那么順利，我按照書上編寫程序之后，發(fā)現(xiàn)有很多邏輯錯誤，應該是編寫環(huán)境不同，所以出現(xiàn)了一系列的問題，最后經(jīng)過自己的多番研究發(fā)現(xiàn)了許多c語言有許多默認的規(guī)則：就拿數(shù)組來講，在計算數(shù)組m和數(shù)組s時，雖然我們不用到下標為零的元素，所以我一開始定義用長度為N*N的m數(shù)組和s數(shù)組來分別存儲矩陣的最小數(shù)乘次數(shù)和其對應的斷開位置，但經(jīng)過多次調(diào)試之后，發(fā)現(xiàn)總是在求m*N和s*N時就會出錯，后來才知道c語言的默認規(guī)則：不管我們用不用數(shù)組的零下標元素，下標為零的元素都默認在該數(shù)組中，因此，必須把m和s數(shù)組的行列長度都必須加一才行，經(jīng)過這次程序設計之后，我懂得