動態(tài)規(guī)劃算法在生活中的應(yīng)用

呂丹 楊子寒 周君

摘要：動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，它是解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法。文中首先分別使用遞歸法和動態(tài)規(guī)劃法對斐波拉契數(shù)列項(xiàng)進(jìn)行求解，通過其不同的求解過程詳細(xì)說明動態(tài)規(guī)劃算法的原理以及建模過程，并突出用其求解具有重疊子問題的問題的優(yōu)勢。最后，文中通過用其對生活中的房屋物品購買以及旅行花費(fèi)最少路徑選擇問題進(jìn)行建模，完成相應(yīng)的分析求解。

關(guān)鍵詞：動態(tài)規(guī)劃；運(yùn)籌學(xué)；重疊子問題；問題建模

中圖分類號：TP30 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）17-0253-03

1引言

20世紀(jì)50年代初，美國數(shù)學(xué)家R.E.Bellman等人在優(yōu)化多階段決策過程的研究中，提出了著名的最優(yōu)化原理。即把多階段過程轉(zhuǎn)化為一系列單階段問題，并利用各階段之間的關(guān)系，逐個(gè)求解，為解決這類過程優(yōu)化問題創(chuàng)造了一種新的方法，即動態(tài)規(guī)劃。使用動態(tài)規(guī)劃中的最優(yōu)化原則，可以將某一個(gè)活動過程劃分為多個(gè)相互關(guān)聯(lián)的階段?；谇耙浑A段的決策結(jié)果，依次選擇出各個(gè)不同階段所處條件下可以選擇的最優(yōu)方案。通過這種方式，不僅可以確定當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)值，而且還可以求出到中間狀態(tài)的最優(yōu)值，從而大大優(yōu)化整個(gè)過程的經(jīng)濟(jì)效益。

由于用動態(tài)規(guī)劃的思想解決問題，不僅可以令問題簡化，而且可以避免計(jì)算的冗余。因此，動態(tài)規(guī)劃問世后被廣泛應(yīng)用于生產(chǎn)調(diào)度，經(jīng)濟(jì)管理和優(yōu)化控制等領(lǐng)域。

2動態(tài)規(guī)劃算法介紹

兩種解法的不同之處：

用遞歸法求解時(shí)會存在子過程重復(fù)求解情況，例如圖1中因?yàn)榍蠼鈌ib（7）需要使用到fib（5）和fib（6）的值，所以計(jì)算機(jī)會依次遞歸對fib（6）和fib（5）的值。雖然在求解fib（6）時(shí)計(jì)算機(jī)已經(jīng)遞歸求解出了fib（5）的值，但是當(dāng)求解fib（7）的時(shí)候，計(jì)算機(jī)仍然會對fib（5）的值進(jìn)行重復(fù)求解。這樣就會大大增加計(jì)算時(shí)間。

而當(dāng)采用動態(tài)規(guī)劃法求解問題時(shí)，因?yàn)樵撍惴▽Ω鳡顟B(tài)的數(shù)值有所保存，故每個(gè)數(shù)值計(jì)算一次即可，當(dāng)下次計(jì)算需要使用到相應(yīng)數(shù)值時(shí)，直接采用即可。這樣就避免了數(shù)據(jù)的冗余計(jì)算，從而大大地減少了計(jì)算的時(shí)間。

2.1動態(tài)規(guī)劃的思想

從上面的例子可以看出：動態(tài)規(guī)劃的本質(zhì)是分治思想和解決冗余。它是一種將問題實(shí)例分解成更小和相似的子問題，通過存儲子問題的解來避免相同子問題的重復(fù)計(jì)算的算法策略。

動態(tài)規(guī)劃算法的關(guān)鍵在于找到基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件，即狀態(tài)轉(zhuǎn)移方程或基本方程。上面的例子就是在已知關(guān)系式的情況下求解問題，所以要減省許多步驟。題中的fib（n）公式就是相應(yīng)的狀態(tài)轉(zhuǎn)移方程。

2.2建立動態(tài)規(guī)劃模型的步驟

A. 對決策過程劃分階段

劃分階段是利用動態(tài)規(guī)劃解決多階段決策問題的第一步。在確定了多階段特征后，根據(jù)時(shí)間或空間的先后順序?qū)⒃撨^程劃分成若干相互關(guān)聯(lián)的階段。靜態(tài)問題應(yīng)該被人為地賦予“時(shí)間”概念，以便于劃分階段。

B. 對個(gè)階段確定狀態(tài)變量

選擇的變量不僅要準(zhǔn)確地描述過程地演變，還要滿足無后效性，并且可以確定每個(gè)階段狀態(tài)變量地值。一般而言，我們是從過程演變的特點(diǎn)中尋找的狀態(tài)變量。

C. 確定決策變量及允許決策集合

通常選擇所求問題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量地取值范圍，即確定允許決策集合。

D. 建立個(gè)階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程

根據(jù)k階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有地推關(guān)系。

E. 確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)劃基本方程

