動(dòng)態(tài)規(guī)劃思想在ACM競(jìng)賽中的應(yīng)用研究

劉雄輝　汪紅宇　陳義明

摘要：動(dòng)態(tài)規(guī)劃算法是運(yùn)籌學(xué)的一個(gè)分支，是求解多階段決策最優(yōu)的方法。該文介紹了使用動(dòng)態(tài)規(guī)劃算法的一定條件，并詳寫了使用動(dòng)態(tài)規(guī)劃算法解決決策性問題時(shí)的三大階段和三大要素，以及動(dòng)態(tài)規(guī)劃算法與分治算法、貪心算法的關(guān)系。并以動(dòng)態(tài)規(guī)劃算法在ACM算法競(jìng)賽中的應(yīng)用，來加強(qiáng)對(duì)于動(dòng)態(tài)規(guī)劃的理解。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；最優(yōu)；算法；策略

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）18-0238-02

動(dòng)態(tài)規(guī)劃算法是求解多階段決策最優(yōu)的方法，它與分治算法和貪婪算法有一定的相似度，它能夠高效地處理分治和貪婪不可以處理的問題。

1使用動(dòng)態(tài)規(guī)劃算法的條件

動(dòng)態(tài)規(guī)劃算法從問世到現(xiàn)在，在很多方面得到了廣泛運(yùn)用。如最短路線、背包問題、最小生成樹等問題，動(dòng)態(tài)規(guī)劃算法比用其他算法求解更加便利。然而動(dòng)態(tài)規(guī)劃并不適用于所有的問題，只有滿足以下條件才能使用動(dòng)態(tài)規(guī)劃求解：

1）最優(yōu)化原理

2）無后效性

最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，假使一個(gè)問題沒有最優(yōu)化原理的支持，就不能使用動(dòng)態(tài)規(guī)劃算法求解。那么最優(yōu)化原理是什么呢？簡(jiǎn)單來說就是一個(gè)最優(yōu)策略的子策略，對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。

例如圖1，狀態(tài)1→狀態(tài)7的最優(yōu)策略為A1-A2-A3-A6-A7，那么其子策略A2-A3也一定是狀態(tài)2→狀態(tài)6的最優(yōu)策略。

無后效性是問題可使用動(dòng)態(tài)規(guī)劃算法的一個(gè)標(biāo)記。我們可以理解為：一個(gè)階段的狀態(tài)只要確定了，那么后面過程的演化不會(huì)受前面狀態(tài)和策略影響，以圖1舉例說明：狀態(tài)3和狀態(tài)4只能夠由狀態(tài)2經(jīng)過決策A2、A4得來，和其他的狀態(tài)沒有任何的關(guān)系。

2動(dòng)態(tài)規(guī)劃問題求解模式

動(dòng)態(tài)規(guī)劃是一種以多階段決策問題的特點(diǎn)為依據(jù)，將其轉(zhuǎn)變成一系列相互聯(lián)系的單階段問題，再逐個(gè)解決的說法。一些靜態(tài)的問題，只要我們找到可以將其劃分成相互聯(lián)系“階段”的特征，就可以轉(zhuǎn)化為多階段動(dòng)態(tài)問題。

動(dòng)態(tài)規(guī)劃所處理的問題是一個(gè)多階段的決策問題，以圖1為例，它由狀態(tài)1開始，在中間經(jīng)過不同的決策選擇，達(dá)到狀態(tài)7。這些決策形成了一個(gè)最優(yōu)策略序列（A1-A2-A3-A7），同時(shí)確定了整個(gè)過程的一條活動(dòng)路線（狀態(tài)1→狀態(tài)2→狀態(tài)3→狀態(tài)6→狀態(tài)7）。

動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)擁有必定的形式，一般必須經(jīng)過三個(gè)步驟：

1）劃分階段：按照我們找到的特征，將其劃分成相互的階段。

2）確定每一個(gè)階段的狀態(tài)和狀態(tài)變量。

3）確定狀態(tài)轉(zhuǎn)移方程：根據(jù)前后階段的演變規(guī)律寫出狀態(tài)轉(zhuǎn)移方程。

求解動(dòng)態(tài)規(guī)劃問題時(shí)，我們需要確定它的三大要素：

1）問題每一個(gè)階段

2）每一個(gè)階段對(duì)應(yīng)的所有狀態(tài)

3）從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系

只要我們確定動(dòng)態(tài)規(guī)劃的三大要素，整個(gè)求解過程就能夠使用最優(yōu)決策表來表示，最優(yōu)決策表是一個(gè)多維的表（在ACM算法競(jìng)賽中最常見的是二維），決策的階段和狀態(tài)對(duì)應(yīng)表的行與列，表中數(shù)據(jù)為對(duì)應(yīng)階段和狀態(tài)下的最優(yōu)值，從初始狀態(tài)開始，以某一優(yōu)先順序填寫表格，填寫完之后根據(jù)表中數(shù)據(jù)得到最優(yōu)解。

3動(dòng)態(tài)規(guī)劃算法與其他相近算法的關(guān)系

動(dòng)態(tài)規(guī)劃算法和貪婪算法都是由局部最優(yōu)推導(dǎo)全局最優(yōu)的一種遞推算法。貪婪算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是貪心選擇性質(zhì)，它是問題可以使用貪婪算法的前提。

