動態(tài)規(guī)劃算法在工程中的應用

何晏清

（華東勘測設計研究院信息中心 浙江省杭州市 330110）

動態(tài)規(guī)劃算法最早提出于20 世紀50年代，由美國數(shù)學家提出，最初是為了優(yōu)化簡單的多階段生產(chǎn)決策問題，其數(shù)學思想的實質(zhì)是將復雜的多階段問題分割成為一系列的單階段問題，進而逐個分析單個階段，確定各階段的關系，最終分析出多階段問題的最優(yōu)方案，即對實際生產(chǎn)多階段問題形成動態(tài)規(guī)劃思維，通俗來講，動態(tài)規(guī)劃法具有實時性，依據(jù)前一階段動態(tài)分析下一階段的最優(yōu)路徑法，動態(tài)規(guī)劃法不僅能夠正確分析當前階段，同時也能結(jié)合各階段的條件合理判斷最優(yōu)方案，動態(tài)規(guī)劃法以其高效性、簡化性等優(yōu)點被廣泛應用于各類生產(chǎn)調(diào)度、優(yōu)化控制等問題。

1 動態(tài)規(guī)劃法原理概述

動態(tài)規(guī)劃算法的實質(zhì)是階段拆分，將復雜的多階段和多條件拆分為單階段問題，結(jié)合各階段條件狀態(tài)對其進行合理的定義，明確各階段之間的關系，使得當前階段的問題能夠結(jié)合當前條件和下一階段的實際情況合理選擇下一階段的路徑。動態(tài)規(guī)劃的數(shù)學思維與遞推思維類似，均是為了著重解決重疊子問題和最優(yōu)子結(jié)構選擇問題而設計的數(shù)學算法，其在數(shù)學、計算機學、經(jīng)濟學以及生產(chǎn)調(diào)度中應用極為廣泛，計算機學中主要通過多種計算機語言實現(xiàn)數(shù)學算法，相對于傳統(tǒng)的整體規(guī)劃法能極大程度節(jié)約算法調(diào)度的時間和效率。

不同于排序算法或二叉樹前序、后序、中序等遍歷算法固有的分析范式，可以依據(jù)既定算法進行問題處理，而動態(tài)規(guī)劃算法的重點是分析，即使存在固有算法，在實際問題決策中仍然需要結(jié)合各階段條件和狀態(tài)動態(tài)分析下一階段的路徑選擇，僅依靠其數(shù)學思想去解決實際問題是遠遠不夠的，更重要的是合理構造動態(tài)規(guī)劃算法所需形式，進而結(jié)合動態(tài)規(guī)劃算法的思想才能解決實際調(diào)度問題。

形如：初始狀態(tài)→│決策1 │→│決策2 │→…→│決策n │→結(jié)束狀態(tài)，動態(tài)規(guī)劃法的基本思想就是將復雜問題分為若干子問題，子問題之間是相互關聯(lián)的，最終形成一條最優(yōu)化的解決方式。動態(tài)規(guī)劃算法在各子階段都需要做出相應的決策，確保路徑規(guī)劃的整體過程都達到最優(yōu)化，子階段的決策依據(jù)當前階段的狀態(tài)，當前階段的狀態(tài)可能由前一階段生成，是前一狀態(tài)的總結(jié)，但前一階段的狀態(tài)并不會影響當前狀態(tài)的下一狀態(tài)，即歷史無關性，歷史性狀態(tài)只能決定下一階段的狀態(tài)，并不會影響未來階段的狀態(tài)，階段3 的決策只依賴階段2 的輸出狀態(tài)，與狀態(tài)1 無關。各階段決策的總體稱為決策序列，決策序列即最優(yōu)的解決方案，多決策過程即將一個具有多種分支路徑或階段的復雜問題拆分成為前后相關且具有鏈狀結(jié)構的子階段。

2 解動態(tài)規(guī)劃法的基本方法

2.1 解決思路

圖1

動態(tài)規(guī)劃相比于樸素算法解決了重復子問題，動態(tài)規(guī)劃算法對任一子問題都只解決一次，其需要通過計算機的二維數(shù)組保存重疊子問題的狀態(tài)和階段，二維數(shù)組的引入可以有效避免子階段重復運算的問題。因此，動態(tài)規(guī)劃算法多依靠計算機學相關語言實現(xiàn)。其解決步驟主要分為將實際問題拆分為子階段、依據(jù)實際情況定義問題狀態(tài)和狀態(tài)關系。

2.1.1 實際問題分割