階段指標(biāo)函數(shù)是指第k階段的增益，最優(yōu)指標(biāo)函數(shù)是指從第k階段狀態(tài)到第n階段結(jié)束時(shí)所獲得收益的最優(yōu)值。最后，寫出動態(tài)規(guī)劃的基本方程。

2.3動態(tài)規(guī)劃的優(yōu)點(diǎn)

① 能得到全局最優(yōu)解

② 能提高算法效率。從上面例子可見，用遞歸法求解斐波那契數(shù)列時(shí)，算法的時(shí)間復(fù)雜度為[o2n]，采用動態(tài)規(guī)劃法時(shí)其復(fù)雜度為[on]，對比顯然可見其效率的差異。

3動態(tài)規(guī)劃在生活中的應(yīng)用

3.1動態(tài)規(guī)劃與日常購物

場景描述：

小明今天很開心，因?yàn)樵诩屹I的新房子即將拿到鑰匙。新房里面有一間他自己專用的、非常寬敞的房間。讓他更高興的是，他的母親昨天對他說：“你的房間需要購買什么物品？怎 么布置，你說了算，只要他們的價(jià)格總和不超過N元錢”。小明今天早上開始預(yù)算，但他想買太多的東西，肯定會超過母親的N元限額。因此，他把對每件物品的渴望程度，分為5等級：用整數(shù)1->5表示，第5等表示最想要。他還從互聯(lián)網(wǎng)上找到了每件商品（所有整數(shù)）的價(jià)格。他希望在不超過N元（可能等于N元）的情況下，將每件商品的價(jià)格與效益度的乘積的總和最大化。

（2） 動態(tài)規(guī)劃法

① 問題分析：

根據(jù)這個(gè)題目，我們需要在金額一定的情況下求解舒適度最高的購物單，可見這是一個(gè)最優(yōu)化問題。又因?yàn)樾∶髟谧龀雒恳粋€(gè)選擇都跟前面已經(jīng)做出的選擇有關(guān)，像這種子問題具有重疊性的最優(yōu)化問題求解，動態(tài)規(guī)劃占有很大的優(yōu)勢。

② 模型建立：

為了設(shè)計(jì)一個(gè)動態(tài)規(guī)劃算法，我們需要推導(dǎo)出一個(gè)遞推關(guān)系。下面，讓我們來考慮一個(gè)由前i[1≤i≤K]個(gè)商品定義的實(shí)例。

設(shè)商品的價(jià)格依次為P1，P2，...Pi，商品對應(yīng)的效益度分別為v1，v2，...vi，用戶的預(yù)算為N元。式子dp[i][N]表示：在前i個(gè)物品中選擇購買物品，在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與效益度的乘積的最大化的購物清單。

可以把在N元預(yù)算下，前i個(gè)物品的購買清單子集分成兩個(gè)類別：包含第i個(gè)物品的子集和不包含第i個(gè)物品的子集。然后就有如下的結(jié)論：

（1） 根據(jù)定義，在不包含第i個(gè)物品的子集中，最優(yōu)子集中每件物品的價(jià)格與效益度的乘積的總和為dp[i-1，N]；

（2） 在包含第i個(gè)物品的子集中[因此，N-Pi≥0]，最優(yōu)子集是由該物品和前i-1個(gè)物品的購買清單的最優(yōu)子集組成。這種最優(yōu)子集中每件物品的價(jià)格與效益度的乘積的總和為[pi×vi+dpi-1，N-pi]；

（3） 因此，在前i個(gè)物品中最優(yōu)子集的價(jià)格與效益度的乘積的總和等于這兩個(gè)總和中的最大值。當(dāng)然，如果當(dāng)預(yù)算不足以購買第i個(gè)物品時(shí)，前i個(gè)物品中最優(yōu)子集的價(jià)格與效益度的乘積的總和等于前i-1個(gè)物品中最優(yōu)子集的價(jià)格與效益度的乘積的總和。這個(gè)結(jié)果導(dǎo)致了如下的遞推式：

即所得購物單為：J1，J5，J6。

總結(jié)：當(dāng)我們通過分析得到相應(yīng)的動態(tài)規(guī)劃狀態(tài)方程時(shí)，用其求解問題的效率會優(yōu)于普通的理論計(jì)算。

3.2動態(tài)規(guī)劃與旅行路徑選擇

問題描述：

在一個(gè)風(fēng)和日麗的假期，你和你的家人決定去度假放松一下心情，但是為了節(jié)約成本。你調(diào)查了你的城市到度假地點(diǎn)之間所有可能的線路以及每條線路上的花費(fèi)。你想知道怎么選擇一條具體的路線才能使你的城市到你的度假地點(diǎn)的總共的花費(fèi)最少。

場景描述：已知從a地到e地有7條路徑，其路徑圖如下圖所示（圖上的數(shù)字表示兩地相應(yīng)的花費(fèi)）：

求解從a地到e地花費(fèi)最小的路徑。

（1） 問題分析：

