動態(tài)規(guī)劃時間效率的優(yōu)化

1、動態(tài)規(guī)劃算法時間效率的優(yōu)化福州第三中學 毛子青動態(tài)規(guī)劃算法的時間復雜度二狀態(tài)總數(shù)*每個狀態(tài)轉移的狀態(tài)數(shù)*每次狀態(tài)轉移的時間-、減少狀態(tài)總數(shù)1、改進狀態(tài)表示；（例一）2、其他方法：選取恰當?shù)囊?guī)劃方向等；/1、減少每個狀態(tài)轉移的狀態(tài)數(shù) 1、根據(jù)最優(yōu)解的性質減少決策量；（例二）2、其他方法：利用四邊形不等式證明決策的單調(diào)性等; 、減少狀態(tài)轉移的時間1、減少決策時間（例三）方法：采用恰當?shù)臄?shù)據(jù)結構；2、減少計算遞推式的時間方法：進行預處理，利用計算結果等；例一、 Raucous Rockers 演唱組(USACO96)問題描述現(xiàn)有n首由Raucous Rockers演唱組錄制的歌曲，計劃從中 選擇一些

2、歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音 樂，唱片中的歌曲不能重疊。按下面的標準進行選擇：(1)這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；(2)包含歌曲的總數(shù)盡可能多。I輸入n, m, t,和n首歌曲的長度，它們按照創(chuàng)作順序排序, 沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的 放在唱片中。輸出所能包含的最多的歌曲數(shù)目。設n首歌曲按照創(chuàng)作順序排序后的長度為longl.n,則動態(tài) 規(guī)劃的狀態(tài)表示描述為：gi, j, k, (0in, 0jm, 0klongi, iNl時：gi,j, k=maxgi-l,j,k-longi+l, gi-l,j,k當klongi, iNl時：gi,j,

3、 k=maxgi-l,j-l,t-longi+l, gi-l,j,k規(guī)劃的邊界條件為：當0jm, OSkt時：gO,j,k二0;問題的最優(yōu)解為：gn,m,0 o算法的時間復雜度為：O(n*m*t)。P亍二改進的狀態(tài)表示描述為：gi,j=(a, b), 0in, ji, 0am, 0bt,表示在前i首歌 曲中選取j首錄制亦需的最少唱片另：a張唱片另加b分鐘。 狀態(tài)轉移方程為：gi,j=mingi-l,j, gi-l,j-l+longi 其中(a, b)+longi=(a, b J的計算方法為: 當b+longi t時：a,=a+l; b,=longi; 規(guī)劃的邊界條件：當0W9時,gi90=(0

4、,0)題目所求的最大值是：answer二maxkl gn, k(m-l,t)算法的時間復雜度為：0(昭)。*Back例三、石子合并問題(NOF95)問題描述在一個操場上擺放著一圈口堆石子?，F(xiàn)要將石子有次序地合 并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆， 并將新的一堆的石子數(shù)記為該次合并的得分。試編程求出將n堆石子合并成一堆的最小得分和最大得分以 及相應的合并方案。本例只考慮最大得分。設各堆的石子數(shù)依次為dl.n,則動態(tài)規(guī)劃的狀態(tài)表示為: li,jn,表示合并di.j所得到的最大得分： 令弟d幻,則狀態(tài)轉移方程為：k = i加，刀=max ，+加伙+1,刀+ /匕川ij規(guī)劃的邊界條件

5、為：mi,i=O令si,j=k,表示合并的最優(yōu)斷開位置。算法的時間復雜度為0(2)。合并第i堆到第j堆石子的最優(yōu)斷開位置si,j要么等于i,要么等于j-1, 也就是說最優(yōu)合并方案只可能是：(i) (i+1. j) 或(i.沖 證明：設合并第i堆到第j堆石子的最優(yōu)斷開位置Si,j=p,且iPj-lo情況 1、ti,ptp+l,j由于ip,所以可以設q=si,po于是最優(yōu)合并方案為： (i.q) (q+l.p) (p+l.j) 它的得分 Fmtil+mtq+ljpl+mtp+ljl+ttiJl+tyil我們可以構造如下的合并方案： (i .q) (q+l.p)(p+l.j) 它的得分 F2=mi,

6、q+mq+l,p+mp+lj+ti,j+tq+141由于qvp,所以ti, ptp+1 ,jtq+ l,j所以Ftp+lj與情況1是對稱的。護二狀態(tài)轉移方程優(yōu)化為：mi,j=maxmi+1 ,j, mi,j-l+ti,jij規(guī)劃的邊界條件是：二0算法的時間復雜度0(n2)o例三、LOSTCITY (NOF2000)問題描述現(xiàn)給出一張單詞表、特定的語法規(guī)則和一篇文章：文章和單詞表中只含26個小寫英文字母a.zo單詞表中的單詞只有名詞，動詞和輔詞這三種詞性，且相同詞 性的單詞互不相同。單詞的個數(shù)不超過1000,單詞的長度均不 超過20。語法規(guī)則可簡述為：名詞短語：任意個輔詞前綴接上一個名詞; 動詞短語：任意個輔詞前綴接上一個動詞；句子：以名詞短語 開頭，名詞短語與動詞短語相間連接而成。文章的長度不超過5k。且已知文章是由有限個句子組成的，句 子只包含有限個單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分 出的單詞數(shù)最少。=；+十產(chǎn)采用不同的方法查找字符串的比較：設單詞表的規(guī)模為N （N的最大值為1000）設文章的長度為M （M的最大值為5000）順序查找二分查找哈希表檢索樹算法的時間 復雜度O(20*M*N)O(20*M*log2N)O(20*M