從生產(chǎn)問題的實際出發(fā)分析問題，將其分為若干子階段處理分析，子階段的劃分需要結(jié)合實際，注意子問題之間的共性，確保可以通過遞推或遞歸的方式解決各子問題，動態(tài)規(guī)劃算法的重要步驟就是分析子問題的遞推或遞歸的可能性，遞推或遞歸具有一定的關聯(lián)性，當前子問題的決策方法應該適用于下一子問題。動態(tài)規(guī)劃算法不僅可以從前至后推導，也可從后至前推導，因此問題的分割也具有多樣性，可以考慮多方面的分割方式，問題可以分割為大問題和小問題，分割應考慮大問題和小問題的共有特性，尋找狀態(tài)各子問題狀態(tài)轉(zhuǎn)移的規(guī)律，當然這需要一定的數(shù)學思維和經(jīng)驗，根據(jù)狀態(tài)轉(zhuǎn)移規(guī)律分析設計出適合子問題的決策方案。

2.1.2 定義子問題狀態(tài)和狀態(tài)的共性及關系

即確定狀態(tài)轉(zhuǎn)移方程式，類似于數(shù)學公式的推導，將子問題的狀態(tài)進行合理有效的量化，使用程序化的方式推導各子問題的狀態(tài)，一般多以計算機語言表達狀態(tài)轉(zhuǎn)移公式，計算機語言相較于數(shù)學可以表達抽象的狀態(tài)轉(zhuǎn)移公式，有助于推導狀態(tài)的共性和轉(zhuǎn)移方式。因此，動態(tài)規(guī)劃算法多使用計算機語言實現(xiàn)，其數(shù)學思想和方法也成為近年來互聯(lián)網(wǎng)企業(yè)機試考察的重點和難點。

其實，動態(tài)規(guī)劃算法的原理和思想與分治算法有異曲同工之處，分治法同樣是拆分復雜問題，將其分解為若干同類型的子問題，但分治法與動態(tài)規(guī)劃算法不同的是歷史無關性，動態(tài)規(guī)劃法的下一子階段狀態(tài)與決策與當前階段的之前階段和狀態(tài)無關，而分治法則依賴于之前階段決策出的最優(yōu)值。

2.2 解決步驟

動態(tài)規(guī)劃算法的整體步驟可分為如下階段：

2.2.1 分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構特征

首先需要全面分析實際問題，其是否適合使用動態(tài)規(guī)劃算法求解，動態(tài)規(guī)劃法使用于生產(chǎn)調(diào)度、路徑規(guī)劃等實際問題，因此分析過程需要總結(jié)出問題的結(jié)構特征，通過拆分算法將問題簡單化，分析各子問題的共性，這也是動態(tài)規(guī)劃算法的首要步驟，確定子問題共性是分析最優(yōu)質(zhì)的基礎。

2.2.2 遞歸的定義最優(yōu)解

子問題的共性是為了使各問題都能滿足遞歸或遞推法的決策方式，遞歸遞推方式能否適用是規(guī)劃算法拆分的最終目的也是動態(tài)規(guī)劃算法的核心，當然動態(tài)規(guī)劃法與二叉樹遍歷算法的區(qū)別也在于此，二叉樹遍歷算法是固有范式的算法思想，滿足條件的二叉樹都可使用遍歷算法查找，而動態(tài)規(guī)劃算法則不同，為并不存在固有范式進行最優(yōu)解計算，決策過程是通過子問題的共性進行合理的遞推和遞歸算法。

2.2.3 以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優(yōu)值

動態(tài)規(guī)劃算法的最優(yōu)值可以自底向上也可自頂向下決策，不同方向的決策過程如出一轍，都是利用遞歸算法決策當前階段的最優(yōu)值，實際生產(chǎn)問題中多采用自頂向下的決策過程。不斷的遞歸決策出每個子問題的最優(yōu)值，在頂端或底端決策的結(jié)果就是整個問題的最優(yōu)值。

3 動態(tài)規(guī)劃法的應用

3.1 多段圖的最短路徑問題

階段：如圖1 所示，將整體階段劃分為12 個子階段。

狀態(tài)：每個子階段到下一子階段都有若干個可供選擇的路徑，路徑的判斷需要結(jié)合輸入的狀態(tài)。

決策：根據(jù)輸入狀態(tài)判斷當前子問題應進行的下一步子問題，即最優(yōu)值的決策。決策必須滿足計算機語言表達的方程式，即遞歸算法的本質(zhì)，方程式也同樣適用于各子問題。如多段圖最短路徑的算法方程式為：

