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

1、動態(tài)規(guī)劃算法的優(yōu)化技巧福州第三中學 毛子青關(guān)鍵詞 動態(tài)規(guī)劃、 時間復(fù)雜度、優(yōu)化、狀態(tài)摘要動態(tài)規(guī)劃是信息學競賽中一種常用的程序設(shè)計方法，本文著重討論了運用動態(tài)規(guī)劃思想解題時時間效率的優(yōu)化。全文分為四個部分，首先討論了動態(tài)規(guī)劃時間效率優(yōu)化的可行性和必要性，接著給出了動態(tài)規(guī)劃時間復(fù)雜度的決定因素，然后分別闡述了對各個決定因素的優(yōu)化方法，最后總結(jié)全文。正文一、引言動態(tài)規(guī)劃是一種重要的程序設(shè)計方法，在信息學競賽中具有廣泛的應(yīng)用。使用動態(tài)規(guī)劃方法解題，對于不少問題具有空間耗費大、時間效率高的特點，因此人們在研究動態(tài)規(guī)劃解題時更多的注意空間復(fù)雜度的優(yōu)化，運用各種技巧將空間需求控制在軟硬件可以承受的范圍之內(nèi)。

2、但是，也有一部分問題在使用動態(tài)規(guī)劃思想解題時，時間效率并不能滿足要求，而且算法仍然存在優(yōu)化的余地，這時，就需要考慮時間效率的優(yōu)化。本文討論的是在確定使用動態(tài)規(guī)劃思想解題的情況下，對原有的動態(tài)規(guī)劃解法的優(yōu)化，以求降低算法的時間復(fù)雜度，使其能夠適用于更大的規(guī)模。二、動態(tài)規(guī)劃時間復(fù)雜度的分析使用動態(tài)規(guī)劃方法解題，對于不少問題之所以具有較高的時間效率，關(guān)鍵在于它減少了“冗余”。所謂“冗余”，就是指不必要的計算或重復(fù)計算部分，算法的冗余程度是決定算法效率的關(guān)鍵。動態(tài)規(guī)劃在將問題規(guī)模不斷縮小的同時，記錄已經(jīng)求解過的子問題的解，充分利用求解結(jié)果，避免了反復(fù)求解同一子問題的現(xiàn)象，從而減少了冗余。但是，動態(tài)規(guī)劃

3、求解問題時，仍然存在冗余。它主要包括：求解無用的子問題，對結(jié)果無意義的引用等等。下面給出動態(tài)規(guī)劃時間復(fù)雜度的決定因素：時間復(fù)雜度=狀態(tài)總數(shù)*每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)*每次狀態(tài)轉(zhuǎn)移的時間1下文就將分別討論對這三個因素的優(yōu)化。這里需要指出的是：這三者之間不是相互獨立的，而是相互聯(lián)系，矛盾而統(tǒng)一的。有時，實現(xiàn)了某個因素的優(yōu)化，另外兩個因素也隨之得到了優(yōu)化；有時，實現(xiàn)某個因素的優(yōu)化卻要以增大另一因素為代價。因此，這就要求我們在優(yōu)化時，堅持“全局觀”，實現(xiàn)三者的平衡。三、動態(tài)規(guī)劃時間效率的優(yōu)化3.1 減少狀態(tài)總數(shù)我們知道，動態(tài)規(guī)劃的求解過程實際上就是計算所有狀態(tài)值的過程，因此狀態(tài)的規(guī)模直接影響到算法的時間效

4、率。所以，減少狀態(tài)總數(shù)是動態(tài)規(guī)劃優(yōu)化的重要部分，本節(jié)將討論減少狀態(tài)總數(shù)的一些方法。1、改進狀態(tài)表示狀態(tài)的規(guī)模與狀態(tài)表示的方法密切相關(guān)，通過改進狀態(tài)表示減小狀態(tài)總數(shù)是應(yīng)用較為普遍的一種方法。例一、 Raucous Rockers 演唱組（USACO96）問題描述現(xiàn)有n首由Raucous Rockers 演唱組錄制的珍貴的歌曲，計劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標準進行選擇：（1） 這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；（2） 包含歌曲的總數(shù)盡可能多。輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的