首先，我先引入Floyed算法的相應(yīng)的概念。Floyd 算法是一種經(jīng)典的動態(tài)規(guī)劃算法，它主要用于求解完全最短路徑問題，即找到每個(gè)頂點(diǎn)到其他所有定點(diǎn)之間的距離（最短路徑的長度）。

其次，我們分析一下Floyed算法是否能用以求解此問題。分析如下：Floyed算法是已知兩點(diǎn)之間的所有路徑以及每條路徑的長度，求取最短路徑。而本題是已知兩點(diǎn)之間的所有路徑，以及每條路徑的基礎(chǔ)消費(fèi)，求取消費(fèi)最少的路徑?？梢?，這里只是把“距離最短”換成了“消費(fèi)最少”，其計(jì)算核心并沒有改變。兩者實(shí)屬一種問題，我們可以暫且把“消費(fèi)額”看成“距離值”，然后引用Floyed算法的相應(yīng)思想，對問題進(jìn)行求解。也就是說我們可以把求解的問題替代為求解最短路徑的問題。兩點(diǎn)之間最短路徑問題分析思路如下：

從任意節(jié)點(diǎn)i到任何節(jié)點(diǎn)j的最短路徑有兩種可能性。一是直接從i到j(luò)，二 是從i經(jīng)過若干個(gè)中間節(jié)點(diǎn)k 然后到j(luò)。因此，我們假設(shè)Dis （i，j）是從節(jié)點(diǎn)u 到節(jié)點(diǎn)p 的最短路徑的距離。對于每個(gè)節(jié)點(diǎn)k，我們檢查判斷Dis（i，k） + Dis（k，j） < Dis（i，j）是否為真，如果條件為真，則表示從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis（i，j）=Dis（i，k）+Dis（k，j）。如此反復(fù)進(jìn)行判斷，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis（i，j） 記錄的便是從i到j(luò)的最短路徑的距離。

4結(jié)束語

從文中我們可以看出動態(tài)規(guī)劃算法在解決多階段最優(yōu)決策問題上具有很大的優(yōu)勢，對比于遞歸算法，動態(tài)規(guī)劃的算法效率更高。同時(shí)，我們可見該算法在我們生活中的實(shí)際案例的解決上發(fā)揮著強(qiáng)大的功能。但它也具有一定的局限性，因?yàn)槊總€(gè)問題對應(yīng)的模型不同，要找到其相應(yīng)的狀態(tài)轉(zhuǎn)移方程并不是一件容易的事情。因此，如何有效地運(yùn)用動態(tài)規(guī)劃來解決問題還待做進(jìn)一步的探究。

參考文獻(xiàn)：

[1] 羅伯特.E.拉森， 約翰.L.卡斯梯， 陳偉. 動態(tài)規(guī)劃原理[M]. 清華大學(xué)出版社， 1984.

[2] 拉森. 動態(tài)規(guī)劃原理[M]. 清華大學(xué)出版社， 1984.

[3] 閆萍， 王見勇. 斐波那契數(shù)列與黃金分割數(shù)[J]. 高等數(shù)學(xué)研究， 2005， 8（1）：28-29.

[4] 朱振元， 朱承. 遞歸算法的非遞歸化實(shí)現(xiàn)[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2003， 24（3）：567-570.

[5] 郝自軍， 何尚錄. 最短路問題的Floyd算法的若干討論[J]. 重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)）， 2008， 22（5）：156-159.

[6] 葉奇明， 石世光. Floyd算法的演示模型研究[J]. 海南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2008， 26（1）：47-50.

[7] 曾方俊. Floyd算法求解最短路徑的簡明方法[J]. 價(jià)值工程， 2012， 31（19）：167-168.

[8] 謝劍輝， 郭嵩山. 國際大學(xué)生程序設(shè)計(jì)競賽試題與分析（四）——?jiǎng)討B(tài)規(guī)劃及其應(yīng)用──雜題[J]. 現(xiàn)代計(jì)算機(jī)（專業(yè)版）， 2000（7）：92-97.

[9] 任家時(shí). 多階段決策過程優(yōu)化方法的數(shù)學(xué)證明[J]. 內(nèi)蒙古民族大學(xué)學(xué)報(bào)（自然漢文版）， 1994（1）：5-6.

[10] 張玉斌. 迭代動態(tài)規(guī)劃算法及并行化研究[D]. 中國石油大學(xué)， 2008.

[11] 萬潤澤， 朱彥松. 從動態(tài)規(guī)劃算法的應(yīng)用談算法設(shè)計(jì)的教學(xué)[J]. 湖北第二師范學(xué)院學(xué)報(bào)， 2012（8）：124-126.

[12] 勞貴. 動態(tài)規(guī)劃簡介[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識， 1974（3）：77-88.

[13] 侯昶. 結(jié)構(gòu)最優(yōu)設(shè)計(jì)（三）（應(yīng)用數(shù)學(xué)規(guī)劃法）[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識， 1979（4）：71-77.