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

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）重疊子問(wèn)題性質(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)解。通過(guò)應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。（1）最短路徑問(wèn)題（2）最長(zhǎng)公共子序列；（3）矩陣連乘問(wèn)題（4）圖的任意兩點(diǎn)間的最短距離（5）流動(dòng)推銷員問(wèn)題（6）背包問(wèn)題（7）整數(shù)規(guī)劃問(wèn)題（8）流水作業(yè)調(diào)度動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題nT(n/2)T(n/2)T(n/2)T(n/2)T

2、(n)=但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(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)如果能夠保存已解決的子問(wèn)題的答案，而在需要時(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)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)問(wèn)題

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

4、，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：110)2() 1(11)(nnnnFnFnF簡(jiǎn)單例子1：Fibonacci序列第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n =3n顯然有：T(n)=f(n)，即求f(n) 的時(shí)間是f(n)，n而f(n)(n), =1.618.n用自上而下的方法用的是指數(shù)時(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 時(shí)間復(fù)雜度為：O(n),空間復(fù)雜度為O(1);n而用遞歸的自上到下的方法的空間復(fù)雜度為0.n即：用O(1)的空間，把復(fù)雜度從指數(shù)級(jí)降到線性。求二項(xiàng)式系數(shù)(n,k)n容易證明，求(n,k)的時(shí)間復(fù)雜度為指數(shù)級(jí)。n可以用楊輝三角形的方法，求出(n,k)，時(shí)間復(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)：對(duì)于一個(gè)問(wèn)題，所有可能到達(dá)的情況n狀態(tài)變量：對(duì)每個(gè)狀態(tài)K關(guān)聯(lián)一個(gè)狀態(tài)變量Sk ，n它的值表示狀態(tài)K所對(duì)應(yīng)的問(wèn)題的當(dāng)前解值。n決策：是一種選擇，對(duì)于每一個(gè)狀態(tài)，都可以選擇一種方法，從而到達(dá)下一個(gè)狀態(tài)n決策變量：在狀態(tài)K下的決策變量Dk的值表示狀態(tài)K當(dāng)前所做出的決策n策略：一個(gè)決策 的集合，滿足某些最優(yōu)條件的策略稱為最優(yōu)策略n狀態(tài)轉(zhuǎn)移函數(shù)(T)：從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，可以依據(jù)一定的規(guī)則來(lái)前進(jìn)，我們用一個(gè)函數(shù)T來(lái)描述這樣的規(guī)劃，它將狀態(tài)I和決策變量Dij映射到另一個(gè)狀態(tài)j n狀態(tài)轉(zhuǎn)移方程：n注意：有限個(gè)狀態(tài)變量，每個(gè)狀態(tài)變量取有限個(gè)不同的值。這樣，總的

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

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

10、加法n 從48條中，找到最短的一條，要進(jìn)行47次比較。動(dòng)態(tài)規(guī)劃法：nf(Ai)表示從 Ai點(diǎn)到終點(diǎn)站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)對(duì)坐標(biāo)系 ，從原點(diǎn)（0，0）到（M，N）的最短的路經(jīng)?n蠻力法（窮舉法）：n求出每條路徑的長(zhǎng)度，通過(guò)比較，找出最短的一條路徑。n問(wèn)