陳曉梅 張晶

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

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

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

1 概述

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

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

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

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

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

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

3.1 分析問題

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

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

可以使用反證+剪貼[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貼上去，若子問題相互獨(dú)立，將會(huì)獲得原問題Q的另一個(gè)解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è)的一個(gè)最優(yōu)解中提取出來，而不是原問題中的任意一個(gè)子問題。如：假設(shè)矩陣連乘問題的最優(yōu)解的首層斷點(diǎn)是矩陣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)由這兩個(gè)子問題出發(fā)去證明最優(yōu)子結(jié)構(gòu)性質(zhì)。

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

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

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

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

3.2 建立遞歸公式

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

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

3.2.1 子問題的范圍

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

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

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

有些問題，其產(chǎn)生的子問題的起點(diǎn)或終點(diǎn)不相同，其子問題的范圍需要使兩個(gè)維度表示。如矩陣連乘問題[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)價(jià)值。相應(yīng)遞歸公式如公式（4）（5）所示。原問題的最優(yōu)值是m[n][C]（根據(jù)公式（4））或m[1][C]（根據(jù)公式（5））。

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

動(dòng)態(tài)規(guī)劃算法使用備忘錄或自底向上的方法計(jì)算每一個(gè)子問題的最優(yōu)值，從而保證每個(gè)子問題最多只被計(jì)算一次。無論是備忘錄方法還是自底向上方法，其關(guān)鍵實(shí)現(xiàn)都是一張表格，表格的維度與子問題維度相同，表格中每個(gè)維度的大小與子問題對(duì)應(yīng)參數(shù)的取值范圍一致。在C++中可使用數(shù)組表示。表格中的每一項(xiàng)對(duì)應(yīng)一個(gè)子問題。如最大子段和問題，其子問題最優(yōu)值表示為c[i]，顯然表格設(shè)置為一維數(shù)組a即可，根據(jù)公式（1），a[i]的值表示序列中以第i個(gè)數(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)價(jià)值。

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

若使用自底向上方式“翻譯”遞歸公式，其實(shí)質(zhì)就是“填表”。填表范圍、從表格的哪一項(xiàng)開始填以及按照什么順序繼續(xù)填，是有規(guī)律可循的。從子問題表示的每個(gè)維度的取值范圍，可確定填表范圍；從遞推公式和原問題的表示方式，可確定從表格的哪一項(xiàng)開始填以及按照什么順序繼續(xù)填。如矩陣連乘問題，根據(jù)公式（3），1<=i<=j<=n， 顯然這是一張n行n列的二維表a，填表范圍是右上三角（含對(duì)角線）；原問題的最優(yōu)值是m[1][n]，對(duì)應(yīng)表格右上角a[1][n]；遞推公式表明，在計(jì)算第i行第j列的最優(yōu)值a[i][j]時(shí)，需要利用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é)束語

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

參考文獻(xiàn)：

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

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