動態(tài)規(guī)劃算法分析

宛 楠 （皖南醫(yī)學(xué)院計(jì)算機(jī)教研室，安徽 蕪湖241000）

張 義 （安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖241000）

ACM國際大學(xué)生程序設(shè)計(jì)競賽 （簡稱ACM／ICPC）是由國際計(jì)算機(jī)界歷史悠久、頗具權(quán)威性的組織ACM學(xué)會 （Association for Computer Machinery）主辦，是世界上公認(rèn)的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計(jì)競賽，在信息技術(shù)界具有相當(dāng)?shù)挠绊懥Γ傎惖暮芏囝}目都是在實(shí)際的工程項(xiàng)目應(yīng)用中遇到的問題，能夠比較全面的考察學(xué)生對計(jì)算機(jī)以及其他學(xué)科知識的綜合運(yùn)用能力，通過競賽可以系統(tǒng)的檢驗(yàn)學(xué)生的計(jì)算機(jī)編程等方面的綜合水平，而這些正是IT從業(yè)者所急需的。在競賽中涉及到各種算法，其中動態(tài)規(guī)劃是較為常見的算法之一［1］。下面，筆者對動態(tài)規(guī)劃算法的進(jìn)行了分析和研究?。

1 動態(tài)規(guī)劃算法的基本思想與步驟設(shè)計(jì)

1）動態(tài)規(guī)劃算法的基本思想 動態(tài)規(guī)劃算法基本思想是將所求解問題分解成若干個(gè)子問題，先求解子問題并保存已解決的子問題的答案，然后從這些子問題的解得到原問題的解。

2）動態(tài)規(guī)劃算法步驟設(shè)計(jì) 動態(tài)規(guī)劃算法適用于解最優(yōu)化問題，一般可按以下步驟設(shè)計(jì)動態(tài)規(guī)劃算法：①找出最優(yōu)解的特質(zhì)，并描述其結(jié)構(gòu)特征；②用遞歸的方式定義最優(yōu)值；③以自下向上的方式計(jì)算出最優(yōu)值；④根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

步驟①～③是動態(tài)規(guī)劃算法的基本步驟。如果只需要求出最優(yōu)值，則步驟④可以省去。如果從最底層的子問題開始，自底向上地逐一推導(dǎo)出子問題的解，則編程的時(shí)候可不寫遞歸函數(shù)［2］。

2 數(shù)字三角形問題的動態(tài)規(guī)劃算法求解

下面以數(shù)字三角形為例，說明動態(tài)規(guī)劃算法的具體實(shí)施。

1）數(shù)字三角形問題描述 圖1給出了一個(gè)數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數(shù)加起來可以得到一個(gè)和，和最大的路徑稱為最佳路徑。問題是求出最佳路徑上的數(shù)字之和，路徑上的每一步只能從一個(gè)數(shù)走到下一層上和它最近的左邊的數(shù)或者右邊的數(shù)［3］。

2）具體實(shí)施過程 按照題目的要求，從頂點(diǎn)出發(fā)，假設(shè)先采用貪心法來求最佳路徑，每次選擇所能選的最大值作為下一步的路徑，則從頂點(diǎn)7出發(fā)選擇8，從8出發(fā)選擇1，從1出發(fā)選擇7，從7出發(fā)選擇5，所求最終路徑為7-8-1-7-5，如圖2所示，路徑和為28。然而，這個(gè)路徑并非題目所要求的最優(yōu)路徑，最優(yōu)路徑應(yīng)該為7-3-8-7-5，如圖3所示，路徑和為30。可見該問題采用自頂至下的貪心法是不能得到正確答案的。換言之，從頂點(diǎn)出發(fā)是無法直接判斷是選擇左下還是右下的數(shù)字。

