《動態(tài)規(guī)劃算法 算法設(shè)計(jì)》由會員分享，可在線閱讀，更多相關(guān)《動態(tài)規(guī)劃算法 算法設(shè)計(jì)（4頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、動態(tài)規(guī)劃算法 張珊1 （安徽中醫(yī)學(xué)院安徽省合肥市230031） 摘 要：在信息學(xué)中，我們經(jīng)常遇到求最優(yōu)解的問題，這些問題的特點(diǎn)是，只需要求出最優(yōu)解，而不要求 寫出最優(yōu)解的具體情況。為了解決此類問題，我們經(jīng)常會遇到一種有效的算法一一動態(tài)規(guī)劃。使得我們可 以在有限的時(shí)間內(nèi)，求出問題的解，本文介紹一些動態(tài)規(guī)劃的理論知識。 關(guān)鍵詞：動態(tài)規(guī)劃最優(yōu)化原理算法 中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A Dynamic programming algorithm ZHANG Shan1 (Anhui College of Traditional Chinese Medicine,Anhui

2、Province ,Hefei 230031,China) Abstract： In information science, we often encounter the problem of the optimal solution, the nature of these problems is to simply request the optimal solution, without requiring to write the optimal solution specific circumstances. In order to solve such problems, we

3、 often encounter an effective algorithm - dynamic programming. Makes the solution that we can within a limited time, find the problem, this article describes the theory of dynamic programming knowledge. Key words： Dynamic Programming Principle of optimality Algorithm 作者簡介：張珊，女，安徽安慶人，安徽中醫(yī)學(xué)院本科生，

4、學(xué)號09713051,09級醫(yī)軟（1）班 0引言 動態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué) 中使用的，用于求解包含重疊字問題的最優(yōu) 化問題的方法。其基本思想是，將原問題分 解為相似的子問題，在求解的過程中通過子 問題的解求出原問題的解。動態(tài)規(guī)劃的思想 是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科 學(xué)和工程領(lǐng)域。比較著名的應(yīng)用實(shí)例有：求 解最短路徑問題，背包問題，項(xiàng)目管理，網(wǎng) 絡(luò)流優(yōu)化等。 1正文 動態(tài)規(guī)劃算法與分治法類似，其基本思 想也是將待求解問題分解成若干個(gè)子問題。 但是經(jīng)分解得到的子問題往往不是互相獨(dú) 立的。不同子問題的數(shù)目常常只有多項(xiàng)式量 級。在用分治法求解時(shí)，有些子問題被重復(fù) 計(jì)算了許

5、多次。動態(tài)規(guī)劃在查找有很多重疊 字問題的情況的最優(yōu)解時(shí)有效。它將問題重 新組合成子問題。為了避免多次解決這些子 問題，它們的結(jié)果都逐漸被計(jì)算并被保存， 從簡單的問題直到整個(gè)問題都被解決。因 此，動態(tài)規(guī)劃保存遞歸時(shí)的結(jié)果，因而不會 在解決同樣的問題時(shí)花費(fèi)時(shí)間。如果能夠保 存已解決的子問題的答案，而在需要時(shí)再找 出已求得的答案，就可以避免大量重復(fù)計(jì) 算，從而得到多項(xiàng)式時(shí)間算法。找出最優(yōu)解 的性質(zhì)，并刻劃其結(jié)構(gòu)特征。以自底向上的 方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到 的信息，構(gòu)造最優(yōu)解。 1.1最優(yōu)子結(jié)構(gòu) 動態(tài)規(guī)劃只能應(yīng)用于有最優(yōu)子結(jié)構(gòu)的 問題。最優(yōu)子結(jié)構(gòu)的意思是局部最優(yōu)解能決 定全局最優(yōu)解（

6、對有些問題這個(gè)要求并不能 完全滿足，故有時(shí)需要引入一定的近似）。 簡單地說，問題能夠分解成子問題來解決。 最優(yōu)子結(jié)構(gòu)性質(zhì)。如果問題的最優(yōu)解所 包含的子問題的解也是最優(yōu)的，我們就稱該 問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原 理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決 問題提供了重要線索。 子問題重疊性質(zhì)。子問題重疊性質(zhì)是指 在用遞歸算法自頂向下對問題進(jìn)行求解時(shí)， 每次產(chǎn)生的子問題并不總是新問題，有些子 問題會被重復(fù)計(jì)算多次。動態(tài)規(guī)劃算法正是 利用了這種子問題的重疊性質(zhì)，對每一個(gè)子 問題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在 一個(gè)表格中，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過的 子問題時(shí)，只是在表格中簡單地查看一下