規(guī)劃方程：f(k)表示狀態(tài)k 到終點狀態(tài)的最短距離。

初始條件：f(k)=0；

方程：f(k-1)=min{f(k)+W(k-1,k)}其中W(k-1,k)表示狀態(tài)k-1到狀態(tài)k 的距離。

3.2 動態(tài)規(guī)劃算法在工程中的應用

動態(tài)規(guī)劃算法已經(jīng)被廣泛應用于地鐵修建、人流量疏通、水電資源分配等實際工程應用中，文章選取某市的地鐵修建問題分析動態(tài)規(guī)劃算法在實際工程中的應用。

假如某市有n 個交通線，其中1 號和n 號非常重要，為了加強運輸能力，某市決定在1 號到n 號樞紐間修建一條地鐵。地鐵由很多段隧道組成，每段隧道連接兩個交通樞紐。經(jīng)過勘探，有m 段隧道作為候選，兩個交通樞紐之間最多只有一條候選的隧道，沒有隧道兩端連接著同一個交通樞紐?，F(xiàn)在有n 家隧道施工的公司，每段候選的隧道只能由一個公司施工，每家公司施工需要的天數(shù)一致。而每家公司最多只能修建一條候選隧道。所有公司同時開始施工?；诖藢嶋H工程問題，如何選擇最優(yōu)方案實現(xiàn)最少天數(shù)內(nèi)完成整條地鐵修建。

工程的資源分配問題已經(jīng)簡化了問題拆分步驟，初始化已經(jīng)將問題分解為資源和生產(chǎn)，即階段和狀態(tài)問題，因此上述的工程問題中階段即生產(chǎn)間，狀態(tài)即條件，需要在生產(chǎn)設備總數(shù)一定的情況下求解可以產(chǎn)生最大利潤的分配方式，這就是最優(yōu)化的問題。又因為在當前設備分配選擇中都跟前面已經(jīng)做出的選擇有關，具有一定的重疊性問題，類似于這種子問題具有重疊性的最優(yōu)化問題求解，動態(tài)規(guī)劃占有很大的優(yōu)勢。

首先確定交通樞紐的數(shù)量和候選隧道的數(shù)量，總數(shù)范圍內(nèi)樞紐a 和樞紐b 之間可以修建一條隧道，需要時間為dist[i]天。那么修建整條地鐵所需總數(shù)最小的算法思想如下。

第 1 步：從第一個樞紐開始，找到與其鄰接的點：1，2，3，更新dist[]數(shù)組，因 0 不與 4 鄰接，故dist[4]為正無窮。在dist[]中找到最小值，其頂點為 2，即此時已找到 0 到 2 的最短路。

第 2 步：從 2 開始，繼續(xù)更新dist[]數(shù)組：2 與 1 不鄰接，不更新；2 與 3 鄰接，因0→2→3比dist[3]大，故不更新dist[3]；2 與 4 鄰接，因0 →2 →4 比dist[4]小，故更新dist[4]為 4。在dist[]中找到最小值，其頂點為 3，即此時又找到 0 到 3 的最短路。

第 3 步：從 3 開始，繼續(xù)更新dist[]數(shù)組：3 與 1 鄰接，因0 →3 →1 比dist[1]小，更 新dist[1]為 5；3 與 4 鄰 接，因0 →3 →4 比dist[4]大，故不更新。在dist[]中找到最小值，其頂點為 4，即此時又找到 0 到 4 的最短路。

第 4 步：從 4 開始，繼續(xù)更新dist[]數(shù)組：4 與 1 不鄰接，不更新。在dist[]中找到最小值，其頂點為 1，即此時又找到 0 到 1 的最短路。

第 5 步：所有點都已找到，停止。

根據(jù)上面的證明，動態(tài)規(guī)劃算法每次循環(huán)都可以確定一個頂點的最短路徑，故程序需要循環(huán) n-1 次。

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

4 結(jié)束語

總之，動態(tài)規(guī)劃算法在解決多階段最優(yōu)決策問題上具有很大的優(yōu)勢，可以有效的結(jié)合工程調(diào)度和資源分配問題，且對比于遞歸算法，動態(tài)規(guī)劃的算法效率更高。當然它也具有一定的局限性，因為每個問題對應的模型不同，要找到其相應的狀態(tài)轉(zhuǎn)移方程并不是一件容易的事情。因此，如何有效地運用動態(tài)規(guī)劃來解決問題還待做進一步的探究。