陳曉梅 張晶

摘要：在動態(tài)規(guī)劃算法的教學(xué)中，學(xué)生最迷惑的是遞歸公式的建立與“翻譯”。并不以單一個具體的事例來討論動態(tài)規(guī)劃算法的實現(xiàn)，而是利用若干個各具代表性的實例來抽象出動態(tài)規(guī)劃算法的共性以及解題方法。

關(guān)鍵詞：動態(tài)規(guī)劃；遞歸公式；備忘錄；自底向上

中圖分類號：O221.3 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）26-0146-02

1 概述

有一類問題，可以將待求解的問題分解成若干子問題，先求解子問題的解，然后通過這些子問題的解來求得原問題的解。若分解的子問題出現(xiàn)重疊，如果使用常規(guī)的遞歸方法來設(shè)計算法，則會耗費大量時間重復(fù)計算相同的子問題。而動態(tài)規(guī)劃使用備忘錄或自底向上的方法來設(shè)計算法，以保證每個子問題最多只被計算一次。

本文基于動態(tài)規(guī)劃求解問題的共性思維探討動態(tài)規(guī)劃算法的教學(xué)過程。

2 動態(tài)規(guī)劃算法案例選擇

在動態(tài)規(guī)劃算法的教學(xué)中，可以選擇一些經(jīng)典的、代表性強(qiáng)的案例進(jìn)行教學(xué)。使用動態(tài)規(guī)劃解決問題，關(guān)鍵是要確定某個狀態(tài)的最優(yōu)解，因此狀態(tài)的選擇是否正確，決定整個問題求解的正確性。一般可選擇以第i時刻為起點、第j時刻為終點的狀態(tài)，如矩陣連乘問題。還可以選擇以最小規(guī)模子問題或原問題規(guī)模為起點、第i時刻為終點的狀態(tài)，如最長公共子序列問題、最大子段和問題和0-1背包問題。

3 動態(tài)規(guī)劃算法求解問題

動態(tài)規(guī)劃一般用于解最優(yōu)化問題。利用某個狀態(tài)（一般是初始狀態(tài)或目標(biāo)狀態(tài)）的最優(yōu)解去計算下一個狀態(tài)的最優(yōu)解，直至獲得原問題的全局最優(yōu)解。因此，使用動態(tài)規(guī)劃求解問題的一般步驟是：分析該問題是否滿足動態(tài)規(guī)劃求解的條件；建立遞歸公式表示某個狀態(tài)的最優(yōu)值；使用備忘錄或自底向上的方法計算最優(yōu)值；構(gòu)造最優(yōu)解（有需要的話）。

3.1 分析問題

3.1.1 最優(yōu)子結(jié)構(gòu)性質(zhì)

當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)[1]。動態(tài)規(guī)劃算法求解問題時，正是通過利用子問題的最優(yōu)解來計算原問題的最優(yōu)解，因此要求該問題要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。滿足最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，其子問題一定是相互獨立的。

可以使用反證+剪貼[2]來證明最優(yōu)子結(jié)構(gòu)性質(zhì)。有原問題Q，其最優(yōu)解為S，若該問題不滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，即S中所包含的子問題Q1的解T并非Q1的最優(yōu)解。不妨設(shè)T是Q1的最優(yōu)解，從原問題的最優(yōu)解S中將T剪下來，將T貼上去，若子問題相互獨立，將會獲得原問題Q的另一個解S=S-T+T，由于T優(yōu)于T，故S優(yōu)于S，此結(jié)論與S是原問題的最優(yōu)解矛盾。因此假設(shè)不成立。T就是子問題Q的最優(yōu)解。即原問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。

在最優(yōu)子結(jié)構(gòu)證明的教學(xué)中，需要提醒學(xué)生注意子問題的提取方式。其必須是在原問題假設(shè)的一個最優(yōu)解中提取出來，而不是原問題中的任意一個子問題。如：假設(shè)矩陣連乘問題的最優(yōu)解的首層斷點是矩陣k，即optimal（[a1：an]） = optimal（[a1：ak]）+optimal（[ak+1：an]）+a1行數(shù)*ak列數(shù)*an列數(shù)，則由此產(chǎn)生的子問題是[a1：ak]和[ak+1：an]，應(yīng)由這兩個子問題出發(fā)去證明最優(yōu)子結(jié)構(gòu)性質(zhì)。

