動態(tài)規(guī)劃基礎(chǔ)和建模.ppt

1、動態(tài)規(guī)劃基礎(chǔ)和建模,山東省濰坊第一中學(xué) 秦政 clavichord,動態(tài)規(guī)劃是統(tǒng)籌學(xué)的重要內(nèi)容 動態(tài)規(guī)劃是OI的重要內(nèi)容 據(jù)不完全統(tǒng)計，每次考試動態(tài)規(guī)劃起碼有一道題,前言,動態(tài)規(guī)劃很重要 ！,這個課件的目的： 對動態(tài)規(guī)劃的模型進(jìn)行了一些總結(jié) 有部分內(nèi)容超出了NOIP范圍 為同學(xué)們提供一個刷題的方向 請同學(xué)們踴躍發(fā)言,前言,階段 狀態(tài) 決策 狀態(tài)轉(zhuǎn)移 狀態(tài)轉(zhuǎn)移方程,動態(tài)規(guī)劃的基本概念,最優(yōu)子結(jié)構(gòu) 無后效性原則 重疊子問題,動態(tài)規(guī)劃的基本概念,DP是一種記憶化的思想,拓展一下： 階段 - 拓?fù)湫?狀態(tài) - 點 狀態(tài)轉(zhuǎn)移 - 邊 決策 - 前驅(qū)？DFA？,動態(tài)規(guī)劃的基本概念,DP是狀態(tài)空間上的最短（

2、長）路或者可行路,實現(xiàn)方式： 遞推：順推和逆推 記憶化搜索 前者靈活，優(yōu)化方法多 后者可以減少不必要節(jié)點的計算,動態(tài)規(guī)劃的基本概念,時間復(fù)雜度： 狀態(tài)數(shù)*轉(zhuǎn)移費用,動態(tài)規(guī)劃的基本概念,線性模型 區(qū)間模型 矩形模型 樹形模型 背包模型 圖狀模型 SCDP 多線程DP 多重DP 更廣泛的,動態(tài)規(guī)劃的模型,單線問題： 上樓梯問題 LIS問題 烏龜棋 詩人小G（簡化版） 雙線問題： LCS問題 模糊匹配,線性模型,Zbwmqlw神犇要上樓梯，他一次可以上一層，也可以上兩層。 樓梯有n層 有多少種上樓梯的方案,上樓梯問題,N=107？ 設(shè)fi表示到第i層得方案數(shù) 前一步可以上一層也可以上兩層 Fi=fi

3、-1+fi-2 N=1015？ 矩陣乘法,上樓梯問題,給定一個數(shù)列an，求它的一個子序列bm 滿足b1b2b3bm 使得m最大 N=10000,LIS問題,設(shè)fi表示以i結(jié)尾的LIS的長度 Fi=maxfj+1,ji且ajai 時間復(fù)雜度？O(n2) 如何優(yōu)化？,LIS問題,對于i來說，如果存在一個長度為len的LIS以i結(jié)尾，那么也一定存在長度=ai的最大的k Fi=k+1 時間復(fù)雜度O(nlogn),LIS問題,烏龜棋（NOIP2010t）,Fiabcd表示到位置i，四種操作分別進(jìn)行了a,b,c,d次 決策有四種 時間復(fù)雜度：O(nc4) TLE+MLE,烏龜棋,烏龜棋,一首詩包含了若干個

4、句子，對于一些連續(xù)的短句，可以將它們用空格隔開并放在一行中，注意一行中可以放的句子數(shù)目是沒有限制的。小G 給每首詩定義了一個行標(biāo)準(zhǔn)長度（行的長度為一行中符號的總個數(shù)），他希望排版后每行的長度都和行標(biāo)準(zhǔn)長度相差不遠(yuǎn)。顯然排版時，不應(yīng)改變原有的句子順序，并且小 G不允許把一個句子分在兩行或者更多的行內(nèi)。在滿足上面兩個條件的情況下，小G 對于排版中的每行定義了一個不協(xié)調(diào)度, 為這行的實際長度與行標(biāo)準(zhǔn)長度差值絕對值的P 次方，而一個排版的不協(xié)調(diào)度為所有行不協(xié)調(diào)度的總和。 小G 最近又作了幾首詩，現(xiàn)在請你對這首詩進(jìn)行排版，使得排版后的詩盡量協(xié)調(diào)（即不協(xié)調(diào)度盡量小），并把排版的結(jié)果告訴他。,詩人小G（NO

5、I2009）簡化版,Fi表示前i句詩的最小不協(xié)調(diào)度 Fi=minfj+(sumi-sumj+i-j-L)p 時間復(fù)雜度O(n2) 優(yōu)化？ 導(dǎo)數(shù)證明四邊形不等式，有興趣的同學(xué)自己查閱有關(guān)資料,詩人小G,給定兩個字符串s，t 求最長公共字串 例：abcde和ace的LCS是ace N=1000,LCS問題,設(shè)fij表示第一個串到i，第二個串到j(luò)的LCS Fij=fi-1j-1+1, si=tj =minfi-1j,fij-1, si!=tj 時間復(fù)雜度O(n2),LCS問題,給定兩個字符串s和t，每個字符串有英文字母和*？！組成，*？！的含義分別是： *：匹配一個或多個字符； ？：匹配至少一個至多