轉(zhuǎn)換思路，從倒數(shù)第2層 （2、7、4、4）出發(fā)，則可以立刻做出判斷，即從2出發(fā)選擇5，從7出發(fā)選擇5，從4出發(fā)選擇6，4從出發(fā)選擇6，求和后更新該數(shù)字三角形，再從新的三角形的倒數(shù)第2層（8、1、0）出發(fā)，同樣可以立即做出判斷，即從8出發(fā)選擇12，從1出發(fā)選擇12，從0出發(fā)選擇10，求和后更新該數(shù)字三角形，依次類推直到最頂層，如圖4所示，此時(shí)該三角形只剩一個(gè)頂點(diǎn)，該頂點(diǎn)即為所求的最佳路徑和。這個(gè)過程就是動態(tài)規(guī)劃算法在求解該問題上的應(yīng)用。

3）算法實(shí)現(xiàn) 定義二維數(shù)組a來存放數(shù)字三角形，二維數(shù)組f來存放每次求和后產(chǎn)生的新數(shù)字三角形，則a［i，j］表示當(dāng)前位置的值，f［i，j］表示在i、j這個(gè)位置能取得的最大值：

3 動態(tài)規(guī)劃算法解題的一般思路

在用動態(tài)規(guī)劃算法解題時(shí)，往往將和子問題相關(guān)的各個(gè)變量的一組取值稱為一個(gè) “狀態(tài)”。一個(gè)狀態(tài)對應(yīng)于一個(gè)或多個(gè)子問題，所謂某個(gè)狀態(tài)下的 “值”，就是這個(gè)狀態(tài)所對應(yīng)的子問題的解［4］。

具體到數(shù)字三角形的例子，子問題就是 “從位于（i，j）數(shù)字開始，到底邊路徑的最大和”。這個(gè)子問題和變量i，j相關(guān)，那么一個(gè)狀態(tài)就i，j的一組取值，即每個(gè)數(shù)字的位置就是一個(gè)狀態(tài)。該狀態(tài)所對應(yīng)的值，就是從該位置的數(shù)字開始，到底邊的最佳路徑上的數(shù)字之和，即源代碼中的f［i］［j］。

確定出什么是狀態(tài)以及在該狀態(tài)下的值后，就要明確不同的狀態(tài)之間怎樣遷移——即如何從一個(gè)或多個(gè)值已知的狀態(tài)，求出另一個(gè)狀態(tài)的值。狀態(tài)的遷移可以用遞推公式表示，該遞推公式又稱為 “狀態(tài)轉(zhuǎn)移方程”。如數(shù)字三角形中的狀態(tài)轉(zhuǎn)移方程為：

4 結(jié) 語

程序設(shè)計(jì)競賽是提高大學(xué)生綜合素質(zhì)的一個(gè)很好的平臺，在參賽的準(zhǔn)備過程中會涉及到各種算法，其中動態(tài)規(guī)劃算法是最為常見的一種。筆者通過數(shù)字三角形詳細(xì)說明了動態(tài)規(guī)劃算法的解題過程，并給出了動態(tài)規(guī)劃算法解題一般思路，用動態(tài)規(guī)劃算法解題，應(yīng)該如何尋找子問題、定義狀態(tài)、狀態(tài)轉(zhuǎn)移方程是什么樣的，都需要具體問題具體分析。當(dāng)然，筆者給出的例子屬簡單動態(tài)規(guī)劃，更為復(fù)雜的動態(tài)規(guī)劃算法如雙重動態(tài)規(guī)劃，還需進(jìn)一步探討。

［1］王宏，吳文虎 ．清華實(shí)踐教學(xué) “賽課結(jié)合”新思路 ［J］．計(jì)算機(jī)教育，2006（7）：12-14．

［2］劉汝佳 ．算法競賽入門 ［M］．北京：清華大學(xué)出版社，2009：158-159．

［3］李文新，郭煒，余華山 ．程序設(shè)計(jì)導(dǎo)引與在線實(shí)踐 ［M］．北京：清華大學(xué)出版社，2007：221-226．

［4］王曉東 ．算法設(shè)計(jì)與分析 ［M］．第2版 ．北京：清華大學(xué)出版社，2008：61-62．