7、結(jié) 果，從而獲得較高的效率。 矩陣連乘計(jì)算次序問題的最優(yōu)解包含 著其子問題的最優(yō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)是 問題能用動態(tài)規(guī)劃算法求解的前提。 同一個(gè)問題可以有多種方式刻劃 它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度 更快（空間占用小，問題的維度低）重疊子 問題遞歸算法求解問題時(shí)，每次產(chǎn)生的子問

8、 題并不總是新問題，有些子問題被反復(fù)計(jì)算 多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。 動態(tài)規(guī)劃算法，對每一個(gè)子問題只 解一次，而后將其解保存在一個(gè)表格中，當(dāng) 再次需要解此子問題時(shí)，只是簡單地用常數(shù) 時(shí)間查看一下結(jié)果。 通常不同的子問題個(gè)數(shù)隨問題的大小 呈多項(xiàng)式增長。因此用動態(tài)規(guī)劃算法只需要 多項(xiàng)式時(shí)間，從而獲得較高的解題效率。 1.2備忘錄 備忘錄方法備忘錄方法的控制結(jié) 構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在 于備忘錄方法為每個(gè)解過的子問題建立了 備忘錄以備需要時(shí)查看，避免了相同子問題 的重復(fù)求解。 由最長公共子序列問題的最優(yōu)子 結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用 c[i][j]記錄序

9、列和的最長公共子序列的長 度。其中，Xi={x1,x2,…，xi}； Yj={y1,y2,…,yj}。當(dāng) i=0或 j=0時(shí)，空序 列是Xi和Yj的最長公共子序列。故此時(shí) C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性 質(zhì)可建立遞歸關(guān)系如下： 0 i= 0,j= 0 c[i][j] =\ di—1]U—1]+1 i,j〉Q x = y i j maxCi]j—1],c[i —1]j]} i,j> Q f.豐七 在算法Icslength和les中，可進(jìn)一步將數(shù) 組b省去。事實(shí)上，數(shù)組元素c[i][j]的值 僅由 c[i-1][j-1] c[i-1][j]和 c[i][j-1] 這3個(gè)數(shù)組

10、元素的值所確定。對于給定的數(shù) 組元素c[i][j]，可以不借助于數(shù)組b而僅 借助于c本身在時(shí)間內(nèi)確定c[i][j]的值是 由 c[i-1][j-1] c[i-1][j]和 c[i][j-1沖 哪一個(gè)值所確定的。 如果只需要計(jì)算最長公共子序列 的長度，則算法的空間需求可大大減少。事 實(shí)上，在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的 第i行和第i-1行。因此，用2行的數(shù)組空間 就可以計(jì)算出最長公共子序列的長度。進(jìn)一 步的分析還可將空間需求減至 O（min（m,n））。在所給多邊形中，從頂點(diǎn)i（1 WiWn）開始，長度為j（鏈中有j個(gè)頂點(diǎn)） 的順時(shí)針鏈p（i，j）可表示為v[i]， op[i+1]，…

11、，v[i+jT]。 如果這條鏈的最后一次合并運(yùn)算在op[i+s] 處發(fā)生（1 WsWj-1），則可在op[i+s]處將鏈 分割為2個(gè)子鏈p（i，s）和p（i+s，j-s）。 設(shè)m1是對子鏈p（i，s）的任意一種合并方式 得到的值，而a和b分別是在所有可能的合 并中得到的最小值和最大值。m2是 p（i+s， j-s）的任意一種合并方式得到的值，而c和 d分別是在所有可能的合并中得到的最小值 和最大值。依此定義有aWm1Wb，cWm2Wd ⑴當(dāng) op[i+s]='+ '時(shí)，顯然有 a+cWmWb+d (2) 當(dāng) op[i+s]='*'時(shí)，有min{ac, ad, bc, bd} WmWma

12、x{ac，ad, bc, bd} (3) 換句話說，主鏈的最大值和最小值可由 子鏈的最大值和最小值得到。 ⑷斐波那契數(shù)列(Fibonacci polynomial) ⑸計(jì)算斐波那契數(shù)列(Fibonacci polynomial) 的一個(gè)最基礎(chǔ)的算法是，直接按照定義計(jì) function fib(n) I if n = 0 or n = 1 I return 1 I return fib(n — 1) + fib(n — 2) 當(dāng)n=5時(shí)，fib(5)的計(jì)算過程如下： 1 fib(5) 2 fib(4) + fib(3) 3 (fib(3) + fib(2)) + (fi

13、b(2) + fib(1)) 4 ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) 5 (((fib(1) +fib(0)) +fib(1)) + (fib(1) + fib(0))) + ((fib(1) +fib(0)) +fib(1)) 由上面可以看出，這種算法對于相 似的子問題進(jìn)行了重復(fù)的計(jì)算，因此不是一 種高效的算法。實(shí)際上，該算法的運(yùn)算時(shí)間 是指數(shù)級增長的。改進(jìn)的方法是，我們可 以通過保存已經(jīng)算出的子問題的解來避免 重復(fù)計(jì)算： array map [0...n] = { 0 =>

14、0, 1 => 1 } fib( n ) I i if ( map m does not contain key n) m[n] := fib(r— 1) + fib(n— I 、 I 2) I I return m[n] 卜 -I 將前n個(gè)已經(jīng)算出的前n個(gè)數(shù)保存在數(shù)組 map中，這樣在后面的計(jì)算中可以直接易用 運(yùn)算時(shí)間變?yōu)? (n) 1.3背包問題 背包問題作為NP完全問題，暫時(shí)不存 在多項(xiàng)式時(shí)間算法。動態(tài)規(guī)劃屬于背包問題 求解最優(yōu)解的可行方法之一。此外，求解背 包問題最優(yōu)解還有搜索法等，近似解還有貪 心法等，分?jǐn)?shù)背包問題有最優(yōu)貪心解等。背 包問題具有最優(yōu)子結(jié)構(gòu)和重疊

