【正文】 第九章 動態(tài)規(guī)劃 第一節(jié) 動態(tài)規(guī)劃的基本模型 第二節(jié) 動態(tài)規(guī)劃與遞推 第三節(jié) 歷屆 NOIP動態(tài)規(guī)劃試題 第四節(jié) 背包問題 第五節(jié) 動態(tài)規(guī)劃應用舉例 動態(tài)規(guī)劃程序設計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計算那樣，具有一個標準的數(shù)學表達式和明確清晰的解題方法。動態(tài)規(guī)劃程序設計往往是針對一種最優(yōu)化問題，由于各種問題的性質不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行分析、討論，逐漸學會并掌握這一設計方法。 第一節(jié) 動態(tài)規(guī)劃的基本模型 ? 多階段決策過程的最優(yōu)化問題 在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。當然，各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展，當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，這種把一個問題看作是一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。如下圖所示： 多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯(lián)系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列。要使整個活動的總體效果達到最優(yōu)的問題，稱為多階段決策問題。 【 例 1】 最短路徑問題。 下圖給出了一個地圖，地圖中的每個頂點代表一個城市，兩個城市間的一條連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在想從城市 A到達城市 E，怎樣走路程最短？最短路程的長度是多少？ 【 算法分析 】 把 A到 E的全過程分成四個階段，用 K表示階段變量，第 1階段有一個初始狀態(tài) A，有兩條可供選擇的支路 AB AB2；第 2階段有兩個初始狀態(tài) BB2， B1有三條可供選擇的支路， B2有兩條可供選擇的支路 …… 。用 DK（ XI，X+1J）表示在第 K階段由初始狀態(tài) XI到下階段的初始狀態(tài) X+1J的路徑距離，F(xiàn)K（ XI）表示從第 K階段的 XI到終點 E的最短距離，利用倒推的方法，求解 A到 E的最短距離。 具體計算過程如下： S1： K = 4 有 F4（ D1） = 3， F4（ D2） = 4， F4（ D3） = 3； S2： K = 3 有 F3（ C1） = MIN{ D3（ C1， D1） + F4（ D1）， D3（ C1， D2） + F4（ D2） } = MIN{ 5+3， 6+4 } = 8 F3（ C2） = D3（ C2， D1） + F4（ D1） = 5+3 = 8 F3（ C3） = D3（ C3， D3） + F4（ D3） = 8+3 = 11 F3（ C4） = D3（ C4， D3） + F4（ D3） = 3+3 = 6 S3： K = 2 有 F2（ B1） = MIN{ D2（ B1， C1） + F3（ C1）， D2（ B1， C2） + F3（ C2）， D2（ B1， C3） + F3(C3)} = MIN{ 1+8,6+8,3+11} = 9 F2（ B2） = MIN{ D2（ B2， C2） + F3（ C2）， D2（ B2， C4） + F3（ C4） } = MIN{ 8+8， 4+6 } = 10 S4： K = 1 有 F1（ A） = MIN{ D1（ A， B1） + F2（ B1）， D1（ A， B2） + F2（ B2） } = MIN{ 5+9， 3+10} = 13 因此由 A點到 E點的全過程最短路徑為 A→B2→C4→D3→E ；最短路程長度為 13。 從以上過程可以看出，每個階段中，都求出本階段的各個初始狀態(tài)到終點 E的最短距離，當逆序倒推到過程起點 A時，便得到了全過程的最短路徑和最短距離。 在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃程序設計方法。 ? 動態(tài)規(guī)劃的基本概念和基本模型構成 現(xiàn)在我們來介紹動態(tài)規(guī)劃的基本概念。 1. 階段和階段變量： 用動態(tài)規(guī)劃求解一個問題時，需要將問題的全過程恰當?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用 K表示，階段的劃分一般是根據(jù)時間和空間的自然特征來劃分，同時階段的劃分要便于把問題轉化成多階段決策過程，如例題 1中，可將其劃分成 4個階段，即 K = 1， 2， 3， 4。 2. 狀態(tài)和狀態(tài)變量： 某一階段的出發(fā)位置稱為狀態(tài)，通常一個階段包含若干狀態(tài)。一般地，狀態(tài)可由變量來描述，用來描述狀態(tài)的變量稱為狀態(tài)變量。如例題 1中， C3是一個狀態(tài)變量。 3. 決策、決策變量和決策允許集合： 在對問題的處理中作出的每種選擇性的行動就是決策。即從該階段的每一個狀態(tài)出發(fā)，通過一次選擇性的行動轉移至下一階段的相應狀態(tài)。一個實際問題可能要有多次決策和多個決策點，在每一個階段的每一個狀態(tài)中都需要有一次決策，決策也可以用變量來描述，稱這種變量為決策變量。在實際問題中，決策變量的取值往往限制在某一個范圍之內，此范圍稱為允許決策集合。如例題 1中， F3（ C3）就是一個決策變量。 4．策略和最優(yōu)策略： 所有階段依次排列構成問題的全過程。全過程中各階段決策變量所組成的有序總體稱為策略。在實際問題中，從決策允許集合中找出最優(yōu)效果的策略成為最優(yōu)策略。 5. 狀態(tài)轉移方程 前一階段的終點就是后一階段的起點，對前一階段的狀態(tài)作出某種決策，產(chǎn)生后一階段的狀態(tài)，這種關系描述了由 k階段到 k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉移方程。 ? 最優(yōu)化原理與無后效性 上面已經(jīng)介紹了動態(tài)規(guī)劃模型的基本組成，現(xiàn)在需要解決的問題是：什么樣的“多階段決策問題”才可以采用動態(tài)規(guī)劃的方法求解。 一般來說，能夠采用動態(tài)規(guī)劃方法求解的問題，必須滿足最優(yōu)化原理和無后效性原則： 動態(tài)規(guī)劃的最優(yōu)化原理。作為整個過程的最優(yōu)策略具有：無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略的性質。也可以通俗地理解為子問題的局部最優(yōu)將導致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結構的性質，也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，而非最優(yōu)解對問題的求解沒有影響。在例題 1最短路徑問題中， A到 E的最優(yōu)路徑上的任一點到終點 E的路徑，也必然是該點到終點 E的一條最優(yōu)路徑，即整體優(yōu)化可以分解為若干個局部優(yōu)化。 動態(tài)規(guī)劃的無后效性原則。所謂無后效性原則，指的是這樣一種性質：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。也就是說，“未來與過去無關”，當前的狀態(tài)是此前歷史的一個完整的總結，此前的歷史只能通過當前的狀態(tài)去影響過程未來的演變。在例題 1最短路徑問題中，問題被劃分成各個階段之后，階段 K中的狀態(tài)只能由階段 K+1中的狀態(tài)通過狀態(tài)轉移方程得來，與其它狀態(tài)沒有關系，特別與未發(fā)生的狀態(tài)沒有關系，例如從 Ci到 E的最短路徑，只與 Ci的位置有關，它是由 Di中的狀態(tài)通過狀態(tài)轉移方程得來，與 E狀態(tài)，特別是 A到 Ci的路徑選擇無關，這就是無后效性。 由此可見，對于不能劃分階段的問題，不能運用動態(tài)規(guī)劃來解；對于能劃分階段，但不符合最優(yōu)化原理的，也不能用動態(tài)規(guī)劃來解；既能劃分階段，又符合最優(yōu)化原理的，但不具備無后效性原則，還是不能用動態(tài)規(guī)劃來解；誤用動態(tài)規(guī)劃程序設計方法求解會導致錯誤的結果。 ? 動態(tài)規(guī)劃設計方法的一般模式 動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結束狀態(tài)；或倒過來，從結束狀態(tài)開始，通過對中間階段決策的選擇，達到初始狀態(tài)。這些決策形成一個決策序列，同時確定了完成整個過程的一條活動路線，通常是求最優(yōu)活動路線。 動態(tài)規(guī)劃的設計都有著一定的模式，一般要經(jīng)歷以下幾個步驟： 劃分階段 按照問題的時間或空間特征，把問題劃分為若干個階段。在劃分階段時，注意劃分后的階段一定是有序的或者是可排序的，否則問題就無法求解。 確定狀態(tài)和狀態(tài)變量 將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。 確定決策并寫出狀態(tài)轉移方程 因為決策和狀態(tài)轉移有著天然的聯(lián)系，狀態(tài)轉移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉移方程也就可以寫出。但事實上常常是反過來做，根據(jù)相鄰兩段的各個狀態(tài)之間的關系來確定決策。 尋找邊界條件 給出的狀態(tài)轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。 【 例 1】 對應的 Pascal程序如下： var d : array[1..4,1..4,1..4] of integer。 f : array[1..5,1..4] of integer。 i,j,k,min : integer。 begin fillchar(d,sizeof(d),0)。 d[1,1,1] := 5。 d[1,1,2] := 3。 d[2,1,1] := 1。 d[2,1,2] := 6。 d[2,1,3] := 3。 d[2,2,2] := 8。 d[2,2,4] := 4。 d[3,1,1] := 5。 d[3,1,2] := 6。 d[3,2,1] := 5。 d[3,3,3] := 8。 d[3,4,3] := 3。 d[4,1,1] := 3。 d[4,2,1] := 4。 d[4,3,1] := 3。 fillchar(f,sizeof(f),255)。 f[5,1] := 0。 for i := 4 downto 1 do for j := 1 to 4 do for k := 1 to 4 do if d[i,j,k] 0 then if f[i,j] d[i,j,k]+f[i+1,k] then f[i,j] := d[i,j,k]+f[i+1,k]。 writeln(f[1,1])。 readln。 end. 第二節(jié) 動態(tài)規(guī)劃與遞推 —— 動態(tài)規(guī)劃是最優(yōu)化算法 由于動態(tài)規(guī)劃的“名氣”如此之大，以至于很多人甚至一些資料書上都往往把一種與動態(tài)規(guī)劃十分相似的算法，當作是動態(tài)規(guī)劃。這種算法就是遞推。實際上，這兩種算法還是很容易區(qū)分的。 按解題的目標來分，信息學試題主要分四類：判定性問題、構造性問題、計數(shù)問題和最優(yōu)化問題。我們在競賽中碰到的大多是最優(yōu)化問題，而動態(tài)規(guī)劃正是解決最優(yōu)化問題的有力武器，因此動態(tài)規(guī)劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數(shù)問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態(tài)規(guī)劃在這兩個方面的聯(lián)系。 【 例 2】 數(shù)塔問題（ IOI94） 有形如圖所示的數(shù)塔，從頂部出發(fā)，在每一結點可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。 這道題如果用枚舉法，在數(shù)塔層數(shù)稍大的情況下（如 40），則需要列舉出的路徑條數(shù)將是一個非常龐大的數(shù)目。如果用貪心法又往往得不到最優(yōu)解。在用動態(tài)規(guī)劃考慮數(shù)塔問題時可以自頂向下的分析，自底向上的計算。從頂點出發(fā)時到底向左走還是向右走應取決于是從左走能取到最大值還是從右走能取到最大值，只要 左右兩道路徑上的最大值求出來了才能作出決策。同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。所以實際求解時，可從底層開始，層層遞進，最后得到最大值。實際求解時應掌握其編程的一般規(guī)律，通常需要哪幾個關鍵數(shù)組來存儲變化過程這一點非常重要。 一般說來，很多最優(yōu)化問題都有著對應的計數(shù)問題；反過來，很多計數(shù)問題也有著對應的最優(yōu)化問題。因此，我們在遇到這兩類問題時，不妨多聯(lián)系、