動態(tài)規(guī)劃與遞推

1、動態(tài)規(guī)劃與遞推動態(tài)規(guī)劃是最優(yōu)化算法 動態(tài)規(guī)劃的實質(zhì)是分治和解決冗余，因此動態(tài)規(guī)劃也是遞歸思想的應(yīng)用 之一。但是，動態(tài)規(guī)劃和遞歸法還是有區(qū)別的。一般我們在實際應(yīng)用中 遇到的問題主要分為四類：判定性問題、構(gòu)造性問題、計數(shù)問題和最優(yōu) 化問題。動態(tài)規(guī)劃是解決最優(yōu)化問題的有效途徑，而遞推法在處理判定 性問題和計數(shù)問題方面是一把利器。下面分別就兩個例子，談一下遞推 法和動態(tài)規(guī)劃在這兩個方面的聯(lián)系。例13模四最優(yōu)路徑問題在下圖中找出從第1點到第4點的一條路徑，要求路徑長度mod 4的余 數(shù)最小。這個圖是一個多段圖，而且是一個特殊的多段圖。雖然這個圖的形式比 一般的多段圖要簡單，但是這個最優(yōu)路徑問題卻不能用動

2、態(tài)規(guī)劃來做。 因為一條從第1點到第4點的最優(yōu)路徑，在它走到第2點、第3點時， 路徑長度mod 4的余數(shù)不一定是最小，也就是說最優(yōu)策略的子策略不一 定最優(yōu)一一這個問題不滿足最優(yōu)化原理但是我們可以把它轉(zhuǎn)換成判定性問題，用遞推法來解決。判斷從第1點 到第k點的長度mod 4為sk的路徑是否存在，用fk(sk)來表示，則遞推 公式如下：邊界條件為I及項我-新句皿14)A伉)=茂從攻-知JU)郵M 六凱一屁燈)成血)這里lenkj表示從第k-1點到第k點之間的第i條邊的長度，方括號表示 “或(or)”運算。最后的結(jié)果就是可以使f4(s4)值為真的最小的s4值。這個遞推法的遞推公式和動態(tài)規(guī)劃的規(guī)劃方程非常

3、相似，我們在這里借 用了動態(tài)規(guī)劃的符號也就是為了更清楚地顯示這一點。其實它們的思想 也是非常相像的，可以說是遞推法借用了動態(tài)規(guī)劃的思想解決了動態(tài)規(guī) 劃不能解決的問題。有的多階段決策問題(像這一題的階段特征就很明顯)，由于不能滿足 最優(yōu)化原理等使用動態(tài)規(guī)劃的先決條件，而無法應(yīng)用動態(tài)規(guī)劃。在這時 可以將最優(yōu)指標(biāo)函數(shù)的值當(dāng)作“狀態(tài)”放到下標(biāo)中去，從而變最優(yōu)化問題 為判定性問題，再借用動態(tài)規(guī)劃的思想，用遞推法來解決問題。例14釘子與小球(NOI99)有一個三角形木板，豎直立放，上面釘著n(n+1)/2顆釘子，還有(n+1)個 格子(當(dāng)n=5時如下圖a)。每顆釘子和周圍的釘子的距離都等于d， 每個格子的

4、寬度也都等于d，且除了最左端和最右端的格子外每個格子 都正對著最下面一排釘子的間隙。讓一個直徑略小于d的小球中心正對著最上面的釘子在板上自由滾落， 小球每碰到一個釘子都可能落向左邊或右邊（概率各1/2），且球的中 心還會正對著下一顆將要碰上的釘子。例如圖b就是小球一條可能的路 徑。我們知道小球落在第i個格子中的概率為：時川一。!其中i為格子的編號，從左至右依次為0,1,.,n?，F(xiàn)在的問題是計算拔掉某些釘子后，小球落在編號為m的格子中的概 率pm。假定最下面一排釘子不會被拔掉。例如圖3是某些釘子被拔掉 后小球一條可能的路徑。圖a圖b圖c輸入：第 1 行為整數(shù) n（2=n=50）和 m（0=m=n

5、）。以下n行依次為木板上從上至下n行釘子的信息，每行中 *，表示釘子 還在， .，表示釘子被拔去，注意在這口行中空格符可能出現(xiàn)在任何位 置。輸出: 僅一行，是一個既約分?jǐn)?shù)（0寫成0/1）,為小球落在編號為m的格子中的 概率Pm。既約分?jǐn)?shù)的定義：A/B是既約分?jǐn)?shù)，當(dāng)且僅當(dāng)A、B為正整數(shù)且A和B 沒有大于1的公因子。樣例輸入：5 2* TOC o 1-5 h z .* *. * * * * *樣例輸出：7/16這個題目一看就不覺讓人想起一道經(jīng)典的動態(tài)規(guī)劃題。下面先讓我們回 顧一下這個問題。例15數(shù)字三角形（IOI94）在下圖中求從頂至低某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最 大，每一步只能向

6、左下或右下走。 TOC o 1-5 h z 810274445265在這個問題中，我們按走過的行數(shù)來劃分階段，以走到每一行時所在的 位置來作為狀態(tài)，決策就是向左下走(用0表示)或向右下走(用1表 示)。狀態(tài)轉(zhuǎn)移方程：況T =其廠電規(guī)劃方程：心如1邊界條件：(0) = 0兒世+ 1) = 0, 0總行數(shù)這是一個比較簡單的最優(yōu)化問題，我們還可以把這個問題改成一個更加 簡單的整數(shù)統(tǒng)計問題：求頂點到每一點的路徑總數(shù)。把這個總數(shù)用fk(xk) 表示，那么遞推公式就是：在這里，雖然求和公式只有兩項，但我們?nèi)匀挥媚切问奖硎荆褪菫?了突出這個遞推公式和上面的規(guī)劃方程的相似之處。這兩個公式的邊界 條件都是一模一樣的。再回到我們上面的“釘子與小球”問題，這是一個概率統(tǒng)計問題。我們繼 續(xù)沿用上面的思想，用fk(xk)表示小球落到第k行第xk個釘子上的概率， 則遞推公式如下：這里函數(shù)Existk(xk)表示第k行第xk個釘子是否存在，存在則取1，不存 在則取0；邊界條件0) 二 1職T 二。i總行數(shù)可以看出這個公式較之上面的兩個式子雖然略有變化，但是其基本思想 還是類似的。在解這個問題的過程中，我們再次運