動(dòng)態(tài)規(guī)劃詳解 第一章首先讓我們看一個(gè)例子：
例1：如下圖有一個(gè)數(shù)字三角陣，請(qǐng)編一個(gè)程序計(jì)算從頂點(diǎn)至底的某處的一條路徑，使該路徑所經(jīng)過(guò)的數(shù)字的和最大。每一步可沿左斜線向下或右斜線向下走。
7
5 3
4 2 1
2 1 3 7
這個(gè)問(wèn)題的實(shí)質(zhì)實(shí)際上是一個(gè)有向圖中最長(zhǎng)路經(jīng)問(wèn)題，可以用經(jīng)典的圖論算法或者搜索來(lái)解決。
考慮如何用搜索法來(lái)解這道題，從第一個(gè)點(diǎn)開始擴(kuò)展，每次擴(kuò)展2個(gè)可行節(jié)點(diǎn)，直到達(dá)到數(shù)字三角形的底部，從所有的可行路徑中找出最優(yōu)值，這樣做的復(fù)雜度是o(2^n)，當(dāng)n很大的時(shí)候，普通的搜索法將不可行。
觀察發(fā)現(xiàn)，搜索的效率低下很大程度上是因?yàn)樽隽舜罅康闹貜?fù)運(yùn)算，因?yàn)閷?duì)于任何一個(gè)節(jié)點(diǎn)，從他開始向下拓展的最優(yōu)值是確定的，這啟發(fā)了我們應(yīng)當(dāng)充分利用之前的運(yùn)算結(jié)果。
下面我們來(lái)進(jìn)行深入的分析，假如已經(jīng)走第I行第J列，此時(shí)最大累加和S[I，J]應(yīng)選S[I-1，J]，S[I-1，J+1]中較大者再加上（I，J）處的值A(chǔ)[I，J]，即下式
S[I，J]=A[I，J]+MAX（S[I-1，J]，S[I-1，J+1]）
所以我們可以從第一行開始，向下逐行推出每一處位置的最大累加和S，最后從底行的N個(gè)S中選出最大的一個(gè)即為所求，這種算法的復(fù)雜度為o(n^2)，比較搜索法，已經(jīng)大大的降低了，這種充分利用已經(jīng)計(jì)算出結(jié)果的方法，就叫做動(dòng)態(tài)規(guī)劃。
通過(guò)上面的例子，我們對(duì)“動(dòng)態(tài)規(guī)劃”有了一個(gè)初步認(rèn)識(shí)，它所處理的問(wèn)題是一個(gè)“多階段決策問(wèn)題”。我們現(xiàn)在對(duì)一些概念進(jìn)行具體定義：
狀態(tài)（State）：它表示事物的性質(zhì)，是描述“動(dòng)態(tài)規(guī)劃”中的“單元”的量。如例1中的每個(gè)節(jié)點(diǎn)（指節(jié)點(diǎn)處的最大值）都為單個(gè)的狀態(tài)。
階段（Stage）：階段是一些性質(zhì)相近，可以同時(shí)處理的狀態(tài)集合。通常，一個(gè)問(wèn)題可以由處理的先后次序劃分為幾個(gè)階段。如例1中的問(wèn)題，每一行若干節(jié)點(diǎn)組成一個(gè)階段。一個(gè)階段既可以包含多個(gè)狀態(tài)，也可以只包含一個(gè)狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量，例1中可用S[4 , j]來(lái)表示第四階段（即第四行）走到第j列的最大值，即第四階段狀態(tài)變量。
狀態(tài)轉(zhuǎn)移方程：是前一個(gè)階段的狀態(tài)轉(zhuǎn)移到后一個(gè)的狀態(tài)的演變規(guī)律，是關(guān)于兩個(gè)相鄰階段狀態(tài)的方程，是“動(dòng)態(tài)規(guī)劃”的中心。
如例1中： S[I，J]=A[I，J]+MAX（S[I-1，J]，S[I-1，J+1]）
決策（Decision）：每個(gè)階段做出的某種選擇性的行動(dòng)。它是我們程序所需要完成的選擇。如例1中MAX（S[I-1，J]，S[I-1，J+1]）
動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)“多階段決策問(wèn)題”，一般由初始狀態(tài)開始，通過(guò)對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線（通常是求最優(yōu)的活動(dòng)路線）
從上面的講解我們可以發(fā)現(xiàn)：動(dòng)態(tài)規(guī)劃并不像一種算法，而更像一種思考方式。
下面，我們來(lái)討論動(dòng)態(tài)規(guī)劃的應(yīng)用范圍，要確定一個(gè)問(wèn)題是否能用動(dòng)態(tài)規(guī)劃，需要考慮兩個(gè)方面：
一：最優(yōu)子結(jié)構(gòu)
即一個(gè)問(wèn)題的最優(yōu)解只取決于其子問(wèn)題的最優(yōu)解，也就是說(shuō)，非最優(yōu)解對(duì)問(wèn)題的求解沒有影響。我們?cè)賮?lái)看一個(gè)問(wèn)題：
例二：有4個(gè)點(diǎn)，分別是A、B、C、D，相鄰兩點(diǎn)用兩條連線，表示兩條通行的道路，給出每條道路的長(zhǎng)度。我們定義從A到D的所有路徑中，長(zhǎng)度除以4所得余數(shù)最小的路徑為最優(yōu)路徑。求一條最優(yōu)路徑。
很多初學(xué)者往往會(huì)認(rèn)為這道題也可以采用動(dòng)態(tài)規(guī)劃的方法，但實(shí)際并不如此，考慮這種情況
假如A-B的兩條道路分別為2，3,B-C的兩條道路分別為1，4。如果采用動(dòng)態(tài)規(guī)劃，節(jié)點(diǎn)B的最優(yōu)值為2，節(jié)點(diǎn)C的最優(yōu)值2，但際上到達(dá)C的最優(yōu)值應(yīng)該是0，即3-1這條線路。
也就是說(shuō)，C的最優(yōu)取值不是由B的最優(yōu)取值決定的，其不具有最優(yōu)子結(jié)構(gòu)。
由此可見，并不是所有的“決策問(wèn)題”都可以用“動(dòng)態(tài)規(guī)劃”來(lái)解決。所以，只有當(dāng)一個(gè)問(wèn)題呈現(xiàn)出最優(yōu)子結(jié)構(gòu)時(shí)，“動(dòng)態(tài)規(guī)劃”才可能是一個(gè)合適的侯選方法。
二：無(wú)后效性
即一個(gè)問(wèn)題被劃分階段后，階段I中的狀態(tài)只能由階段I-1中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與其他狀態(tài)沒有關(guān)系，特別是與未發(fā)生的狀態(tài)沒有關(guān)系，這就是無(wú)后效性。
<<<<<<<<<<<<<<<<<<<END>>>>>>>>>>>>>>>>>>
