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

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

3、出的選擇。決策變量 uk（sk）（decision variable）決策集合 Dk（sk）（set of admissible decision）6 6多階段決策過(guò)程及實(shí)例狀態(tài)狀態(tài) s s1 1階段階段1 1決策決策u u1 1狀態(tài)狀態(tài) s s2 2決策決策u u2 2階段階段2 2狀態(tài)狀態(tài) s s3 3.狀態(tài)狀態(tài) s sk k決策決策u uk k階段階段k k狀態(tài)狀態(tài) s sk k+1+1.狀態(tài)狀態(tài) x xn n決策決策u un n階段階段n n狀態(tài)狀態(tài) s sn n+1+17 7動(dòng)態(tài)規(guī)劃的適用范圍動(dòng)態(tài)規(guī)劃的適用范圍動(dòng)態(tài)規(guī)劃用于解決多階段決策最優(yōu)化問(wèn)題，但是不是所有的最優(yōu)化問(wèn)題都可以用動(dòng)態(tài)

4、規(guī)劃解答呢？一般在題目中出現(xiàn)求最優(yōu)解的問(wèn)題就要考慮動(dòng)態(tài)規(guī)劃了，但是否可以用還要滿足兩個(gè)條件：最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）當(dāng)前狀態(tài)是前面狀態(tài)的完美總結(jié)無(wú)后效性什么是無(wú)后效性呢？就是說(shuō)在狀態(tài)i求解時(shí)用到狀態(tài)j而狀態(tài)j就解有用到狀態(tài)k.狀態(tài)N,而求狀態(tài)N時(shí)有用到了狀態(tài)i8 8動(dòng)態(tài)規(guī)劃解決問(wèn)題的一般思路動(dòng)態(tài)規(guī)劃解決問(wèn)題的一般思路(1）模型匹配法：最先考慮的就是這個(gè)方法了。挖掘問(wèn)題的本質(zhì)，如果發(fā)現(xiàn)問(wèn)題是自己熟悉的某個(gè)基本的模型，就直接套用，但要小心其中的一些小的變動(dòng)，現(xiàn)在考題辦都是基本模型的變形套用時(shí)要小心條件，三思而后行。這些基本模型在先面的分類中將一一介紹。(2）三要素法仔細(xì)分析問(wèn)題嘗試著確定動(dòng)態(tài)規(guī)劃的

5、三要素，不同問(wèn)題的卻定方向不同：先確定階段的問(wèn)題：數(shù)塔問(wèn)題，和走路問(wèn)題（詳見(jiàn)解題報(bào)告）先確定狀態(tài)的問(wèn)題：大多數(shù)都是先確定狀態(tài)的。先確定決策的問(wèn)題：背包問(wèn)題。（詳見(jiàn)解題報(bào)告）(3）尋找規(guī)律法(4）邊界條件法找到問(wèn)題的邊界條件，然后考慮邊界條件與它的領(lǐng)接狀態(tài)之間的關(guān)系。這個(gè)方法也很起效。(5）放寬約束和增加約束這個(gè)思想是在陳啟鋒的論文里看到的，具體內(nèi)容就是給問(wèn)題增加一些條件或刪除一些條件使問(wèn)題變的清晰。9 9狀態(tài)是一維的1010例1:攔截導(dǎo)彈某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的

6、高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。問(wèn)題:輸入導(dǎo)彈依次飛來(lái)的高度（389,207,155 ,300 299 ,170 ,158 ,65），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)?1111問(wèn)題分析問(wèn)題分析第一問(wèn)不難看出這是一個(gè)求最長(zhǎng)非升子序列問(wèn)題，顯然標(biāo)準(zhǔn)算法是動(dòng)態(tài)規(guī)劃。對(duì)于第二問(wèn)最直觀的方法就是求完一次opti后把剛才要打的導(dǎo)彈去掉，在求一次opti直到打完所有的導(dǎo)彈，但這樣做就錯(cuò)了。不難舉出反例： 6 1 7 3 2錯(cuò)解： 6 3 2/1/7 正解：6 1/7 3 2認(rèn)真分析

7、一下題就回發(fā)現(xiàn)：每一個(gè)導(dǎo)彈最終的結(jié)果都是要被打的，如果它后面有一個(gè)比它高的導(dǎo)彈，那打它的這個(gè)裝置無(wú)論如何也不能打那個(gè)導(dǎo)彈了，經(jīng)過(guò)這么一分析，這個(gè)問(wèn)題便抽象成在已知序列里找最長(zhǎng)上升序列的問(wèn)題。1212狀態(tài)是二維的所謂二維狀態(tài)就是說(shuō)一般設(shè)計(jì)的狀態(tài)是dpij形式的。那i,j可以代表什么呢?1313(1)i,j組合起來(lái)代表一個(gè)點(diǎn)的坐標(biāo)（顯然是平面坐標(biāo)系）（如：街道問(wèn)題）。(2)i,j組合表示一個(gè)矩陣的單元的位置（第i行，第j列）（如：數(shù)塔問(wèn)題）(3)起點(diǎn)為i長(zhǎng)度為j的區(qū)間。（如：回文詞）(4)起點(diǎn)為i終點(diǎn)為j的區(qū)間。（如：石子合并問(wèn)題）(5)兩個(gè)沒(méi)關(guān)聯(lián)的事物，事物1的第i個(gè)位置，對(duì)應(yīng)事物2的第j個(gè)位置

8、（花店櫥窗設(shè)計(jì)）(6)兩個(gè)序列，第一個(gè)序列的前i個(gè)位置或第i個(gè)位置對(duì)應(yīng)第2個(gè)序列的第j個(gè)位置或前j個(gè)位置。（最長(zhǎng)公共子序列）。(7)其它1414例例2:2:最長(zhǎng)公共子序列最長(zhǎng)公共子序列給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。例如，若X= 和Y= ，則序列是X和Y的一個(gè)公共子序列，序列也是X和Y的一個(gè)公共子序列。而且，后者是X和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閄和Y沒(méi)有長(zhǎng)度大于4的公共子序列。問(wèn)題:給定兩個(gè)序列X= 和Y= ，要求找出X和Y的一個(gè)最長(zhǎng)公共子序列。1515問(wèn)題分析問(wèn)題分析這個(gè)題目的階段很不明顯，所以初看這個(gè)題目沒(méi)什么頭緒，不像前面講

9、的有很明顯的上一步，上一層之類的東西，只是兩個(gè)字符串而且互相沒(méi)什么關(guān)聯(lián)。既然是求公共子序列，也就有第一個(gè)序列的第i個(gè)字符和第二個(gè)序列的第j個(gè)字符相等的情況。那么我們枚第一個(gè)序列（X）的字符，和第二個(gè)序列（Y）的字符。出現(xiàn)兩種情況如果X i , Y j 相等呢?那要是不相等呢？1616狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程If ( X i = Y j ) dp i j = dp i - 1 j - 1 + 1;If( X i != Y j )dp i j = Max( dp i - 1 j , dp i j - 1 );1717例3:回文詞回文詞是一種對(duì)稱的字符串也就是說(shuō)，一個(gè)回文詞，從左到右讀和從右到左讀得

10、到的結(jié)果是一樣的。任意給定一個(gè)字符串，通過(guò)插入若干字符，都可以變成一個(gè)回文詞。你的任務(wù)是寫(xiě)一個(gè)程序，求出將給定字符串變成回文詞所需插入的最少字符數(shù)。(長(zhǎng)度最大5000) 比如字符串“Ab3bd”，在插入兩個(gè)字符后可以變成一個(gè)回文詞（“dAb3bAd”或“Adb3bdA”）。然而，插入兩個(gè)以下的字符無(wú)法使它變成一個(gè)回文詞。1818問(wèn)題分析問(wèn)題分析這個(gè)題目要求出最少填幾個(gè)數(shù)可以使一個(gè)字符串變成回文詞，也就是說(shuō)從任意點(diǎn)截?cái)啵俜D(zhuǎn)后面部分后。兩個(gè)序列有相同的部分不用添字符，不一樣的部分添上字符就可以了這樣就把原問(wèn)題抽象成求最長(zhǎng)公共子序列問(wèn)題了。枚舉截?cái)帱c(diǎn)，把原串截?cái)?，翻轉(zhuǎn)。求最長(zhǎng)公共子序列。答案就是len-（ans*2） len是翻轉(zhuǎn)后兩個(gè)序列的長(zhǎng)度和。Ans 是最長(zhǎng)公共子序列的長(zhǎng)度。其實(shí)這樣求解很麻煩，做了好多重復(fù)的工作。仔細(xì)想想既然在最后求解ans還要乘2那么在先前計(jì)算時(shí)直接把原串翻轉(zhuǎn)作為第二個(gè)序列和第一個(gè)序列求最長(zhǎng)公共子序列就可以了。1919怎么理解這個(gè)優(yōu)化呢？其實(shí)翻轉(zhuǎn)了序列后字符的先后順序就變了，求解最長(zhǎng)公共子序列中得到的解，是唯一的，也就是說(shuō)這個(gè)序列的順序是唯一的，如果在翻轉(zhuǎn)后的序列和原串能得到相同的序列，那么這個(gè)序列在兩個(gè)串中字符間的