8/8動態(tài)規(guī)劃算法的優(yōu)化技巧動態(tài)規(guī)劃算法的優(yōu)化技巧

福州第三中學(xué)毛子青

[關(guān)鍵詞]動態(tài)規(guī)劃、時間復(fù)雜度、優(yōu)化、狀態(tài)

[

1、改進狀態(tài)表示

狀態(tài)的規(guī)模與狀態(tài)表示的方法密切相關(guān)，通過改進狀態(tài)表示減小狀態(tài)總數(shù)是應(yīng)用較為普遍的一種方法。

例一、RaucousRockers演唱組（USACO`96）

[問題描述]

現(xiàn)有n首由RaucousRockers演唱組錄制的珍貴的歌曲，計劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進行選擇：

（1）這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；

（2）包含歌曲的總數(shù)盡可能多。

輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。

（1≤n,m,t≤20）

[算法分析]

本題要求唱片中的歌曲必須按照它們創(chuàng)作順序排序，這就滿足了動態(tài)規(guī)劃的無后效性要求，啟發(fā)我們采用動態(tài)規(guī)劃進行解題。

分析可知，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即：設(shè)最優(yōu)錄制方案中第i首歌錄制的位置是從第j張唱片的第k分鐘開始的，那么前j-1張唱片和第j張唱片的前k-1分鐘是前1..i-1首歌的最優(yōu)錄制方案，也就是說，問題的最優(yōu)解包含了子問題的最優(yōu)解。

設(shè)n首歌曲按照寫作順序排序后的長度為long[1..n]，則動態(tài)規(guī)劃的狀態(tài)表示描述為：g[i,j,k]，0≤i≤n，0≤j≤m，0≤kt-b時：a’=a+1;b’=long[i];

規(guī)劃的邊界條件：

g[i,0]=(0,0)0≤i≤n

這樣題目所求的最大值是：ans=max{k|g[n,k]≤(m-1,t)}

改進后的算法，狀態(tài)總數(shù)為O(n2)，每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(1)，每次狀態(tài)轉(zhuǎn)移的時間為O(1)，所以總的時間復(fù)雜度為O(n2)。值得注意的是，算法的空間復(fù)雜度也由改進前的O(m*n*t)降至優(yōu)化后的O(n2)。

（程序及優(yōu)化前后的運行結(jié)果比較見附件）

通過對本題的優(yōu)化，我們認(rèn)識到：應(yīng)用不同的狀態(tài)表示方法設(shè)計出的動態(tài)規(guī)劃算法的性能也迥然不同。改進狀態(tài)表示可以減少狀態(tài)總數(shù)，進而降低算法的時間復(fù)雜度。在降低算法的時間復(fù)雜度的同時，也降低了算法的空間復(fù)雜度。因此，減少狀態(tài)總數(shù)在動態(tài)規(guī)劃的優(yōu)化中占有重要的地位。

2、選擇適當(dāng)?shù)囊?guī)劃方向

動態(tài)規(guī)劃方法的實現(xiàn)中，規(guī)劃方向的選擇主要有兩種：順推和逆推。在有些情況下，選取不同的規(guī)劃方向，程序的時間效率也有所不同。一般地，若初始狀態(tài)確定，目標(biāo)狀態(tài)不確定，則應(yīng)考慮采用順推，反之，若目標(biāo)狀態(tài)確定，而初始狀態(tài)不確定，就應(yīng)該考慮采用逆推。那么，若是初始狀態(tài)和目標(biāo)狀態(tài)都已確定，一般情況下順推和逆推都可以選用，但是，能否考慮選用雙向規(guī)劃呢？

雙向搜索的方法已為大家所熟知，它的主要思想是：在狀態(tài)空間十分龐大，而初始狀態(tài)和目標(biāo)狀態(tài)又都已確定的情況下，由于擴展的狀態(tài)量是指數(shù)級增長的，于是為了減少狀態(tài)的規(guī)模，分別從初始狀態(tài)和目標(biāo)狀態(tài)兩個方向進行擴展，并在兩者的交匯處得到問題的解。

上述優(yōu)化思想能否也應(yīng)用到動態(tài)規(guī)劃之中呢？來看下面這個例子。

例二、Divide(Merc`2000)

[問題描述]