15、子問題。動態(tài) 規(guī)劃一般用于求解背包問題中的整數(shù)背包 問題(即每種物品所選的個(gè)數(shù)必須是整數(shù))。 解整數(shù)背包問題：設(shè)有n件物品，每件價(jià) 值記為Pi，每件體積記為Vi，用一個(gè)最大 容積為Vmax的背包，求裝入物品的最大價(jià) 值。用一個(gè)數(shù)組f[i,j]表示取i件商品填 充一個(gè)容積為j的背包的最大價(jià)值，顯然問 題的解就是f[n,Vmax] f[i-1,j] {j=Vi} 0 {i=0 OR j=0} 對于特例01背包問題(即每件物品最多放1 件，否則不放入)的問題，狀態(tài)轉(zhuǎn)移方程： f[i,j] = T-—— — — —

16、— — — — — — — — — — — — — — — — — — — — — — — — — — — —— f[i-1,j] {j=Vi} 0 {i=0 OR j=0} for i:=1 to n do for j:=tot down to v[i] do F[j]:=max(f[j]f[j-v[i]]+p[i]); writeln(f[tot]) 2結(jié)論 理解動態(tài)規(guī)劃算法的概念，掌握動態(tài)規(guī) 劃算法的基本要素:最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊 子問題性質(zhì)。 前面的結(jié)果，從而避免了重復(fù)計(jì)算。算法的 [參考

17、文獻(xiàn)] ［1］ 《算法設(shè)計(jì)與分析基礎(chǔ)（第二版）》（美）Anany Levitin著 ［2］ 《算法設(shè)計(jì)技巧與分析》［沙特］M.H.Alsuwaiyel吳偉昶方世昌譯電 子工業(yè)出版社 ［3］ 《算法設(shè)計(jì)與分析》第2版 王曉東著 清華大學(xué)出版社 ［4］ 《微軟新英漢雙解計(jì)算機(jī)詞典》（美）Microsoft Corporation著 北京超品計(jì)算機(jī)有 限責(zé)任公司譯人民郵電出版社 ［5］ 《計(jì)算機(jī)算法基礎(chǔ)》鄒海明著 華中理工大學(xué)出版社 ［6］ 《計(jì)算機(jī)算法設(shè)計(jì)與分析》蘇德富著 電子工業(yè)出版社 ［7］ 《算法導(dǎo)論》Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein著潘金貴顧鐵成李成法等譯機(jī)械工業(yè)出版 ［8］ 《計(jì)算機(jī)算法》設(shè)計(jì)與分析導(dǎo)論朱清新楊凡 鐘黔川等著 人民郵電出版社