3.1.2 重疊子問題性質(zhì)

重疊子問題是指在計算不同的子問題的最優(yōu)解時，這些不相同的子問題產(chǎn)生了相同的子子問題，這會導(dǎo)致有些子問題會被重復(fù)計算。

可以列出一個規(guī)模比較小的實例，對該實例逐層分解子問題，以判斷是否有重疊子問題性質(zhì)。如假設(shè)矩陣連乘問題的一個實例是[a1：a4]，則原問題可能產(chǎn)生的子問題是：[a1：a1]、[a2：a4]、[a1：a2]、[a3：a4]、[a1：a3]、[a4：a4]，而子問題[a2：a4]會產(chǎn)生[a2：a2]、[a3：a4]、[a2：a3]、[a4：a4]，顯然[a3：a4]出現(xiàn)重復(fù)計算現(xiàn)象。隨著矩陣連乘問題規(guī)模的加大，重疊子問題的數(shù)量會迅速增加，達(dá)到指數(shù)級別[1]。

動態(tài)規(guī)劃算法使用備忘錄或自底向上的方法計算每一個子問題的最優(yōu)值，從而保證每個子問題最多只被計算一次。

3.2 建立遞歸公式

在這一步，將會使用數(shù)學(xué)公式來表示子問題的最優(yōu)解。由于動態(tài)規(guī)劃算法總是通過利用子問題的最優(yōu)解來計算原問題的最優(yōu)解，因此當(dāng)計算某個子問題時，又會產(chǎn)生對更小規(guī)模的子問題的求解，該過程可以使用遞歸來描述。在教學(xué)過程中，可以從子問題的表示、求解子問題的遞歸公式，以及原問題的表示三個步驟遞進(jìn)分析。其中關(guān)鍵步驟是子問題的表示，以下基于子問題表示來展開探討。

要表示一個子問題，就要分析表示該子問題所需的維度及每個維度的含義，這可以對應(yīng)理解為表示這個子問題的參數(shù)個數(shù)及每個參數(shù)的含義。無論是什么問題，其中一個共同的參數(shù)必定是這個子問題的范圍，而其他參數(shù)則與具體問題相關(guān)。

3.2.1 子問題的范圍

有些問題，其產(chǎn)生的子問題的起點或終點都相同且與原問題的起點或終點一致，其子問題的范圍可用一個維度表示。如在求a1..an的最大子段和問題中，最大子段有可能以任一個元素ai為結(jié)尾。因此需要計算所有以ai（1<=i<=n）為結(jié)尾的最大子段和Ti，max{Ti}即為全局最優(yōu)值。這些子問題（求a1..ai中以ai為結(jié)尾的最大子段和）范圍的起點相同且與原問題一致（起點都是a1）。同時這些子問題的求解不受其他因素約束，故可將子問題表示為c[i]，其含義是a1..ai中以ai為結(jié)尾的最大子段和。進(jìn)一步分析，c[i]依賴于c[i-1]，故可用c[i-1]來計算c[i]。相應(yīng)遞歸公式如公式（1）所示。原問題最優(yōu)值表示為max{c[i]|1<=i<=n}。

另一角度分析，c[i]亦可理解為以ai為起點的ai..an最大子段和，這種表示可看作子問題的終點相同且與原問題一致（終點都是an），此時c[i]依賴于c[i+1]。相應(yīng)遞歸公式如公式（2）所示。原問題最優(yōu)值可表示為max{c[i]|1<=i<=n}。

滿足以上特點的可用動態(tài)規(guī)劃求解的典型問題還有很多，如最長單調(diào)遞增子序列問題，最長公共子序列問題，編輯距離問題，游艇租用問題，0-1背包問題，等等，這些問題都可以使用上述思路寫出遞歸公式。

有些問題，其產(chǎn)生的子問題的起點或終點不相同，其子問題的范圍需要使兩個維度表示。如矩陣連乘問題[a1：an]，其首層子問題是[a1：ak]和[ak+1：an]（1<=k

3.2.2 子問題的其他約束條件