有價值分別為1..6的大理石各a[1..6]塊，現(xiàn)要將它們分成兩部分，使得兩部分價值和相等，問是否可以實現(xiàn)。其中大理石的總數(shù)不超過20000。(英文試題詳見附件)

[算法分析]

令S=∑(i*a[i])，若S為奇數(shù)，則不可能實現(xiàn)，否則令Mid=S/2，則問題轉(zhuǎn)化為能否從給定的大理石中選取部分大理石，使其價值和為Mid。

這實際上是母函數(shù)問題，用動態(tài)規(guī)劃求解也是等價的。

m[i,j]，0≤i≤6，0≤j≤Mid，表示能否從價值為1..i的大理石中選出部分大理石，使其價值和為j，若能，則用true表示，否則用false表示。則狀態(tài)轉(zhuǎn)移方程為：m[i,j]=m[i,j]ORm[i-1,j-i*k](0≤k≤a[i])

規(guī)劃的邊界條件為：m[i,0]=true；0≤i≤6

若m[i,Mid]=true，0≤i≤6，則可以實現(xiàn)題目要求，否則不可能實現(xiàn)。

我們來分析上述算法的時間性能，上述算法中每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)為a[i]，每次狀態(tài)轉(zhuǎn)移的時間為O(1)，而狀態(tài)總數(shù)是所有值為true的狀態(tài)的總數(shù)，實際上就是母函數(shù)中項的數(shù)目。

[算法優(yōu)化]

實踐發(fā)現(xiàn)：本題在i較小時，由于可選取的大理石的價值品種單一，數(shù)量也較少，因此值為true的狀態(tài)也較少，但隨著i的增大，大理石價值品種和數(shù)量的增多，值為true的狀態(tài)也急劇增多，使得規(guī)劃過程的速度減慢，影響了算法的時間效率。

另一方面，我們注意到我們關(guān)心的僅是能否得到價值和為Mid的值為true的狀態(tài)，那么，我們能否從兩個方向分別進行規(guī)劃，分別求出從價值為1..3的大理石中選出部分大理石所能獲得的所有價值和，和從價值為4..6的大理石中選出部分大理石所能獲得的所有價值和。最后通過判斷兩者中是否存在和為Mid的價值和，由此，可以得出問題的解。

狀態(tài)轉(zhuǎn)移方程改進為：

當(dāng)i≤3時：

m[i,j]=m[i,j]ORm[i-1,j-i*k](1≤k≤a[i])

當(dāng)i>3時：

m[i,j]=m[i,j]ORm[i+1,j-i*k](1≤k≤a[i])

規(guī)劃的邊界條件為：m[i,0]=true；0≤i≤7

這樣，若存在k，使得m[3,k]=true,m[4,Mid-k]=true，則可以實現(xiàn)題目要求，否則無法實現(xiàn)。

（程序及優(yōu)化前后的運行結(jié)果比較見附件）

從上圖可以看出雙向動態(tài)規(guī)劃與單向動態(tài)規(guī)劃在計算的狀態(tài)總數(shù)上的差異。

回顧本題的優(yōu)化過程可以發(fā)現(xiàn)：本題的實際背景與雙向搜索的背景十分相似，同樣有龐大的狀態(tài)空間，有確定的初始狀態(tài)和目標(biāo)狀態(tài)，狀態(tài)量都迅速增長，而且可以實現(xiàn)交匯的判斷。因此，由本題的優(yōu)化過程，我們認(rèn)識到，雙向擴展以減少狀態(tài)量的方法不僅適用于搜索，同樣適用于動態(tài)規(guī)劃。這種在不同解題方法中，尋找共通的屬性，從而借用相同的優(yōu)化思想，可以使我們不斷創(chuàng)造出新的方法。

3.2減少每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)

在使用動態(tài)規(guī)劃方法解題時，對當(dāng)前狀態(tài)的計算都是進行一些決策并引用相應(yīng)的已經(jīng)

計算過的狀態(tài)，這個過程稱為“狀態(tài)轉(zhuǎn)移”。因此，每個狀態(tài)可能做出的決策數(shù)，也就是每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)是決定動態(tài)規(guī)劃算法時間復(fù)雜度的一個重要因素。本節(jié)將討論減少每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)的一些方法。

1、四邊形不等式和決策的單調(diào)性