5、長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。（1n, m, t20）算法分析本題要求唱片中的歌曲必須按照它們創(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首歌曲按照寫作順序排序后的長度為long1.n，則動態(tài)規(guī)劃的狀態(tài)表示描述為：gi, j, k，0in，0jm，0kt，表示前i首歌曲，用j張唱片另加k分鐘來

6、錄制，最多可以錄制的歌曲數(shù)目，則問題的最優(yōu)解為gn,m,0。由于歌曲i有發(fā)行和不發(fā)行兩種情況，而且還要分另加的k分鐘是否能錄制歌曲i。這樣我們可以得到如下的狀態(tài)轉(zhuǎn)移方程和邊界條件：當klongi，i1時：gi, j, k=maxgi-1,j,k-longi，gi-1,j,k當klongi，i1時：gi, j, k=maxgi-1,j-1,t-longi，gi-1,j,k規(guī)劃的邊界條件為：當0kt-b時： a=a+1; b=longi;規(guī)劃的邊界條件：gi,0=(0,0) 0in這樣題目所求的最大值是：ans=maxk| gn, k(m-1,t)改進后的算法，狀態(tài)總數(shù)為O(n2)，每個狀態(tài)轉(zhuǎn)移的

7、狀態(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)化，我們認識到：應(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、選擇適當?shù)囊?guī)劃方向 動態(tài)規(guī)劃方法的實現(xiàn)中，規(guī)劃方向的選擇主要有兩種：順推和逆推。在有些情況下，選取不同的規(guī)劃方向，程序的時間效率也有所不同。一

8、般地，若初始狀態(tài)確定，目標狀態(tài)不確定，則應(yīng)考慮采用順推，反之，若目標狀態(tài)確定，而初始狀態(tài)不確定，就應(yīng)該考慮采用逆推。那么，若是初始狀態(tài)和目標狀態(tài)都已確定，一般情況下順推和逆推都可以選用，但是，能否考慮選用雙向規(guī)劃呢？雙向搜索的方法已為大家所熟知，它的主要思想是：在狀態(tài)空間十分龐大，而初始狀態(tài)和目標狀態(tài)又都已確定的情況下，由于擴展的狀態(tài)量是指數(shù)級增長的，于是為了減少狀態(tài)的規(guī)模，分別從初始狀態(tài)和目標狀態(tài)兩個方向進行擴展，并在兩者的交匯處得到問題的解。上述優(yōu)化思想能否也應(yīng)用到動態(tài)規(guī)劃之中呢？來看下面這個例子。例二、 Divide (Merc2000)問題描述有價值分別為1.6的大理石各a1.6塊，現(xiàn)

9、要將它們分成兩部分，使得兩部分價值和相等，問是否可以實現(xiàn)。其中大理石的總數(shù)不超過20000。(英文試題詳見附件)算法分析令S=(i*ai)，若S為奇數(shù)，則不可能實現(xiàn)，否則令Mid=S/2，則問題轉(zhuǎn)化為能否從給定的大理石中選取部分大理石，使其價值和為Mid。這實際上是母函數(shù)問題，用動態(tài)規(guī)劃求解也是等價的。mi, j，0i6，0jMid，表示能否從價值為1.i的大理石中選出部分大理石，使其價值和為j，若能，則用true表示，否則用false表示。則狀態(tài)轉(zhuǎn)移方程為：mi, j=mi, j OR mi-1,j-i*k (0kai)規(guī)劃的邊界條件為：mi,0=true； 0i6若mi, Mid=true

10、，0i6，則可以實現(xiàn)題目要求，否則不可能實現(xiàn)。我們來分析上述算法的時間性能，上述算法中每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)為ai，每次狀態(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的大理石中選出

11、部分大理石所能獲得的所有價值和，和從價值為4.6的大理石中選出部分大理石所能獲得的所有價值和。最后通過判斷兩者中是否存在和為Mid的價值和，由此，可以得出問題的解。狀態(tài)轉(zhuǎn)移方程改進為：當i3時：mi, j=mi, j OR mi-1,j-i*k (1kai)當i3時：mi, j=mi, j OR mi+1,j-i*k (1kai)規(guī)劃的邊界條件為：mi,0=true； 0i7這樣，若存在k，使得m3,k=true, m4,Mid-k=true，則可以實現(xiàn)題目要求，否則無法實現(xiàn)。（程序及優(yōu)化前后的運行結(jié)果比較見附件）從上圖可以看出雙向動態(tài)規(guī)劃與單向動態(tài)規(guī)劃在計算的狀態(tài)總數(shù)上的差異?；仡櫛绢}的優(yōu)化

