《算法分析》7動態(tài)規(guī)劃1分析

1、學(xué)習(xí)要點學(xué)習(xí)要點:理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)掌握設(shè)計動態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。通過應(yīng)用范例學(xué)習(xí)動態(tài)規(guī)劃算法設(shè)計策略。（1）最短路徑問題（2）最長公共子序列；（3）矩陣連乘問題（4）圖的任意兩點間的最短距離（5）流動推銷員問題（6）背包問題（7）整數(shù)規(guī)劃問題（8）流水作業(yè)調(diào)度動態(tài)規(guī)劃算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題nT(n/2)T(n/2)T(n/2)T(n/2)T

2、(n)=但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。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)如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)問題

3、對象n這一強(qiáng)有力的算法設(shè)計技術(shù)，廣泛應(yīng)用于求解組合最優(yōu)化問題。n它不遞歸調(diào)用自身，但問題的基本解通常是用遞歸函數(shù)的形式來說明。n而分治法是直接實現(xiàn)遞推的結(jié)果，往往會導(dǎo)致不止一次的遞歸調(diào)用n動態(tài)規(guī)劃采用自底向上的方式遞推求值，并把中間結(jié)果存儲起來以便以后用來計算所需要求的解。（事實上是采用了空間換時間的算法）n動態(tài)規(guī)劃可以設(shè)計出特別有效的解決許多組合最優(yōu)化問題。n比如：旅行商問題n有n個城市，城市之間有不等長的道路連接，一個旅行商要走遍所有城市，請找到一條最短的步行方法？n用蠻力算法需要O(n!)n用動態(tài)規(guī)劃可以在O(n2 2n)內(nèi)解決。簡單例子1：Fibonacci序列 無窮數(shù)列1，1，2，3

4、，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：110)2() 1(11)(nnnnFnFnF簡單例子1：Fibonacci序列第n個Fibonacci數(shù)可遞歸地計算如下：int fibonacci(int n) if (n =3n顯然有：T(n)=f(n)，即求f(n) 的時間是f(n)，n而f(n)(n), =1.618.n用自上而下的方法用的是指數(shù)時間求出f(n).用自底向上的方法：nint f(int n)n int x=1,y=1,z,j;n for(j=2;j=n;j+) n z=x+y;n x=y;y=z;n n return z;n用自底向上的

5、方法：n 時間復(fù)雜度為：O(n),空間復(fù)雜度為O(1);n而用遞歸的自上到下的方法的空間復(fù)雜度為0.n即：用O(1)的空間，把復(fù)雜度從指數(shù)級降到線性。求二項式系數(shù)(n,k)n容易證明，求(n,k)的時間復(fù)雜度為指數(shù)級。n可以用楊輝三角形的方法，求出(n,k)，時間復(fù)雜度降為O(n 2)，n為什么？空間復(fù)雜度哪？nkknknkknkn0,1110, 1若或楊輝三角形nn=1 1 1nn=2 1 2 1n 1 3 3 1n 1 4 6 4 1n 1 5 10 10 5 1nn=6 1 6 15 20 15 6 1n .nk= 0 1 2 3 4 5 6楊輝三角形nn=1 1 1nn=2 1 2 1

6、n 1 3 3 1n 1 4 6 4 1n 1 5 10 10 5 1nn=6 1 6 15 20 15 6 1n .nk= 0 1 2 3 4 5 6C:nint f(int n,int k)n int x,y,an+1,bn+1;n if (n=0|k0) return 1;n if(k=0|k=n) return 1;n for(x=0;xn+1;x+) ax=bx=0;n a0=1;a1=1;n for(x=1;xn;x+) /* ?*/n a0=b0=1;n for(y=1;y n;y+) /* ?*/n by=ay-1+ay;n n for(y=0;yn+1;y+) ay=by;n

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

8、狀態(tài)個數(shù)為有限。n畢竟：人類只能處理有限的事物（有限時間）最優(yōu)化原理：n1951年，美國數(shù)學(xué)家R.Bellman等人，提出 了最優(yōu)化原理：n 一個最大優(yōu)策略的子策略，對于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。n動態(tài)規(guī)劃思想利用了最優(yōu)化原理。n最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)。使用動態(tài)規(guī)劃算法的條件n可用動態(tài)規(guī)劃來解決的問題，要符合如個條件：n1.滿足最優(yōu)化原理n2.狀態(tài)滿足無后效性n找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。n遞歸地定義最優(yōu)值。n以自底向上的方式計算出最優(yōu)值。n根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。n動態(tài)規(guī)劃的兩種不同的思維法：n逆向思維法n正向思維法最短路徑問題n從A0點出發(fā)，要鋪設(shè)一條管道

9、到A6點。中間必須經(jīng)過5個中間站，每個中間站都有若干個候選站，第一站可以從A1，B1兩地中任選 一個，第二站從A2，B2,C2，D2中任選一個，第三站從A3，B3，C3中任選一個，第四站從A4，B4，C4中任選一個，第五站從A5，B5中任選一個，連接兩地間距離的連線上數(shù)字表示，求總距離最短？A0B1A1D2C2B2A2C3B3A3C4B4A4B5A5A6特征分析n有指定的起點與終點，中間站之間的先后順序是固定的n每個中間站有若干個中間站n最短路徑上的每個點到終點都是最短的窮舉法分析n用窮舉法：n 狀態(tài)空間數(shù)：1*2*3*2*2*2*1=48n 計算48條，每條的包含5個線段，所以要進(jìn)行240次

10、加法n 從48條中，找到最短的一條，要進(jìn)行47次比較。動態(tài)規(guī)劃法：nf(Ai)表示從 Ai點到終點站A6的最短距離n其中：0=i5nf(A5)=4， f(B5)=3nf(A4)=mind(A4,A5)+ f(A5),d(A4,B5)+ f(B5)n =min3+4,5+3n =min7,8n =7nf(B4)= mind(B4,A5)+ f(A5),d(B4,B5)+ f(B5)n =min5+4,2+3=5nf(C4)=9nf(A3)=7nf(B3)=8nf(C3)=8nf(A2)=13nf(B2)=10nf(C2)=9nf(D2)=12nf(A1)=13nf(B1)=16nf(A0)=18A0-18A1-16A1-13A2-12A2-9A2-10A2-13A3-8A3-6A3-7A4-9A4-5A4-7A5-3A5-4A6-0復(fù)雜度分析：(0,0)(m,n)對坐標(biāo)系 ，從原點（0，0）到（M，N）的最短的路經(jīng)?n蠻力法（窮舉法）：n求出每條路徑的長度，通過比較，找出最短的一條路徑。n問