6、三個字符； ?。浩ヅ渲辽偃齻€字符。 問兩個字符串是否能夠匹配。 N=1000,模糊匹配（POJ1229）,模糊匹配,石子歸并 回文詞 決斗問題 Blocks,區(qū)間模型,有n堆石子，第i堆重ai 每次可以合并相鄰兩堆 合并費用為新堆的重量 求合并成一堆的最小費用 N=200,石子歸并,合并的費用是一段的和 設(shè)fij表示合并i到j(luò)的一段 Fij=minfik+fk+1j+sumij 時間復(fù)雜度O(n3),石子歸并,給定一個字符串s，要求添加最少的字符，使得s成為一個回文串。 N=5000,回文詞（IOI2000）,abcba：回文 abcbc：不回文 Fij表示i到j(luò)變成回文的最小代價 Fij=f

7、i+1j-1, si=sj =minfi+1j,fij-1+1, si!=sj 時間復(fù)雜度O(n2),回文詞,N個人排成一圈，他們要決斗N-1場，其中相鄰的兩人決斗（即第i個人與第i+1個人決斗，第N個人與第1個人決斗），死者退出，最終剩下的人勝利。將任意兩個人之間決斗的輸贏情況告訴你，決斗順序由你安排，問哪些人可能成為最終的勝利者？ N=200,決斗問題（POI99）,首先把環(huán)復(fù)制一份接到后面 然后一個人獲勝就是跟自己相遇 Meetij表示i能j相遇 Meetij=meetik i=costi;j-) gmax(fj,fj-costi+valuei); ,01背包問題,完全背包問題,特點：每

8、類問題有個數(shù)限制ci 基本想法：每類物品的每一個看作一個物品，轉(zhuǎn)化成01背包 代碼： void LimitedPack for(int i=1;i=costi;k-) gmax(fk,fk-costi+valuei); ,多重背包問題,優(yōu)化： 二進(jìn)制拆分 原理：2k能夠表示出02(k+1)-1的所有數(shù) 把ci拆成若干2k相加 O(nmlogc),多重背包問題,特點：物品被分為很多組，每組之間有限制。 假設(shè)限制為：每組只能取一個 Fij=maxfi-1j,fi-1j-wik+vik 代碼： void GroupPack for(int i=1;i=mincosti;j-) for(int k=1

9、;k=cnti;k+) if(costik=j) gmax(fj,fj-costik+valueik; ,分組背包問題,考試的時候合理分配時間是很重要的，我們應(yīng)該在同樣的時間內(nèi)盡量得到更多的分?jǐn)?shù)?，F(xiàn)在有m道題需要在n分鐘內(nèi)解決，每道題分為p個步驟，每道題的每個步驟都會有不同的分值，所需時間也不盡相同。現(xiàn)在你可以從任意一道題的任意一個步驟開始，如果當(dāng)前步驟與上一步驟不連續(xù)，則需要q分鐘的思考時間（每題第一個步驟之前同樣需要思考），請確定自己的策略使得獲得的分?jǐn)?shù)最高。,分配時間（WFTSC2009T）,每道題實際上是一個組。 我們可以發(fā)現(xiàn)，每個步驟選或不選對后面的決策是有影響的，所以我們考慮加一維

10、來區(qū)分。 設(shè)fijk表示前i道題的前j個步驟，其中第i道題的第j個步驟被選，在k分鐘內(nèi)解決的最大得分，gijk表示前i道題的前j個步驟，其中第i道題的第j個步驟不被選，在k分鐘內(nèi)解決的最大得分，那么：,分配時間,分配時間,依賴背包問題，顧名思義，就是一些物品可以選要建立在其它一些物品被選的基礎(chǔ)之上。這類問題往往是建立在樹上的，所以通常也叫樹形背包問題。鑒于在樹形模型中已經(jīng)有了比較詳細(xì)的討論，這里不再詳細(xì)展開,依賴背包問題,泛化物品,void GeneralMatters for(int i=1;i=0;j-) for(int k=0;k=j;k+) gmax(fj,fj-k+cost(i,k)

11、; ,泛化物品,回顧上面的數(shù)值分配型的樹形動態(tài)規(guī)劃，考慮其中的一個節(jié)點i，其子樹就相當(dāng)于一個一個的泛化物品，隨著分配給它們的數(shù)值的變化，其價值也在不斷的變化。由此可見，泛化物品在各個方面都有著很廣泛的應(yīng)用。,泛化物品,環(huán)狀： Naptime 拓?fù)鋱D： 關(guān)鍵路徑 一般圖模型 最優(yōu)貿(mào)易,圖狀模型,找一個位置把環(huán)拆成鏈 DP 把鏈的首尾接成環(huán) 枚舉首狀態(tài),環(huán)狀模型,小F同學(xué)最近特別累，老是想睡覺 小F同學(xué)把一天分為n個時段，選擇不一定連續(xù)的m個時段來睡覺 小F同學(xué)睡眠質(zhì)量不好，每次睡覺要花1個時段來進(jìn)入睡眠 每個時段有一個休息值ai，如果小F同學(xué)選擇在I,j的時段內(nèi)睡覺的話，得到的休息就是ai+1+

