dp浙江大學周楊濤教授PPT課件

1、1,什么是動態(tài)規(guī)劃,動態(tài)規(guī)劃是解決某一類問題的一種方法，是分析問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因此，在學習動態(tài)規(guī)劃時，除了對基本概念和方法正確地理解外，應以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解,2,動態(tài)規(guī)劃三要素：階段，狀態(tài)，決策,1、階段（stage） 把所給問題恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，通常根據(jù)時間順序或空間特征來劃分，以便按階段的次序逐段解決整個過程的優(yōu)化問題。 描述階段的變量叫作階段變量，階段變量通常用k表示（k = 1，2，3，n,3,動態(tài)規(guī)劃三要素：階段，狀態(tài)，決策,2、狀態(tài)（state） 用以描述事物(或系統(tǒng))在某特定的時間與

2、空間域中所處位置及運動特征的量，稱為狀態(tài)。它應能描述過程的特征并具有“無后效性”，又稱馬爾柯夫性，是指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。 狀態(tài)變量 sk（state variable） 狀態(tài)集合 Sk（set of admissible states,4,動態(tài)規(guī)劃三要素：階段，狀態(tài)，決策,3、決策（decision） 決策：確定系統(tǒng)過程發(fā)展的方案。 決策的實質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。 決策變量 uk（sk）（decision variable） 決策集合 Dk（sk）（set

3、 of admissible decision,5,多階段決策過程及實例,6,動態(tài)規(guī)劃的適用范圍,動態(tài)規(guī)劃用于解決多階段決策最優(yōu)化問題，但是不是所有的最優(yōu)化問題都可以用動態(tài)規(guī)劃解答呢？ 一般在題目中出現(xiàn)求最優(yōu)解的問題就要考慮動態(tài)規(guī)劃了，但是否可以用還要滿足兩個條件： 最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理） 當前狀態(tài)是前面狀態(tài)的完美總結(jié) 無后效性 什么是無后效性呢？ 就是說在狀態(tài)i求解時用到狀態(tài)j而狀態(tài)j就解有用到狀態(tài)k.狀態(tài)N,而求狀態(tài)N時有用到了狀態(tài)i,7,動態(tài)規(guī)劃解決問題的一般思路,1）模型匹配法： 最先考慮的就是這個方法了。挖掘問題的本質(zhì)，如果發(fā)現(xiàn)問題是自己熟悉的某個基本的模型，就直接套用，但要小心其