12、過程可以發(fā)現(xiàn)：本題的實際背景與雙向搜索的背景十分相似，同樣有龐大的狀態(tài)空間，有確定的初始狀態(tài)和目標狀態(tài)，狀態(tài)量都迅速增長，而且可以實現(xiàn)交匯的判斷。因此，由本題的優(yōu)化過程，我們認識到，雙向擴展以減少狀態(tài)量的方法不僅適用于搜索，同樣適用于動態(tài)規(guī)劃。這種在不同解題方法中，尋找共通的屬性，從而借用相同的優(yōu)化思想，可以使我們不斷創(chuàng)造出新的方法。3.2 減少每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)在使用動態(tài)規(guī)劃方法解題時，對當前狀態(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é)將討論減

13、少每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)的一些方法。1、四邊形不等式和決策的單調(diào)性例三、石子合并問題(NOI95)問題描述 在一個操場上擺放著一排n（n20）堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。算法分析這道題是動態(tài)規(guī)劃的經(jīng)典應(yīng)用。由于最大得分和最小得分是類似的，所以這里僅對最小得分進行討論。設(shè)n堆石子依次編號為1，2，.，n。各堆石子數(shù)為d1.n，則動態(tài)規(guī)劃的狀態(tài)表示為：mi,j，1ijn，表示合并di.j所得到的最小得分，則狀態(tài)轉(zhuǎn)移方程和邊界條件為：mi

14、,j=0 i=j ij同時令si,j=k，表示合并的斷開位置，便于在計算出最優(yōu)值后構(gòu)造出最優(yōu)解。上式中的計算，可在預(yù)處理時計算，i=1.n；t0=0, 則：上述算法的狀態(tài)總數(shù)為O(n2)，每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(n)，每次狀態(tài)轉(zhuǎn)移的時間為O(1)，所以總的時間復(fù)雜度為O(n3)。算法優(yōu)化當函數(shù)wi,j滿足時，稱w滿足四邊形不等式2。當函數(shù)wi,j滿足wi,jwi,j 時稱w關(guān)于區(qū)間包含關(guān)系單調(diào)。在石子歸并問題中，令wi,j= ，則wi,j滿足四邊形不等式，同時由di0,ti0可知wi,j滿足單調(diào)性。mi,j=0 i=j ij 對于滿足四邊形不等式的單調(diào)函數(shù)w，可推知由遞推式定義的函數(shù)mi,j

15、也滿足四邊形不等式，即。這一性質(zhì)可用數(shù)學歸納法證明如下：我們對四邊形不等式中“長度”l=j-i進行歸納：當i=i或j=j時，不等式顯然成立。由此可知，當l1時，函數(shù)m滿足四邊形不等式。下面分兩種情形進行歸納證明：情形1：ii=jj。下面只討論kj，kj的情況是類似的。情形1.1：kj，此時：情形2：iijy。下面只討論zy，zy的情況是類似的。由izyj有：綜上所述，mi,j滿足四邊形不等式。令si,j=maxk | mi,j=mi,k-1+mk,j+wi,j 由函數(shù)mi,j滿足四邊形不等式可以推出函數(shù)si,j的單調(diào)性，即si,jsi,j+1si+1,j+1, ij當i=j時，單調(diào)性顯然成立。

16、因此下面只討論ij的情形。由于對稱性，只要證明si,jsi,j+1。令mki,j=mi,k-1+mk,j+wi,j。要證明si,jsi,j+1，只要證明對于所有ikkj且mki,jmki,j，有：mki,j+1mki,j+1。事實上，我們可以證明一個更強的不等式mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用遞推定義式將其展開整理可得：mk,j+mk,j+1mk,j+mk,j+1，這正是kkjj+1時的四邊形不等式。綜上所述，當w滿足四邊形不等式時，函數(shù)si,j具有單調(diào)性。于是，我們利用si,j的單調(diào)性，得到優(yōu)化的狀態(tài)轉(zhuǎn)移方

