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

1、動態(tài)規(guī)劃算法時間效率的優(yōu)化,福州第三中學(xué) 毛子青,動態(tài)規(guī)劃算法的時間復(fù)雜度= 狀態(tài)總數(shù)*每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)*每次狀態(tài)轉(zhuǎn)移的時間,一、減少狀態(tài)總數(shù)二、減少每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)三、減少狀態(tài)轉(zhuǎn)移的時間,1、改進(jìn)狀態(tài)表示；（例一）,1、減少決策時間 （例三）,方法：采用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；,2、減少計算遞推式的時間,方法：進(jìn)行預(yù)處理，利用計算結(jié)果等；,2、其他方法：選取恰當(dāng)?shù)囊?guī)劃方向等；,1、根據(jù)最優(yōu)解的性質(zhì)

2、減少決策量；（例二）,2、其他方法：利用四邊形不等式證明決策的單調(diào)性等；,例一、   Raucous Rockers 演唱組（USACO`96）[問題描述] 現(xiàn)有n首由Raucous Rockers 演唱組錄制的歌曲，計劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進(jìn)行選擇：   (1) 這組唱片中的歌曲必須按照它們

3、創(chuàng)作的順序排序； (2) 包含歌曲的總數(shù)盡可能多。 輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。,設(shè)n首歌曲按照創(chuàng)作順序排序后的長度為long[1..n]，則動態(tài)規(guī)劃的狀態(tài)表示描述為： g[i, j, k]，(0≤i≤n，0≤j≤m，0≤k<t), 表示前i首歌曲，用j張唱片另加k分鐘來

4、錄制，最多可以錄制的歌曲數(shù)目。狀態(tài)轉(zhuǎn)移方程為：當(dāng)k≥long[i]，i≥1時：g[i, j, k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}當(dāng)k<long[i]，i≥1時：g[i, j, k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}規(guī)劃的邊界條件為：當(dāng)0≤j≤m， 0≤k<t時：g[0,j,k]=0;問題的最優(yōu)解為：g[n,m,0]。,算法

5、的時間復(fù)雜度為：O(n*m*t)。,改進(jìn)的狀態(tài)表示描述為： g[i,j]=(a, b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中選取j首錄制所需的最少唱片為：a張唱片另加b分鐘。狀態(tài)轉(zhuǎn)移方程為：g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long[i]} 其中(a, b)+long[i]=(a’, b’)的計算方法為：當(dāng)b+long[i] ≤t時： a’=a;

6、b’=b+long[i];當(dāng)b+long[i] ＞t時： a’=a+1; b’=long[i];規(guī)劃的邊界條件：當(dāng)0≤i≤n時，g[i,0]=(0,0) 題目所求的最大值是：answer=max{k| g[n, k]≤(m-1,t)},算法的時間復(fù)雜度為：O(n2)。,Back,例三、石子合并問題(NOI`95)[問題描述] 在一個操場上擺放著一圈n堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆

7、石子合并成新的一堆，并將新的一堆的石子數(shù)記為該次合并的得分。 試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。 本例只考慮最大得分。,i<j,規(guī)劃的邊界條件為：m[i,i]=0 令s[i,j]=k，表示合并的最優(yōu)斷開位置。 算法的時間復(fù)雜度為O(n3)。,設(shè)各堆的石子數(shù)依次為d[1..n]，則動態(tài)規(guī)劃的狀態(tài)表示為： m[i,j]，1≤i, j≤n，表示合并d[i..j]所得到的

8、最大得分：令 ，則狀態(tài)轉(zhuǎn)移方程為：,合并第i堆到第j堆石子的最優(yōu)斷開位置s[i,j]要么等于i，要么等于j-1，也就是說最優(yōu)合并方案只可能是： { (i) (i+1… j) } 或 { (i… j-1) (j) },證明：設(shè)合并第i堆到第j堆石子的最優(yōu)斷開位置 s[i,j]=p，且it[p+1,j] 與情況1是對稱的。,狀態(tài)轉(zhuǎn)移方程優(yōu)化為：m[i,j]=max{m[i+1,

9、j], m[i,j-1]}+t[i,j] i<j規(guī)劃的邊界條件是： m[i,i]=0算法的時間復(fù)雜度O(n2)。,Back,例三、LOSTCITY (NOI`2000)[問題描述] 現(xiàn)給出一張單詞表、特定的語法規(guī)則和一篇文章：文章和單詞表中只含26個小寫英文字母a…z。單詞表中的單詞只有名詞，動詞和輔詞這三種詞性，且相同詞性的單詞互不相同。單詞的個數(shù)不超過1000，單詞的長度均不超過20。語法規(guī)則

10、可簡述為：名詞短語：任意個輔詞前綴接上一個名詞；動詞短語：任意個輔詞前綴接上一個動詞；句子：以名詞短語開頭，名詞短語與動詞短語相間連接而成。文章的長度不超過5k。且已知文章是由有限個句子組成的，句子只包含有限個單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。,我們分別用v,u,a表示動詞，名詞和輔詞，給出的文章用L[1..M]表示，則狀態(tài)表示描述為：F(v,i)：表示將L的前i個字符劃分為以動詞結(jié)尾（當(dāng)

11、iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)；F(u,i)：表示將L的前i個字符劃分為以名詞結(jié)尾（當(dāng)iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)。狀態(tài)轉(zhuǎn)移方程為：F(v,i)=min{ F(u,j)+(0,1)， L(j+1..i)為動詞； F(v,j)+(0,1)， L(j+1..i)為輔詞，iM；}F(u,i)=min{ F(u,j)+(1,1)

12、, L(j+1..i)為名詞； F(v,j)+(0,1), L(j+1..i)為名詞； F(u,j)+(0,1), L(j+1..i)為輔詞，iM；}邊界條件：F(v,0)=(1,0)； F(u,0)=(∞, ∞)；問題的解為：min{ F(v,M), F(u,M) }；,Back,采用不同的方法查找字符串的比較： 設(shè)單詞表的規(guī)模