例三、石子合并問題(NOI`95)

[問題描述]

在一個操場上擺放著一排n（n≤20）堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。

試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。

[算法分析]

這道題是動態(tài)規(guī)劃的經(jīng)典應(yīng)用。由于最大得分和最小得分是類似的，所以這里僅對最小得分進行討論。設(shè)n堆石子依次編號為1，2，…..，n。各堆石子數(shù)為d[1..n]，則動態(tài)規(guī)劃的狀態(tài)表示為：

m[i,j]，1≤i≤j≤n，表示合并d[i..j]所得到的最小得分，則狀態(tài)轉(zhuǎn)移方程和邊界條件為：

m[i,j]=0i=j

∑=≤j。下面只討論k≤j，k>j的情況是類似的。

情形1.1：k≤j，此時：

]

',[]

',[]1,[]',[]

',[],[]1,[]',[]

',[],[]1,[],[]',[],[jimjkmkimjiwjjmjkmkimjiwjjmjkmkimjiwjjmjim=+?+≤++?+≤++?+≤+

情形2：iy。下面只討論z≤y，z>y的情況是類似的。由iy，下面僅討論

z≤y，z>y的情況是類似的。

由i≤z≤y≤j有：

]

',[],'[|

][][||][][||][][||][][||][][||][][||

][][||][][|]','[],['

''1'

1'''

'jiwjiwydldzdldydldzdldydldzdldydldzdldjiwjiwjiljiljjljjljilji

ljiljil+=?+?=???+

?+?≤?+?≤+∑∑∑∑∑∑∑∑==+=+=====接著，我們用數(shù)學(xué)歸納法證明函數(shù)m也滿足四邊形不等式。對四邊形不等式中“長度”l=j’-i進行歸納：

當(dāng)i=i’或j=j’時，不等式顯然成立。由此可知，當(dāng)l≤1時，函數(shù)m滿足四邊形不等式。下面分兩種情形進行歸納證明：

情形1：ij。下面只討論k≤j，k>j的情況是類似的。

]

',[]

',1[],1[]',[]1,1[],1[],1[]

',[],[jimjkwkimjjwjjmjkwkimjjmjim=++?≤+??+++?≤+情形2：iy。

情形2.1，當(dāng)z≤y1時，令p[i]=k，表示最優(yōu)決策，以便在計算出最優(yōu)值后構(gòu)造最長單調(diào)

上升子序列。

上述算法的狀態(tài)總數(shù)為O(n)，每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)最多為O(n)，每次狀態(tài)轉(zhuǎn)移的時間為O(1)，所以算法總的時間復(fù)雜度為O(n2)。

[算法優(yōu)化]

我們先來考慮以下兩種情況：

1、若x[i]j，k>i)，必有x[k]>x[j]>x[i]，則m[k]也能由m[i]轉(zhuǎn)移得到；另一方面，可以由狀態(tài)m[i]轉(zhuǎn)移得到的狀態(tài)m[k](k>j，k>i)，當(dāng)x[j]>x[k]>x[i]時，m[k]就無法由m[j]轉(zhuǎn)移得到。

由此可見，在所有狀態(tài)值相同的狀態(tài)中，只需保留最后一個元素值最小的那個狀態(tài)即可。

2、若x[i]m[j]，則m[j]這個狀態(tài)不必保留。因為，可以由狀態(tài)m[j]轉(zhuǎn)移得到的狀態(tài)m[k](k>j，k>i)，必有x[k]>x[j]>x[i]，則m[k]也能由m[i]轉(zhuǎn)移得到，而且m[i]>m[j]，所以m[k]≥m[i]+1>m[j]+1，則m[j]的狀態(tài)轉(zhuǎn)移是沒有意義的。

綜合上述兩點，我們得出了狀態(tài)m[k]需要保留的必要條件：不存在i使得：x[i]x[j]。

下面我們來考慮狀態(tài)轉(zhuǎn)移：假設(shè)當(dāng)前已求出m[1..i-1]，當(dāng)前保留的狀態(tài)集合為S，下面計算m[i]。

1、若存在狀態(tài)k∈S，使得x[k]=x[i]，則狀態(tài)m[i]必定不需保留，不必計算。因為，不妨設(shè)m[i]=m[j]+1，則x[j]x[i],j∈S}。于是狀態(tài)k應(yīng)從S中刪去。

于是，我們得到了改進后的算法：

Fori:=1tondo

{

找出集合S中的x值不超過x[i]的最大元素k；

ifx[k]M時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)；

F(u,i)：表示L前i個字符劃分為以名詞結(jié)尾（當(dāng)iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)。

過去的分解方案僅通過最后一個非輔詞的詞性影響以后的決策，所以這種狀態(tài)表示滿足無后效性，

狀態(tài)轉(zhuǎn)移方程為：

F(v,i)=min{F(n,j)+(0,1)，L(j+1..i)為動詞；

F(v,j)+(0,1)，L(j+1..i)為輔詞，iM；}

F(n,i)=min{F(n,j)+(1,1),L(j+1..i)為名詞；

F(v,j)+(0,1),L(j+1..i)為名詞；

F(n,j)+(0,1),L(j+1..i)為輔詞，iM；}

邊界條件：F(v,0)=(1,0)；F(n,0)=(∞,∞)；

問題的解為：min{F(v,M),F(u,M)}；

上述算法中，狀態(tài)總數(shù)為O(M)，每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)最多為20，在進行狀態(tài)轉(zhuǎn)移時，需要查找L[j+1..i]的詞性，根據(jù)其詞性做出相應(yīng)的決策，并引用相應(yīng)的狀態(tài)。下面就通過不同的方法查找L[j+1..i]的詞性，比較它們的時間復(fù)雜度。

[算法實現(xiàn)]

設(shè)單詞表的規(guī)模為N，首先我們對單詞表進行預(yù)處理，將單詞按字典順序排序并合并具有多重詞性的單詞。在查找詞性時有以下幾種方法：

方法1、采用順序查找法。最壞情況下需要遍歷整個單詞表，因此最壞情況下的時間復(fù)雜度為O(20*N*M)，比較次數(shù)最多可達(dá)1000*5k*20=108，當(dāng)數(shù)據(jù)量較大時效率較低。

方法2、采用二分查找法。最壞情況下的時間復(fù)雜度為O(20*M*log2N)，最多比較次數(shù)降為5k*20*log21000=106，完全可以忍受。

集合查找最為有效的方法要屬采用哈希表了。

方法3、采用哈希表查找單詞的詞性。首先將字符串每四位折疊相加計算關(guān)鍵值k，然后用雙重哈希法計算哈希函數(shù)值h(k)。采用這種方法，通過O(N)時間的預(yù)處理構(gòu)造哈希表，每次查找只需O(1)的時間，因此，算法的時間復(fù)雜度為O(20*M+N)=O(M)。

采用哈希表是進行集合查找的一般方法，對于以字符串為元素的集合還有更為高效的方法，即采用檢索樹[3]。

方法四、采用檢索樹查找單詞的詞性。由于每個狀態(tài)在進行狀態(tài)轉(zhuǎn)移時需要查找的所有單詞都是分布在同一條從樹根到葉子的路徑上的，因此，如果選取從樹根走一條路徑到葉子作為基本操作，則每個狀態(tài)進行狀態(tài)轉(zhuǎn)移時的最多20次單詞查找只需O(1)的時間，另外，建立檢索樹需要O(N)的時間，因此，算法總的時間復(fù)雜度雖然仍為O(M)，但是由于時間復(fù)雜度的常數(shù)因子小于方法三，因此實際測試的速度也最快。

（程序及四種方法的運行結(jié)果的比較見附件）

從本題的優(yōu)化過程可以看出：采用正確的數(shù)據(jù)結(jié)構(gòu)是算法優(yōu)化的重要原則，在動態(tài)規(guī)劃算法的優(yōu)化中也同樣適用。方法3使用了哈希表這一高效的集合查找數(shù)據(jù)結(jié)構(gòu)，方法四使

用的針對性更強的檢索樹，使得算法的時間效率得到了提高。

2、減少計算遞推式的時間

計算遞推式的主要操作是對常數(shù)項的計算，因此減少計算遞推式所需的時間主要是指減少計算常數(shù)項的時間。

例八、公路巡邏(CTSC`2000)