17、程為：mi,j=0 i=j iy，下面僅討論zy，zy的情況是類似的。由izyj有： 接著，我們用數(shù)學歸納法證明函數(shù)m也滿足四邊形不等式。對四邊形不等式中“長度”l=j-i進行歸納：當i=i或j=j時，不等式顯然成立。由此可知，當l1時，函數(shù)m滿足四邊形不等式。下面分兩種情形進行歸納證明：情形1：ii=jj。下面只討論kj，kj的情況是類似的。情形2：iijy。情形2.1，當zyjj時：情形2.2，當i-1i-1yzj時：最后，我們證明決策si,j滿足單調(diào)性。為討論方便，令mki,j=mi-1,k+wk+1,j；我們先來證明si-1,jsi,j，只要證明對于所有ikkj且mki-1,jmki-

18、1,j，有：mki,jmki,j。類似地，我們可以證明一個更強的不等式mki-1,j-mki-1,jmki,j-mki,j也就是： mki-1,j+mki,jmki,j+mki-1,j利用遞推定義式展開整理的：mi-2,k+mi-1,kmi-1,k+mi-2,k，這就是i-2i-1kk時m的四邊形不等式。我們再來證明si,jsi,j+1，與上文類似，設(shè)kkj，則我們只需證明一個更強的不等式： mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用遞推定義式展開整理的：wk+1,j+wk+1,j+1wk+1,j+1+wk+1,j，這

19、就是k+1k+1jj+1時w的四邊形不等式。綜上所述，該問題的決策si,j具有單調(diào)性，于是優(yōu)化后的狀態(tài)轉(zhuǎn)移方程為：m1,j=w1,j ij si,j=k同上文所述，優(yōu)化后的算法時間復(fù)雜度為O(n*p)。（程序及優(yōu)化前后的運行結(jié)果比較見附件） 四邊形不等式優(yōu)化的實質(zhì)是對結(jié)果的充分利用。它通過分析狀態(tài)值之間的特殊關(guān)系，推出了最優(yōu)決策的單調(diào)性，從而在計算當前狀態(tài)時，利用已經(jīng)計算過的狀態(tài)所做出的最優(yōu)決策，減少了當前的決策量。這就啟發(fā)我們，在應(yīng)用動態(tài)規(guī)劃解題時，不僅可以實現(xiàn)狀態(tài)值的充分利用，也可以實現(xiàn)最優(yōu)決策的充分利用。這實際上是從另一個角度實現(xiàn)了“減少冗余”。2、決策量的優(yōu)化通過分析問題最優(yōu)解所具備的

20、性質(zhì)，從而縮小有可能產(chǎn)生最優(yōu)解的決策集合，也是減少每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)的一種方法。大家所熟悉的NOI96中的添加號問題，正是從“所得的和最小”這一原則出發(fā)，僅在等分點的附近添加號，從而大大減少了每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)，降低了算法的時間復(fù)雜度。讓我們在再來看一例。例五、石子歸并的最大得分問題問題描述 見例三，本例只考慮最大得分問題。算法分析 設(shè)n堆石子依次編號為1，2，.，n。各堆石子數(shù)為d1.n，則動態(tài)規(guī)劃的狀態(tài)表示為：mi,j，1ijn，表示合并di.j所得到的最大得分，則狀態(tài)轉(zhuǎn)移方程和邊界條件為：mi,j=0 i=j ij同時令si,j=k，表示合并的斷開位置，便于在計算出最優(yōu)值后構(gòu)造出

21、最優(yōu)解。 該算法的時間復(fù)雜度為O(n3)。算法優(yōu)化仔細分析問題，可以發(fā)現(xiàn)：si,j要么等于i+1，要么等于j，即：證明可以采用反證法，設(shè)使mi,j達到最大值的斷開位置為p，且i+1pj，下面分為2種情形討論。情形1、yz由pj，可設(shè)sp,j=k，則相應(yīng)的合并方式可以表示為：( (aiap-1) ( (ap.ak-1) (ak.aj) ) )相應(yīng)的得分為：下面考慮另一種合并方案si,j=k，si,k=p，表示為：( ( (aiap-1) (ap.ak-1) ) (ak.aj) )相應(yīng)的得分為：由yz可得，TT，這與使mi,j達到最大值的斷開位置為p的假設(shè)矛盾。情形2、yz 與情形1類似。于是，狀

