動(dòng)態(tài)規(guī)劃算法 算法設(shè)計(jì)

動(dòng)態(tài)規(guī)劃算法 張珊1 （安徽中醫(yī)學(xué)院安徽省合肥市230031） 摘 要：在信息學(xué)中，我們經(jīng)常遇到求最優(yōu)解的問(wèn)題，這些問(wèn)題的特點(diǎn)是，只需要求出最優(yōu)解，而不要求 寫(xiě)出最優(yōu)解的具體情況。為了解決此類(lèi)問(wèn)題，我們經(jīng)常會(huì)遇到一種有效的算法一一動(dòng)態(tài)規(guī)劃。使得我們可 以在有限的時(shí)間內(nèi)，求出問(wèn)題的解，本文介紹一些動(dòng)態(tài)規(guī)劃的理論知識(shí)。 關(guān)鍵詞：動(dòng)態(tài)規(guī)劃最優(yōu)化原理算法 中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A Dynamic programming algorithm ZHANG Shan1 (Anhui College of Traditional Chinese Medicine,Anhui 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 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 作者簡(jiǎn)介：張珊，女，安徽安慶人，安徽中醫(yī)學(xué)院本科生，學(xué)號(hào)09713051,09級(jí)醫(yī)軟（1）班 0引言 動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué) 中使用的，用于求解包含重疊字問(wèn)題的最優(yōu) 化問(wèn)題的方法。其基本思想是，將原問(wèn)題分 解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子 問(wèn)題的解求出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃的思想 是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科 學(xué)和工程領(lǐng)域。比較著名的應(yīng)用實(shí)例有：求 解最短路徑問(wèn)題，背包問(wèn)題，項(xiàng)目管理，網(wǎng) 絡(luò)流優(yōu)化等。 1正文 動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思 想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。 但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú) 立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量 級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù) 計(jì)算了許多次。動(dòng)態(tài)規(guī)劃在查找有很多重疊 字問(wèn)題的情況的最優(yōu)解時(shí)有效。它將問(wèn)題重 新組合成子問(wèn)題。為了避免多次解決這些子 問(wèn)題，它們的結(jié)果都逐漸被計(jì)算并被保存， 從簡(jiǎn)單的問(wèn)題直到整個(gè)問(wèn)題都被解決。因 此，動(dòng)態(tài)規(guī)劃保存遞歸時(shí)的結(jié)果，因而不會(huì) 在解決同樣的問(wèn)題時(shí)花費(fèi)時(shí)間。如果能夠保 存已解決的子問(wèn)題的答案，而在需要時(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) 動(dòng)態(tài)規(guī)劃只能應(yīng)用于有最優(yōu)子結(jié)構(gòu)的 問(wèn)題。最優(yōu)子結(jié)構(gòu)的意思是局部最優(yōu)解能決 定全局最優(yōu)解（對(duì)有些問(wèn)題這個(gè)要求并不能 完全滿足，故有時(shí)需要引入一定的近似）。 簡(jiǎn)單地說(shuō)，問(wèn)題能夠分解成子問(wèn)題來(lái)解決。 最優(yōu)子結(jié)構(gòu)性質(zhì)。如果問(wèn)題的最優(yōu)解所 包含的子問(wèn)題的解也是最優(yōu)的，我們就稱該 問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原 理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決 問(wèn)題提供了重要線索。 子問(wèn)題重疊性質(zhì)。子問(wèn)題重疊性質(zhì)是指 在用遞歸算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí)， 每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子 問(wèn)題會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是 利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子 問(wèn)題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在 一個(gè)表格中，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過(guò)的 子問(wèn)題時(shí)，只是在表格中簡(jiǎn)單地查看一下結(jié) 果，從而獲得較高的效率。 矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含 著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子 結(jié)構(gòu)性質(zhì)。 在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)， 所用的方法具有普遍性：首先假設(shè)由問(wèn)題的 最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后 再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn) 題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自 底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐 步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是 問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。 同一個(gè)問(wèn)題可以有多種方式刻劃 它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度 更快（空間占用小，問(wèn)題的維度低）重疊子 問(wèn)題遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn) 題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算 多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。 動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只 解一次，而后將其解保存在一個(gè)表格中，當(dāng) 再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù) 時(shí)間查看一下結(jié)果。 通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小 呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要 多項(xiàng)式時(shí)間，從而獲得較高的解題效率。 1.2備忘錄 備忘錄方法備忘錄方法的控制結(jié) 構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在 于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了 備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題 的重復(fù)求解。 由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子 結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用 c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng) 度。其中，Xi={x1,x2,…，xi}； Yj={y1,y2,…,yj}。當(dāng) i=0或 j=0時(shí)，空序 列是Xi和Yj的最長(zhǎng)公共子序列。故此時(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ù)組元素的值所確定。對(duì)于給定的數(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ì)算最長(zhǎng)公共子序列 的長(zhǎng)度，則算法的空間需求可大大減少。事 實(shí)上，在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的 第i行和第i-1行。因此，用2行的數(shù)組空間 就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一 步的分析還可將空間需求減至 O（min（m,n））。在所給多邊形中，從頂點(diǎn)i（1 WiWn）開(kāi)始，長(zhǎng)度為j（鏈中有j個(gè)頂點(diǎn)） 的順時(shí)針鏈p（i，j）可表示為v[i]， op[i+1]，…，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是對(duì)子鏈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} WmWmax{ac，ad, bc, bd} (3) 換句話說(shuō)，主鏈的最大值和最小值可由 子鏈的最大值和最小值得到。 ⑷斐波那契數(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ì)算過(guò)程如下： 1 fib(5) 2 fib(4) + fib(3) 3 (fib(3) + fib(2)) + (fib(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)) 由上面可以看出，這種算法對(duì)于相 似的子問(wèn)題進(jìn)行了重復(fù)的計(jì)算，因此不是一 種高效的算法。實(shí)際上，該算法的運(yùn)算時(shí)間 是指數(shù)級(jí)增長(zhǎng)的。改進(jìn)的方法是，我們可 以通過(guò)保存已經(jīng)算出的子問(wèn)題的解來(lái)避免 重復(fù)計(jì)算： array map [0...n] = { 0 => 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背包問(wèn)題 背包問(wèn)題作為NP完全問(wèn)題，暫時(shí)不存 在多項(xiàng)式時(shí)間算法。動(dòng)態(tài)規(guī)劃屬于背包問(wèn)題 求解最優(yōu)解的可行方法之一。此外，求解背 包問(wèn)題最優(yōu)解還有搜索法等，近似解還有貪 心法等，分?jǐn)?shù)背包問(wèn)題有最優(yōu)貪心解等。背 包問(wèn)題具有最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題。動(dòng)態(tài) 規(guī)劃一般用于求解背包問(wèn)題中的整數(shù)背包 問(wèn)題(即每種物品所選的個(gè)數(shù)必須是整數(shù))。 解整數(shù)背包問(wèn)題：設(shè)有n件物品，每件價(jià) 值記為Pi，每件體積記為Vi，用一個(gè)最大 容積為Vmax的背包，求裝入物品的最大價(jià) 值。用一個(gè)數(shù)組f[i,j]表示取i件商品填 充一個(gè)容積為j的背包的最大價(jià)值，顯然問(wèn) 題的解就是f[n,Vmax] f[i-1,j] {j<Vi} max{f[i-1,j],f[i,j-Vi]+Pi} {j>=Vi} 0 {i=0 OR j=0} 對(duì)于特例01背包問(wèn)題(即每件物品最多放1 件，否則不放入)的問(wèn)題，狀態(tài)轉(zhuǎn)移方程： f[i,j] = T-—— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —— f[i-1,j] {j<Vi} max{f[i-1,j],f[i-1,j-Vi]+Pi} {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é)論 理解動(dòng)態(tài)規(guī)劃算法的概念，掌握動(dòng)態(tài)規(guī) 劃算法的基本要素:最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊 子問(wèn)題性質(zhì)。 前面的結(jié)果，從而避免了重復(fù)計(jì)算。算法的 [參考文獻(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)論朱清新楊凡 鐘黔川等著 人民郵電出版社