[問題描述]

在一條沒有分岔的公路上有n（n≤50）個關(guān)口，相鄰兩個關(guān)口之間的距離都是10km。所有車輛在這條公路上的最低速度為60km/h，最高速度為120km/h，且只能在關(guān)口出改變速度。

有m(m≤300)輛巡邏車分別在時刻Ti從第ni個關(guān)口出發(fā)，勻速行駛到達(dá)第ni+1個關(guān)口，路上耗費時間為ti秒。

兩輛車相遇指他們之間發(fā)生超車現(xiàn)象或同時到達(dá)某個關(guān)口。

求一輛于6點整從第1個關(guān)口出發(fā)去第n個關(guān)口的車（稱為目標(biāo)車）最少會與多少輛巡邏車相遇，以及在此情況下到達(dá)第n個關(guān)口的最早時刻。

假設(shè)所有車輛到達(dá)關(guān)口的時刻都是整秒。

[算法分析]

本題也是用動態(tài)規(guī)劃來解。問題的狀態(tài)表示描述為：

F(i,T)表示在時刻T到達(dá)第i個關(guān)口的途中最少已與巡邏車相遇的次數(shù)。則狀態(tài)轉(zhuǎn)移方程和邊界條件為：

F(i,T)=min{F(i-1,T-Tk)+w(i-1,T-Tk,T)，300≤Tk≤600}2≤i≤n