22、態(tài)轉(zhuǎn)移方程優(yōu)化為：mi,j=0 i=j ij優(yōu)化后每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)減少為O(1)，算法總的時間復(fù)雜度也降為O(n2)。（程序及優(yōu)化前后的運行結(jié)果比較見附件）本題的優(yōu)化過程是通過對問題最優(yōu)解性質(zhì)的分析，找出最優(yōu)決策必須滿足的必要條件，這與搜索中的最優(yōu)性剪枝的思想十分類似，由此我們再次看到了相同的優(yōu)化思想應(yīng)用于不同的算法設(shè)計方法。同時，我們也認識到：動態(tài)規(guī)劃的優(yōu)化必須建立在全面細致分析問題的基礎(chǔ)上，只有深入分析問題的屬性，挖掘問題的實質(zhì)，才能實現(xiàn)算法的優(yōu)化。3、合理組織狀態(tài) 在動態(tài)規(guī)劃求解的過程中，需要不斷地引用已經(jīng)計算過的狀態(tài)。因此，合理地組織已經(jīng)計算出的狀態(tài)有利于提高動態(tài)規(guī)劃的時間效率。例

23、六、求最長單調(diào)上升子序列問題描述給出一個由n個數(shù)組成的序列x1.n，找出它的最長單調(diào)上升子序列。即求最大的m和a1,a2,am，使得a1a2am且xa1xa2xam。算法分析這也是一道動態(tài)規(guī)劃的經(jīng)典應(yīng)用。動態(tài)規(guī)劃的狀態(tài)表示描述為：mi，1in，表示以xi結(jié)尾的最長上升子序列的長度，則問題的解為 maxmi,1in，狀態(tài)轉(zhuǎn)移方程和邊界條件為：mi=1+max0, mk|xkxi , 1k1時，令pi=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)。算法

24、優(yōu)化我們先來考慮以下兩種情況：1、若xij，ki)，必有xkxjxi，則mk也能由mi轉(zhuǎn)移得到；另一方面，可以由狀態(tài)mi轉(zhuǎn)移得到的狀態(tài)mk (kj，ki)，當xjxkxi時，mk就無法由mj轉(zhuǎn)移得到。由此可見，在所有狀態(tài)值相同的狀態(tài)中，只需保留最后一個元素值最小的那個狀態(tài)即可。2、若ximj，則mj這個狀態(tài)不必保留。因為，可以由狀態(tài)mj轉(zhuǎn)移得到的狀態(tài)mk (kj，ki)，必有xkxjxi，則mk也能由mi轉(zhuǎn)移得到，而且mimj，所以mkmi+1mj+1，則mj的狀態(tài)轉(zhuǎn)移是沒有意義的。綜合上述兩點，我們得出了狀態(tài)mk需要保留的必要條件：不存在i使得：xixk且mimk。于是，我們保留的狀態(tài)中不存

25、在相同的狀態(tài)值，且隨著狀態(tài)值的增加，最后一個元素的值也是單調(diào)遞增的。也就是說，設(shè)當前保留的狀態(tài)集合為S，則S具有以下性質(zhì)D：對于任意iS, jS, ij有：mimj，且若mimj，則xixj。下面我們來考慮狀態(tài)轉(zhuǎn)移：假設(shè)當前已求出m1.i-1，當前保留的狀態(tài)集合為S，下面計算mi。1、若存在狀態(tài)kS，使得xk=xi，則狀態(tài)mi必定不需保留，不必計算。因為，不妨設(shè)mi=mj+1，則xjxi=xk，jS，jk，所以mjmk，則mi=mj+1mk，所以狀態(tài)mi不需保留。2、否則，mi=1+maxmj| xjxi, jS。我們注意到滿足條件的j也滿足xj=maxxk|xkxi, kS。同時我們把狀態(tài)i

26、加入到S中。3、若2成立，則我們往S中增加了一個狀態(tài)，為了保持S的性質(zhì)，我們要對S進行維護，若存在狀態(tài)kS，使得mi=mk，則我們有xixi, jS。于是狀態(tài)k應(yīng)從S中刪去。于是，我們得到了改進后的算法：For i:=1 to n do 找出集合S中的x值不超過xi的最大元素k； if xkxi then mi:=mk+1; 將狀態(tài)i插入集合S； 找出集合S中的x值大于xi的最小元素j； if mj=mi then 將狀態(tài)j從S中刪去； 從性質(zhì)D和算法描述可以發(fā)現(xiàn)，S實際上是以x值為關(guān)鍵字（也是以m值為關(guān)鍵字）的有序集合。若使用平衡樹實現(xiàn)有序集合S，則該算法的時間復(fù)雜度為O(n*log2n)。