貪婪算法做出的選擇只是在當(dāng)前情況下最好的，而不會(huì)從整體最優(yōu)上考慮，它的選擇僅僅是局部最優(yōu)。貪心選擇性質(zhì)就是：可以通過貪婪算法的得到的局部最優(yōu)得到整體最優(yōu)解。而在動(dòng)態(tài)規(guī)劃算法中，中間階段的最好選擇，不能保證最后的結(jié)果是最優(yōu)的。

動(dòng)態(tài)規(guī)劃與分治法都是通過組合子問題的解求解原問題的算法。不同的是，分治算法把原問題分為沒有聯(lián)系的子問題，遞歸地求解子問題，然后把子問題的解組合，以求解原問題。而動(dòng)態(tài)規(guī)劃對(duì)應(yīng)子問題重復(fù)的情況，即不一樣的子問題具有公共的子子問題（子子問題是將子問題再次劃分得到的子問題）。面對(duì)這樣的問題，分治算法將完成許多不必要的任務(wù)，它會(huì)反復(fù)地求解那些公共的子子問題。而動(dòng)態(tài)規(guī)劃對(duì)于重復(fù)的子子問題只求解一次，并把它記錄在最優(yōu)決策表中，從而避免了重復(fù)子問題的計(jì)算工作。

在分治法示意圖中，我們可以知道已知f（n）f（n-2）+f（n-4），求f（10）。f（2）、f（4）都是重復(fù)子問題，使用動(dòng)態(tài)規(guī)劃的話，我們就可以直接記錄值，以避免重復(fù)的求解，所以動(dòng)態(tài)規(guī)劃算法實(shí)際上是在以空間換時(shí)間。

4動(dòng)態(tài)規(guī)劃算法在ACM競(jìng)賽中的應(yīng)用

為了能夠更好地了解動(dòng)態(tài)規(guī)劃算法的使用，以下面的題目來介紹一下動(dòng)態(tài)規(guī)劃算法在ACM算法競(jìng)賽中的應(yīng)用，加深對(duì)動(dòng)態(tài)規(guī)劃算法的理解。

Problem Description

子序列是一個(gè)序列通過刪除若干元素后可以得到的序列。公共子序列就是一個(gè)序列同時(shí)是多個(gè)序列的子序列。題目給出兩個(gè)序列X和Y，求解XY的最長(zhǎng)公共子序列長(zhǎng)度。

Input：輸入若干組數(shù)據(jù)，每組數(shù)據(jù)包括：序列X和Y，中間使用空格分開

Output：對(duì)應(yīng)每組數(shù)據(jù)輸出序列X和Y的最長(zhǎng)公共子序列長(zhǎng)度

輸入：ABCABCDEA BCBCEA輸出：6

問題分析：

題目已知了序列X和序列Y，要求求解其最長(zhǎng)公共子序列的長(zhǎng)度。對(duì)于一個(gè)長(zhǎng)度為n的系列，我們考慮其中元素的去與留，會(huì)有2*種可能。所以序列XY的長(zhǎng)度較短的話，我們可以使用遍歷。當(dāng)n很大的時(shí)候，使用遍歷將使程序的時(shí)間復(fù)雜度很高，明顯不可取。

所以我們使用動(dòng)態(tài)規(guī)劃算法來解決這道問題，采用二維數(shù)組來標(biāo)識(shí)中間計(jì)算結(jié)果，避免重復(fù)的計(jì)算來提高效率。我們以在字符串X、Y的不同位置劃分階段，用num[i][j]二維數(shù)組保存每一個(gè)階段下的狀態(tài)（即字符串X前面i個(gè)字符和字符串Y前面i個(gè)字符的最長(zhǎng)公共子序列長(zhǎng)度）。根據(jù)只有當(dāng)序列中X[i]==Y[j]序列X[1…i]Y[1…j]的最長(zhǎng)公共子序列長(zhǎng)度比序列X[1…i-1]Y[1…j-1]的最長(zhǎng)公共子序列長(zhǎng)度大1。由此可以得到最長(zhǎng)公共子序列長(zhǎng)度的狀態(tài)轉(zhuǎn)移方程（圖3）。再根據(jù)狀態(tài)轉(zhuǎn)移方程，我們可以依次填寫最優(yōu)決策表（圖4）。其中字符串X對(duì)應(yīng)的是二維數(shù)組nun的行，字符串Y對(duì)應(yīng)的是二維數(shù)組nun的列。

5結(jié)束語

動(dòng)態(tài)規(guī)劃算法是求解決策過程最優(yōu)化的數(shù)學(xué)方法，自問世以來，在諸多方面得到了廣泛應(yīng)用。而在ACM程序設(shè)計(jì)大賽中，動(dòng)態(tài)規(guī)劃算法也是一位從不缺席的?？?。但是要很好地利用動(dòng)態(tài)規(guī)劃算法，就要充分的理解動(dòng)態(tài)規(guī)劃問題的求解，區(qū)分動(dòng)態(tài)規(guī)劃和其他算法的不同。相信在將來，動(dòng)態(tài)規(guī)劃將在更多的領(lǐng)域得到更好的應(yīng)用與發(fā)展。endprint