12、aj，因為時段i被用來進(jìn)入睡眠了 如何選擇能夠休息的最好？ 注意天與天是連續(xù)的，即這n個時段是一個環(huán),Naptime（POJ2228）,因為環(huán)首尾相接的地方會對結(jié)果產(chǎn)生影響，所以要枚舉開始的狀態(tài)，做幾遍DP 設(shè)fij0表示前i個時間段睡了j段，第i段不睡的最長時間，fij1表示第i段睡的最長時間，那么： fij0=maxfi-1j0,fi-1j1 fij1=maxfi-1j-10,fi-1j-11+ti 初始時，所有的f=-INF 然后枚舉第一個時間段睡不睡，分別使f111=1,f100=1，做兩次DP 內(nèi)存限制比較緊，要滾動,naptime,邊拓?fù)渑判蜻匘P SCC縮點,拓?fù)鋱D模型,給定一個

13、DAG，求從s到t的最長路,關(guān)鍵路徑,設(shè)fi表示從s到i的最長路徑 Fi+disij-fj 拓?fù)渑判虻倪^程中解決,關(guān)鍵路徑,給定一個圖，邊有的是單向的，有的是雙向的 有一個水晶球，每個點有一個價格 從s出發(fā)到t，沿途在某個點買入水晶球，在另一個點賣出 顯然你要先買入才能賣出 最大化收益,最優(yōu)貿(mào)易（NOIP2009T）,方法一： 同一個SCC里的點都可以走到，可以在其中任意一個買，任意一個賣 收縮SCC，記錄SCC的最大值和最小值 Fi表示到i的最大獲利，gi表示到i的最小價格，minvi表示i所在SCC的最小價格，maxvi表示i所在SCC的最大價格 Gi=mingj,minvi Fi=max

14、fj,maxvi-gi 邊拓?fù)渑判蜻呑?最優(yōu)貿(mào)易,方法二： Fi0表示到i點，沒有水晶球的最大 Fi1表示到i點，有水晶球的最大 Fi0=maxfj0,fj1+wi fi1=maxfj1,-wi 前面說過：動態(tài)規(guī)劃是狀態(tài)圖的最短路或最長路 嵌套在SPFA算法中，迭代求解,最優(yōu)貿(mào)易,這類問題在NOIP中一般不會出現(xiàn)，但鑒于在NOIP的模擬題和WFTSC中出現(xiàn)了不止一次，稍微提一下 插頭DP 棋盤DP 集合DP,狀態(tài)壓縮模型,把問題的狀態(tài)壓縮成一個k進(jìn)制數(shù)來表示，利用這個數(shù)的每一位反映出來的信息來進(jìn)行轉(zhuǎn)移 問題規(guī)模往往特別小,狀態(tài)壓縮模型,困惑的旅行家（WFTSC2010T）,經(jīng)典的TSP問題 最

15、優(yōu)哈密頓回路 設(shè)fiS表示當(dāng)前在i點，經(jīng)過的點的集合是S FiS=minfjS-i+disji Ans=minfi2n-1+disi1,困惑的旅行家,多線程動態(tài)規(guī)劃，顧名思義，就是很多條線一起進(jìn)行的動態(tài)規(guī)劃。這類問題要完整的表達(dá)出各條線的特點，轉(zhuǎn)移往往比較簡單。,多線程動態(tài)規(guī)劃,一個公司有三個移動服務(wù)員。如果某個地方有一個請求，某個員工必須趕到那個地方去（那個地方?jīng)]有其他員工），某一時刻只有一個員工能移動。被請求后，他才能移動，不允許在同樣的位置出現(xiàn)兩個員工。從p到q移動一個員工，需要花費c(p,q)。這個函數(shù)沒有必要對稱，但是c(p,p)=0。公司必須滿足所有 的請求。目標(biāo)是最小化公司花費。,Mobile Service（tyvj1061）,Fabc表示三個員工分別在a,b,c位置上 Fabc-fqbc+caq -faqc+cbq -fabq+ccq F123=0,Mobile Service,你贏得了一場航空公司舉辦的比賽，獎品是一張加拿大環(huán)游機(jī)票。旅行在這家航空公司開放的最西邊的城市開始，然后一直自西向東旅行，直到你到達(dá)最東邊的城市，再由東向西返回，直到你回到開始的城市。每個城市只能訪問一次，除了旅行開始的城市之外，這個城市必定要被訪問兩次（在旅行的開始和結(jié)束）。你不允許使用其他公司的航線或者用其他的交通工具。 給出這個航空公司開放的城市的列表，和兩兩城市之間