27、本題優(yōu)化后，每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)僅為O(1)，而每次狀態(tài)轉(zhuǎn)移的時間變?yōu)镺(log2n)，這也體現(xiàn)了上文所提到的優(yōu)化中不同因素之間的矛盾，但從總體上看，算法的時間復(fù)雜度是降低了。（程序及優(yōu)化前后的運行結(jié)果比較見附件）回顧本題的優(yōu)化過程，首先通過分析狀態(tài)之間的分析，減少需要保留的狀態(tài)數(shù)，同時發(fā)現(xiàn)需要保留狀態(tài)的單調(diào)性，從而減少了每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)，并通過高效數(shù)據(jù)結(jié)構(gòu)平衡樹組織當前保留的狀態(tài)，實現(xiàn)算法的優(yōu)化。通過對本題的優(yōu)化，我們認識到減少保留的狀態(tài)數(shù)，合理組織已經(jīng)計算出的狀態(tài)可以實現(xiàn)減少每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)，同時，選取恰當?shù)臄?shù)據(jù)結(jié)構(gòu)也是算法優(yōu)化的一個重要原則，在下文的闡述中，還會看到借助數(shù)

28、據(jù)結(jié)構(gòu)實現(xiàn)算法優(yōu)化。4、細化狀態(tài)轉(zhuǎn)移所謂“細化狀態(tài)轉(zhuǎn)移”，就是將原來的一次狀態(tài)轉(zhuǎn)移細化成若干次狀態(tài)轉(zhuǎn)移，其目的在于減少總的狀態(tài)轉(zhuǎn)移的次數(shù)。在優(yōu)化前，問題的決策一般都是復(fù)合決策，也就是一些子決策的排列，因此決策的規(guī)模較大，每個狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)也就較多，優(yōu)化的方法就是將每個復(fù)合決策細化成若干個子決策，并在每個子決策后面增設(shè)一個狀態(tài)，這樣，后面的子決策只在前面的子決策達到最優(yōu)解時才進行轉(zhuǎn)移，因此在優(yōu)化后，雖然，狀態(tài)總數(shù)增加了，但是總的狀態(tài)轉(zhuǎn)移次數(shù)卻減少了，算法總的復(fù)雜度也就降低了。應(yīng)該注意的是：上述優(yōu)化應(yīng)該滿足一個條件，即原來每個復(fù)合決策的各個子決策之間也滿足最優(yōu)化原理和無后效性，也就是說：復(fù)合

29、最優(yōu)決策的子決策也是最優(yōu)決策；前面的子決策不影響后面的子決策。上述優(yōu)化方法再一次體現(xiàn)了實現(xiàn)一個因素的優(yōu)化要以增大另一個因素作為代價，但是，算法總的時間復(fù)雜度的降低才是我們的真正目的。3.3 減少狀態(tài)轉(zhuǎn)移的時間我們知道，狀態(tài)轉(zhuǎn)移是動態(tài)規(guī)劃的基本操作，因此，減少每次狀態(tài)轉(zhuǎn)移所需的時間，對提高算法的時間效率具有重要的意義。狀態(tài)轉(zhuǎn)移主要有兩個部分構(gòu)成：1 進行決策：通過當前狀態(tài)和選取的決策計算出需要引用的狀態(tài)。2 計算遞推式：根據(jù)遞推式計算當前狀態(tài)值。其中主要操作是常數(shù)項的計算。本節(jié)將分別討論提高這兩部分時間效率的一些方法。1、減少決策時間例七、LOSTCITY (NOI2000)問題描述 現(xiàn)給出一張

30、單詞表、特定的語法規(guī)則和一篇文章：文章和單詞表中只含26個小寫英文字母az。單詞表中的單詞只有名詞，動詞和輔詞這三種詞性，且相同詞性的單詞互不相同。單詞的長度均不超過20。語法規(guī)則可簡述為：名詞短語：任意個輔詞前綴接上一個名詞；動詞短語：任意個輔詞前綴接上一個動詞；句子：以名詞短語開頭，名詞短語與動詞短語相間連接而成。文章的長度不超過1000。且已知文章是由有限個句子組成的，句子只包含有限個單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。算法分析這是也是一道動態(tài)規(guī)劃問題。我們分別用v,u,a表示動詞，名詞和副詞，給出的文章用L1.M表示，則狀態(tài)表示描述為：F(v,i

31、)：表示L前i個字符劃分為以動詞結(jié)尾（當iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)；F(u,i)：表示L前i個字符劃分為以名詞結(jié)尾（當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)

