動(dòng)態(tài)規(guī)劃與矩陣連乘

1、 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn):理解動(dòng)態(tài)規(guī)劃算法的概念。掌握動(dòng)態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。（1）矩陣連乘問題；（2）最長(zhǎng)公共子序列；（3）圖的任意兩點(diǎn)間的最短距離（4）背包問題；問題 1.問題求解的分類：求任意解，求最優(yōu)解 （工作量哪個(gè)大？） 求最優(yōu)解的算法大都具有指數(shù)級(jí)的復(fù)雜度，因此好的方法很重要，有一種多項(xiàng)式時(shí)間的復(fù)雜度算法-動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法與分治法類似，

2、其基本思想是將待求解問題分解成若干個(gè)子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4

3、)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)常用名詞： 狀態(tài)：對(duì)于一個(gè)問題，所有可能到達(dá)的情況 狀態(tài)變量：對(duì)每個(gè)狀態(tài)K關(guān)聯(lián)一個(gè)狀態(tài)變量Sk ， 它的值表示狀態(tài)K所對(duì)應(yīng)的問題的當(dāng)前解值。 決策：是一種選擇，對(duì)于每一個(gè)狀態(tài)，都可以選擇一種方法，從而到達(dá)下一個(gè)狀態(tài) 決策變量：在狀態(tài)K下的決策變量Dk的值表示狀態(tài)K當(dāng)前所做出的決策 策略：一個(gè)決策 的集合，滿足某些最優(yōu)條件的策略稱為最優(yōu)策略 狀態(tài)轉(zhuǎn)移函數(shù)(T)：從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，可以依據(jù)一定的規(guī)則來前進(jìn)，我們用一個(gè)函數(shù)T來描述這樣的規(guī)劃，它將狀態(tài)I和決策變量Dij映射到另一個(gè)狀態(tài)j 狀態(tài)轉(zhuǎn)移方程： 注

4、意：有限個(gè)狀態(tài)變量，每個(gè)狀態(tài)變量取有限個(gè)不同的值。這樣，總的狀態(tài)個(gè)數(shù)為有限。 畢竟：人類只能處理有限的事物（有限時(shí)間）最優(yōu)化原理： 1951年，美國(guó)數(shù)學(xué)家R.Bellman等人，提出 了最優(yōu)化原理( Principle of Optimality) 一個(gè)最大優(yōu)策略的子策略，對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的數(shù)學(xué)描述： 最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。 可用動(dòng)態(tài)規(guī)劃來解決的問題，要符合如個(gè)條件： 1.滿足最優(yōu)化原理 2.狀態(tài)滿足無后效性 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計(jì)算出最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。動(dòng)態(tài)規(guī)劃的兩種不同的思維法： 逆向

5、思維法 正向思維法（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積 是完全加括號(hào)的，則 可 表示為2個(gè)完全加括號(hào)的矩陣連乘積 和 的乘積并加括號(hào)，即 AABC)(BCADCBA , , ,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500完全加括號(hào)的矩陣連乘積可遞歸地定義為：設(shè)有四個(gè)矩陣 ，它們的維數(shù)分別是：總共有五中完全加括號(hào)的方式回顧矩陣相乘： 單個(gè)乘法次數(shù)：n 單個(gè)加法次數(shù)：n-1 總的乘法次數(shù)：m*n*l 總的加法次數(shù)：m*(n-1)*lmlmmllnlnnllmnmmnnl

6、mlnnmzzzzzzzzzyyyyyyyyyxxxxxxxxxZYX,.,.,.,.,.,.,.,.,.,.,.,.,212222111211212222111211212222111211nkjkkijibaz1,給定n個(gè)矩陣 ， 其中 與 是可乘的， ?？疾爝@n個(gè)矩陣的連乘積 由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,.,21nAAAiA1iA1,.,2 , 1ninAAA.21 給定n個(gè)矩陣A1,

7、A2,An，其中Ai與Ai+1是可乘的，i=1，2，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。u窮舉法窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 算法復(fù)雜度分析：算法復(fù)雜度分析：對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnku動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃將矩陣連乘積 簡(jiǎn)記為Ai:j ，這里ij jii

8、AAA.1考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號(hào)方式為).)(.(211jkkkiiAAAAAA計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上Ai:k和Ak+1:j相乘的計(jì)算量特征：計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n 當(dāng)i=j時(shí)，A

9、i:j=Ai，因此，mi,i=0，i=1,2,n當(dāng)ij時(shí)，可以遞歸地定義mi,j為：jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種可能kij 對(duì)于1ijn不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問題。因此，不同子問題的個(gè)數(shù)最多只有由此可見，在遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算多次許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查

10、一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法)(22nnn舉例：設(shè)有以下四個(gè)矩陣m12=35*40*20=28000m23=40*20*10=8000m34=20*10*15=3000m13=minm12+35*20*10,m23+35*40*10 =min28000+7000,8000+14000 =22000同樣有：m24=14000m14=minm24+35*40*15,m12+m34+35*20*15,m13+35*10*15 =min14000+21000,28000+3000+10500,22000+5250 =min35000,41500,27250=27250最佳乘法

11、順序?yàn)? (A1(A2A3)A4)1510,41020,32040,24035,1,jijijijiaAaAaAaAvoid MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*

12、pk*pj; if (t mij) mij = t; sij = k; 算法復(fù)雜度分析：算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。A1A2A3A4A5A63035 3515 155 510 1020 20251137520103504375 55 4271252053510002625 54 321300020153525000 53 22min 52541531521pppmmpppmmpppmmm矩陣連乘計(jì)算次序問

13、題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。同一個(gè)問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低）遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)子問題的重疊性質(zhì)。動(dòng)態(tài)規(guī)