邊界條件：F(1,06:00:00)=0;

問題的解為：min{F(n,T)}

其中，函數(shù)w(i-1,T-Tk,T)是計算目標(biāo)車于時刻T-Tk從第i-1個關(guān)口出發(fā)，于時刻T到達(dá)第i個關(guān)口，途中與巡邏車相遇的次數(shù)。

下面來分析上述算法的時間復(fù)雜度，問題的階段數(shù)為n，第i個階段的狀態(tài)數(shù)為(i-1)*300，則狀態(tài)總數(shù)為：)150()2

)1(**

300()300*)1((21nOnnOiOni∑==?=?，每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為300，每次狀態(tài)轉(zhuǎn)移所需的時間關(guān)鍵取決與函數(shù)w的計算。下面比較采用不同的計算方法時，時間復(fù)雜度的差異。

[函數(shù)w的計算]

方法1、在每個決策中都進行一次計算，對所有從第i個關(guān)口出發(fā)的巡邏車進行判斷，這樣平均每次狀態(tài)轉(zhuǎn)移的時間為O(1+m/n)，由M的最大值為300，算法總的時間復(fù)雜度為：

()

nmOnmnmOnmnO3322222)1(*300*150=????????+=??????+方法2、仔細(xì)觀察狀態(tài)轉(zhuǎn)移方程可以發(fā)現(xiàn)，在對狀態(tài)F(i,T)進行轉(zhuǎn)移時，所計算的函數(shù)w都是從第i個關(guān)口出發(fā)的，而且出發(fā)時刻都是T，只是相應(yīng)的到達(dá)時刻不同，我們考慮能否找出它們之間的聯(lián)系，從而能夠利用已經(jīng)得出的結(jié)果，減少重復(fù)運算。

我們來考慮w(i,T,k)與w(i,T,k+1)之間的聯(lián)系：

對于每輛從第i個關(guān)口出發(fā)的巡邏車，設(shè)其出發(fā)時刻和到達(dá)時刻分別為Stime和Ttime，則：

若Ttimek+1，則目標(biāo)車A、目標(biāo)車B與該巡邏車的相遇情況相同；若Ttime=k，則目標(biāo)車A與該巡邏車相遇，對目標(biāo)車B的分析又分為：若Stime≤T，則目標(biāo)車B不與該巡邏車相遇，否則目標(biāo)車B也與該巡邏車相遇；

若Ttime=k+1,則目標(biāo)車B與該巡邏車相遇，對目標(biāo)車A的分析又分為：若Stime≥T，則目標(biāo)車A不與該巡邏車相遇，否則目標(biāo)車A也與該巡邏車相遇；

我們令⊿[k]=w[i,T,k+1]-w[i,T,k]，由上述討論得：

⊿[k]=G((Ttime=k+1)and(Stime≥T))–G((Ttime=k)and(Stime≤T)).其中函數(shù)G(P)表示所有從i個關(guān)口出發(fā)，且滿足條件P的巡邏車的數(shù)目。

這樣我們就找到了函數(shù)w之間的聯(lián)系。于是，我們在對狀態(tài)