有些問題，其子問題的表示還受其他條件的約束，這就需要把這些約束條件加入到子問題的數(shù)學(xué)表示中。如0-1背包問題，其子問題范圍可用i標(biāo)記，表示當(dāng)前可選物品是第1件到第i件物品，或第i件到第n件物品。0-1背包問題的最優(yōu)解還受當(dāng)前背包剩余容量的約束，因此子問題的最優(yōu)值應(yīng)記為m[i][j]，表示在前述物品范圍內(nèi)，當(dāng)前背包容量為j的情況下的最優(yōu)價值。相應(yīng)遞歸公式如公式（4）（5）所示。原問題的最優(yōu)值是m[n][C]（根據(jù)公式（4））或m[1][C]（根據(jù)公式（5））。

3.3 數(shù)據(jù)結(jié)構(gòu)與算法選擇

動態(tài)規(guī)劃算法使用備忘錄或自底向上的方法計算每一個子問題的最優(yōu)值，從而保證每個子問題最多只被計算一次。無論是備忘錄方法還是自底向上方法，其關(guān)鍵實現(xiàn)都是一張表格，表格的維度與子問題維度相同，表格中每個維度的大小與子問題對應(yīng)參數(shù)的取值范圍一致。在C++中可使用數(shù)組表示。表格中的每一項對應(yīng)一個子問題。如最大子段和問題，其子問題最優(yōu)值表示為c[i]，顯然表格設(shè)置為一維數(shù)組a即可，根據(jù)公式（1），a[i]的值表示序列中以第i個數(shù)為結(jié)尾的最大子段和；又如0-1背包問題，其子問題最優(yōu)值表示為c[i][j]，可將表格設(shè)置為二維數(shù)組a，根據(jù)公式（4），a[i][j]的值表示當(dāng)前背包容量為j，待選物品是第1件到第i件狀態(tài)下的最優(yōu)價值。

在使用遞歸方式“翻譯”遞歸公式時，以上面所述的表格充當(dāng)備忘錄。先將備忘錄中的每一項初始化為一個特殊的值，每次求解子問題時，先到備忘錄查看該子問題是否已記錄答案，若有，直接返回答案，否則，遞歸求解計算該子問題并把答案寫入備忘錄。

若使用自底向上方式“翻譯”遞歸公式，其實質(zhì)就是“填表”。填表范圍、從表格的哪一項開始填以及按照什么順序繼續(xù)填，是有規(guī)律可循的。從子問題表示的每個維度的取值范圍，可確定填表范圍；從遞推公式和原問題的表示方式，可確定從表格的哪一項開始填以及按照什么順序繼續(xù)填。如矩陣連乘問題，根據(jù)公式（3），1<=i<=j<=n， 顯然這是一張n行n列的二維表a，填表范圍是右上三角（含對角線）；原問題的最優(yōu)值是m[1][n]，對應(yīng)表格右上角a[1][n]；遞推公式表明，在計算第i行第j列的最優(yōu)值a[i][j]時，需要利用a[i][i：j-1]以及a[i+1：j][j]的值，即要先求出表格中a[i][j]的左邊部分以及下面部分的值。因此，首先應(yīng)填右下角a[n][n]的值，然后按照自下而上，自左向右的順序來填表格a的右上三角，最后填的是a[1][n]，即原問題的最優(yōu)值。

4 結(jié)束語

動態(tài)規(guī)劃算法是一種比較抽象的算法，在動態(tài)規(guī)劃教學(xué)中，需要向?qū)W生講清楚理論分析和遞歸公式的建立。本文著重從求解問題的共性思維出發(fā)，介紹了具體的理論分析方法以及操作性強(qiáng)的建立和“翻譯”遞歸公式方法。實踐證明，學(xué)生利用該思路能夠較好地解決一些動態(tài)規(guī)劃典型問題。

參考文獻(xiàn)：

[1] 王曉東. 計算機(jī)算法設(shè)計與分析.第4版[M]. 電子工業(yè)出版社， 2012.

[2] ThomasH.Cormen. 算法導(dǎo)論：第2版[M]. 機(jī)械工業(yè)出版社， 2007. [通聯(lián)編輯：王力]