32、+(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)移時，需要查找Lj+1.i的詞性，根據(jù)其詞性做出相應(yīng)的決策，并引用相應(yīng)的狀態(tài)。下面就通過不同的方法查找Lj+1.i的詞性，比較它們的時間復(fù)雜度。算法實現(xiàn) 設(shè)單詞表的規(guī)模為N，首先我們對單詞表進行預(yù)處理，將單詞按字典順序排序并合并具有多重詞性的單詞。在查找詞性時有以下幾種方法：方法1、采用順序查找法。最壞情況下需要遍歷整個單詞表，因此最壞情況下的時間復(fù)雜度為O(2

33、0*N*M)，比較次數(shù)最多可達1000*5k*20=108，當數(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)。采用哈希表是進行集合查找的一般方法，對于以字符串為元素的集合還有更為高效的方法，即采用

34、檢索樹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)，方法四使用的針對性更強的檢

35、索樹，使得算法的時間效率得到了提高。2、減少計算遞推式的時間計算遞推式的主要操作是對常數(shù)項的計算，因此減少計算遞推式所需的時間主要是指減少計算常數(shù)項的時間。例八、公路巡邏 (CTSC2000)問題描述在一條沒有分岔的公路上有n（n50）個關(guān)口，相鄰兩個關(guān)口之間的距離都是10km。所有車輛在這條公路上的最低速度為60km/h，最高速度為120km/h，且只能在關(guān)口出改變速度。有m(m300)輛巡邏車分別在時刻Ti從第ni個關(guān)口出發(fā)，勻速行駛到達第ni+1個關(guān)口，路上耗費時間為ti秒。兩輛車相遇指他們之間發(fā)生超車現(xiàn)象或同時到達某個關(guān)口。求一輛于6點整從第1個關(guān)口出發(fā)去第n個關(guān)口的車（稱為目標車）最

36、少會與多少輛巡邏車相遇，以及在此情況下到達第n個關(guān)口的最早時刻。假設(shè)所有車輛到達關(guān)口的時刻都是整秒。算法分析本題也是用動態(tài)規(guī)劃來解。問題的狀態(tài)表示描述為：F(i,T)表示在時刻T到達第i個關(guān)口的途中最少已與巡邏車相遇的次數(shù)。則狀態(tài)轉(zhuǎn)移方程和邊界條件為：F(i,T)=minF(i-1,T-Tk)+w(i-1,T-Tk,T)，300Tk600 2in 邊界條件：F(1,06:00:00)=0;問題的解為：minF(n,T)其中，函數(shù)w(i-1,T-Tk,T)是計算目標車于時刻T-Tk從第i-1個關(guān)口出發(fā)，于時刻T到達第i個關(guān)口，途中與巡邏車相遇的次數(shù)。下面來分析上述算法的時間復(fù)雜度，問題的階段數(shù)為

37、n，第i個階段的狀態(tài)數(shù)為(i-1)*300，則狀態(tài)總數(shù)為：，每個狀態(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ù)雜度為：方法2、仔細觀察狀態(tài)轉(zhuǎn)移方程可以發(fā)現(xiàn)，在對狀態(tài)F(i,T)進行轉(zhuǎn)移時，所計算的函數(shù)w都是從第i個關(guān)口出發(fā)的，而且出發(fā)時刻都是T，只是相應(yīng)的到達時刻不同，我們考慮能否找出它們之間的聯(lián)系，從而能夠利用已經(jīng)得出的結(jié)果，減少重復(fù)運算。我們來考慮w(i,T,k)與w(i,T,k+1)之間的聯(lián)系：對于每輛從第i個關(guān)口出發(fā)的巡邏車，設(shè)其出發(fā)時刻和到達時刻分別為Stime和Ttime，則：若Ttimek+1，則目標車A、目標車B與該巡邏車的相遇情況相同；若Ttime=k，則目標車A與該巡邏車相遇，對目標車B的分析又分為：若StimeT，則目標車B不與該巡邏車相遇，否則目標車B也與該巡邏車相遇；若Ttime=k+1,則目標車B與該巡邏車相遇，對目標車A的分析又分為：若 StimeT，則目標車A不與該巡邏車相遇，否則目標車A也與該巡邏車相遇；我們令k=wi,T,k+1-wi,T,k，由上述討論得：k=G(Ttime=k+1) and (St