4、中的一些小的變動，現(xiàn)在考題辦都是基本模型的變形套用時要小心條件，三思而后行。這些基本模型在先面的分類中將一一介紹。 (2）三要素法 仔細分析問題嘗試著確定動態(tài)規(guī)劃的三要素，不同問題的卻定方向不同： 先確定階段的問題：數(shù)塔問題，和走路問題（詳見解題報告） 先確定狀態(tài)的問題：大多數(shù)都是先確定狀態(tài)的。 先確定決策的問題：背包問題。（詳見解題報告） (3）尋找規(guī)律法 (4）邊界條件法 找到問題的邊界條件，然后考慮邊界條件與它的領(lǐng)接狀態(tài)之間的關(guān)系。這個方法也很起效。 (5）放寬約束和增加約束 這個思想是在陳啟鋒的論文里看到的，具體內(nèi)容就是給問題增加一些條件或刪除一些條件使問題變的清晰,8,狀態(tài)是一維的,

5、9,例1:攔截導彈,某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。 問題:輸入導彈依次飛來的高度（389,207,155 ,300 299 ,170 ,158 ,65），計算這套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng),10,問題分析,第一問不難看出這是一個求最長非升子序列問題，顯然標準算法是動態(tài)規(guī)劃。 對于第二問最直觀的方法就是求完一次op

6、ti后把剛才要打的導彈去掉，在求一次opti直到打完所有的導彈，但這樣做就錯了。 不難舉出反例： 6 1 7 3 2 錯解： 6 3 2/1/7 正解：6 1/7 3 2 認真分析一下題就回發(fā)現(xiàn)：每一個導彈最終的結(jié)果都是要被打的，如果它后面有一個比它高的導彈，那打它的這個裝置無論如何也不能打那個導彈了，經(jīng)過這么一分析，這個問題便抽象成在已知序列里找最長上升序列的問題,11,狀態(tài)是二維的,所謂二維狀態(tài)就是說一般設計的狀態(tài)是dpij形式的。那i,j可以代表什么呢,12,1)i,j組合起來代表一個點的坐標（顯然是平面坐標系）（如：街道問題）。 (2)i,j組合表示一個矩陣的單元的位置（第i行，第j列

7、）（如：數(shù)塔問題） (3)起點為i長度為j的區(qū)間。（如：回文詞） (4)起點為i終點為j的區(qū)間。（如：石子合并問題） (5)兩個沒關(guān)聯(lián)的事物，事物1的第i個位置，對應事物2的第j個位置（花店櫥窗設計） (6)兩個序列，第一個序列的前i個位置或第i個位置對應第2個序列的第j個位置或前j個位置。（最長公共子序列）。 (7)其它,13,例2:最長公共子序列,給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X= 和Y= ，則序列是X和Y的一個公共子序列，序列也是X和Y的一個公共子序列。而且，后者是X和Y的一個最長公共子序列，因為X和Y沒有長度大于4

8、的公共子序列。 問題:給定兩個序列X= 和Y= ，要求找出X和Y的一個最長公共子序列,14,問題分析,這個題目的階段很不明顯，所以初看這個題目沒什么頭緒，不像前面講的有很明顯的上一步，上一層之類的東西，只是兩個字符串而且互相沒什么關(guān)聯(lián)。 既然是求公共子序列，也就有第一個序列的第i個字符和第二個序列的第j個字符相等的情況。那么我們枚第一個序列（X）的字符，和第二個序列（Y）的字符。 出現(xiàn)兩種情況 如果X i , Y j 相等呢? 那要是不相等呢,15,狀態(tài)轉(zhuǎn)移方程,If ( X i = Y j ) dp i j = dp i - 1 j - 1 + 1; If( X i != Y j ) dp

9、i j = Max( dp i - 1 j , dp i j - 1,16,例3:回文詞回文詞是一種對稱的字符串也就是說，一個回文詞，從左到右讀和從右到左讀得到的結(jié)果是一樣的。任意給定一個字符串，通過插入若干字符，都可以變成一個回文詞。你的任務是寫一個程序，求出將給定字符串變成回文詞所需插入的最少字符數(shù)。(長度最大5000) 比如字符串“Ab3bd”，在插入兩個字符后可以變成一個回文詞（“dAb3bAd”或“Adb3bdA”）。然而，插入兩個以下的字符無法使它變成一個回文詞,17,問題分析,這個題目要求出最少填幾個數(shù)可以使一個字符串變成回文詞，也就是說從任意點截斷，再翻轉(zhuǎn)后面部分后。兩個序列有

10、相同的部分不用添字符，不一樣的部分添上字符就可以了 這樣就把原問題抽象成求最長公共子序列問題了。枚舉截斷點，把原串截斷，翻轉(zhuǎn)。求最長公共子序列。答案就是len-（ans*2） len是翻轉(zhuǎn)后兩個序列的長度和。Ans 是最長公共子序列的長度。 其實這樣求解很麻煩，做了好多重復的工作。仔細想想既然在最后求解ans還要乘2那么在先前計算時直接把原串翻轉(zhuǎn)作為第二個序列和第一個序列求最長公共子序列就可以了,18,怎么理解這個優(yōu)化呢？ 其實翻轉(zhuǎn)了序列后字符的先后順序就變了，求解最長公共子序列中得到的解，是唯一的，也就是說這個序列的順序是唯一的，如果在翻轉(zhuǎn)后的序列和原串能得到相同的序列，那么這個序列在兩個串中字符間的順序是橫定的，著就滿足了回文詞的定義