摘? 要：動(dòng)態(tài)規(guī)劃是解決多階段決策最優(yōu)化問(wèn)題的一種思想方法，也是ACM程序設(shè)計(jì)競(jìng)賽中常用的算法。本文首先討論了動(dòng)態(tài)規(guī)劃的基本思想和解題步驟。但基本動(dòng)態(tài)規(guī)劃對(duì)于數(shù)據(jù)規(guī)模很大的問(wèn)題，在解題過(guò)程中還是存在效率和占用空間非常大的問(wèn)題，本文巧妙利用線段樹(shù)優(yōu)化動(dòng)態(tài)規(guī)劃，提高對(duì)大規(guī)模數(shù)據(jù)處理的方法和技巧，在線段樹(shù)基礎(chǔ)上利用樹(shù)狀數(shù)組合理地解決了動(dòng)態(tài)規(guī)劃占用大量?jī)?nèi)存的問(wèn)題。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃;數(shù)據(jù)結(jié)構(gòu);線段樹(shù)

中圖分類號(hào)：TP301?????????? 文獻(xiàn)標(biāo)識(shí)碼：A

1?? 引言（Introduction）

動(dòng)態(tài)規(guī)劃與分治法和貪心法類似，它們都是將問(wèn)題分解為更小的、相似的子問(wèn)題，但是動(dòng)態(tài)規(guī)劃又有自己的特點(diǎn)。能用貪心法解決的問(wèn)題必須具備貪心的性質(zhì)，所以有很大的局限性[1]。采用分治法解決問(wèn)題時(shí)，由于子問(wèn)題的數(shù)目往往是問(wèn)題規(guī)模的指數(shù)函數(shù)，因此對(duì)時(shí)間的消耗太大。為了節(jié)約重復(fù)求相同子問(wèn)題的時(shí)間，引入一個(gè)數(shù)組，不管它們是否對(duì)最終解有用，把所有子問(wèn)題的解存于該數(shù)組中，這就是動(dòng)態(tài)規(guī)劃法所采用的基本方法。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，動(dòng)態(tài)規(guī)劃的思想在于，如果各個(gè)子問(wèn)題不是獨(dú)立的，不同的子問(wèn)題的個(gè)數(shù)只是多項(xiàng)式量級(jí)，如果能夠保存已經(jīng)解決的子問(wèn)題的答案，而在需要的時(shí)候再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算[2]。

2?? 線段樹(shù)（Segment tree）

2.1?? 線段樹(shù)定義

美國(guó)數(shù)學(xué)家R.E.Bellman等人創(chuàng)立的最優(yōu)化原理（principle of optimality），可以很好的解決多階段決策過(guò)程（multistep decision process）的優(yōu)化問(wèn)題[3]。這為后來(lái)國(guó)內(nèi)外研究動(dòng)態(tài)規(guī)劃提供了原始資料。

動(dòng)態(tài)規(guī)劃方法在求解最短路線、排序、資源分配、裝載、設(shè)備更新、庫(kù)存管理等問(wèn)題上面有很大的優(yōu)越性，遠(yuǎn)比其他的求解方法來(lái)得方便簡(jiǎn)潔;因此廣泛地應(yīng)用于工程技術(shù)、生產(chǎn)調(diào)度、經(jīng)濟(jì)管理和最優(yōu)控制等方面。求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題是動(dòng)態(tài)規(guī)劃的優(yōu)勢(shì)所在，那么那些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃）是否能夠用動(dòng)態(tài)規(guī)劃方法解決呢？答案是肯定的，只要能夠人為引進(jìn)時(shí)間因素，把靜態(tài)規(guī)劃問(wèn)題視為多階段的決策過(guò)程，同樣可以用動(dòng)態(tài)規(guī)劃方法來(lái)求解。

2.2?? 線段樹(shù)的基本操作

一維線段樹(shù)能在O（logL）的時(shí)間內(nèi)完成一條線段的插入、刪除和查找工作，下面對(duì)這些基本操作做簡(jiǎn)要的說(shuō)明。

（1）線段樹(shù)的插入算法

對(duì)線段樹(shù)插入算法的解釋為：如果[left，right]完全覆蓋了當(dāng)前線段，即與樹(shù)結(jié)點(diǎn)p的區(qū)間相匹配，那么顯然該結(jié)點(diǎn)上的覆蓋線段數(shù)為1;否則二分取中值，如在左邊則只對(duì)左樹(shù)做插入，如在右邊則對(duì)右樹(shù)插入。遞歸直到所要插入的結(jié)點(diǎn)的區(qū)間與樹(shù)結(jié)點(diǎn)p的區(qū)間相匹配。由于插入時(shí)做了二分取中值，故時(shí)間復(fù)雜度為O（logN）。

線段樹(shù)的刪除算法跟插入算法類似，這里就不再詳細(xì)展開(kāi)。

（2）線段樹(shù)的查詢算法

線段樹(shù)支持各種查詢操作，例如要查詢一個(gè)結(jié)點(diǎn)q在區(qū)間Interval v位置，我們?nèi)匀灰暂^為容易理解的遞歸的形式執(zhí)行查詢操作。

3?? 優(yōu)化動(dòng)態(tài)規(guī)劃算法（Optimization of dynamic

programming algorithm）

下面我們以郵局選址問(wèn)題為例，以上面介紹的三種方法分別進(jìn)行分析。

3.1?? 典型的動(dòng)態(tài)規(guī)劃算法

有一個(gè)比較明顯的樸素的O（N^2*M）的動(dòng)態(tài)規(guī)劃算法：

我們對(duì)每個(gè)村莊先預(yù)處理一下（O（N*log（N）的復(fù)雜度）），對(duì)于每個(gè)村莊I，如果該村莊建一個(gè)郵局，那么用left[I]表示第I個(gè)能夠覆蓋到的最左邊的村莊，right[I]表示最右邊能夠覆蓋到的村莊。

dp[i][j]表示對(duì)于前面i個(gè)村莊而言如果在這個(gè)i村莊中建了j個(gè)郵局（1=

令A(yù)=Min{dp[k][j-1]+C[i]}---（條件是第k個(gè)村莊最右邊能夠覆蓋到的村莊right[k]，跟第i個(gè)村莊最左邊能夠覆蓋到的村莊left[i]，包含了村莊k和村莊i之間所有村莊，即right[k]>= left[i]-1，否則A設(shè)為正無(wú)窮）。

令B=Min{dp[k][j-1]+C[i]+Cost[right[k]+1][left[i]-1]}---跟上面的情況相比，這種是在區(qū)間[right[k]+1，left[i]-1]之間的村莊都未被村莊i和村莊k覆蓋到，即right[k]

dp[i][j]=Min（A，B）;

O（N*M）的狀態(tài)，O（N）的轉(zhuǎn)移，所以算法總的復(fù)雜度為O（N^2*M）。

3.2?? 利用線段樹(shù)改進(jìn)動(dòng)態(tài)規(guī)劃算法

上述算法不足以應(yīng)付大的數(shù)據(jù)，存在改進(jìn)的空間。

通過(guò)適當(dāng)?shù)倪x取數(shù)據(jù)結(jié)構(gòu)，把狀態(tài)轉(zhuǎn)移的時(shí)間降到O（Log（N））甚至O（1）使得整個(gè)算法的復(fù)雜度為O（S*log（N））或O（S）。

這樣改進(jìn)的地方在于狀態(tài)轉(zhuǎn)移：

①對(duì)于求A的狀態(tài)轉(zhuǎn)移

A=Min{dp[k][j-1]+C[i]}，同傳統(tǒng)的方法一樣，把所有事先已經(jīng)求出的dp[k][j-1]存入線段樹(shù)中，可以通過(guò)線段樹(shù)查詢區(qū)間[left[i]，right[i]]，查詢復(fù)雜度為O（log（N））。endprint

②對(duì)于求B的狀態(tài)轉(zhuǎn)移

B=Min{dp[k][j-1]+C[i]+Cost[right[k]+1][left[i]-1]}，由于Cost[right[k]+1][left[i]-1]的值與下標(biāo)k有關(guān)，所以不能像求A一樣，直接把原狀態(tài)存入線段樹(shù)。我們令F[i][j]=dp[i][j]+Cost[right[i]+1][N]也就前面i個(gè)村的費(fèi)用加上后面N-i個(gè)村莊的費(fèi)用（如果該村莊未被覆蓋）。

那么得到B=Min{F[i][j]-Cost[left[i]][N]}這樣求B的過(guò)程也與k無(wú)關(guān)，這樣同樣利用求A的方法，可以求得B。

綜上所述，我們需要建立兩顆線段樹(shù)，一顆存dp[i][j]，另一顆存F[i][j]，狀態(tài)轉(zhuǎn)移的復(fù)雜度由原來(lái)的O（N）降到了O（log（N）），從而使整個(gè)算法的復(fù)雜度從O（N^2*M）降到了O（N*M*log（N））。

這里有個(gè)很好的優(yōu)化：假如，我們已經(jīng)求出了建設(shè)對(duì)于N個(gè)村莊，建設(shè)j個(gè)郵局的最優(yōu)值a，在我們利用動(dòng)態(tài)規(guī)劃求出建設(shè)N個(gè)村莊建設(shè)j+1的最優(yōu)值b，很明顯b>=a，如果b==a，也就是說(shuō)再新建一個(gè)村莊不會(huì)帶來(lái)費(fèi)用的減少，那么這個(gè)時(shí)候，可以確定最后的答案就是a，所以此時(shí)可以直接退出動(dòng)態(tài)規(guī)劃的過(guò)程，可以大大減少無(wú)謂的計(jì)算。

4?? 算法驗(yàn)證及分析（Verification and analysis

algorithm）

樹(shù)狀數(shù)組是一個(gè)可以很高效的進(jìn)行區(qū)間統(tǒng)計(jì)的數(shù)據(jù)結(jié)構(gòu)。在思想上類似于線段樹(shù)，比線段樹(shù)節(jié)省空間，編程復(fù)雜度比線段樹(shù)低，但適用范圍比線段樹(shù)小。

以簡(jiǎn)單的求和為例。設(shè)原數(shù)組為a[1...N]，樹(shù)狀數(shù)組為c[1...N]，其中c[k]=a[k-（2^t）+1]+...+a[k]。比如c[6]=c[5]+c[6]。也就是說(shuō)，把k表示成二進(jìn)制1***10000，那么c[k]就是1***00001+1***00010+...+1***10000這一段數(shù)的和。設(shè)一個(gè)函數(shù)lowestbit（k）為取得k的最低非零位，容易發(fā)現(xiàn)，根據(jù)上面的表示方法，從a[1]到a[k]的所有數(shù)的總和即為sum[k]=c[k]+c[k-lowestbit（k）]+c[k-lowestbit（k）-lowestbit（k-lowestbit（k））]+...于是可以在logk的時(shí)間內(nèi)求出sum[k]。當(dāng)數(shù)組中某元素發(fā)生變化時(shí)，需要改動(dòng)的c值是c[k]，

c[k+lowestbit（k）]，c[k+lowestbit（k）+lowestbit（k+lowestbit（k））]...

這個(gè)復(fù)雜度是logN（N為最大范圍）。

擴(kuò)展到多維情況：以二維為例，用c[k1][k2]表示c[k1-（2^t1）+1][k2-（2^t2）+1]+...+c[k1][k2]的總和。可以用類似的方法進(jìn)行處理，復(fù)雜度為（logn）^k（k為維數(shù)）。

樹(shù)狀數(shù)組相比線段樹(shù)的優(yōu)勢(shì)：空間復(fù)雜度略低，編程復(fù)雜度低，容易擴(kuò)展到多維情況。劣勢(shì)：適用范圍小，對(duì)可以進(jìn)行的運(yùn)算也有限制，比如每次要查詢的是一個(gè)區(qū)間的最小值，似乎就沒(méi)有很好的解決辦法。

5?? 結(jié)論（Conclusion）

本文提出一種基于線段樹(shù)的優(yōu)化動(dòng)態(tài)規(guī)劃算法。通過(guò)在同樣的機(jī)器上面運(yùn)行程序的時(shí)間復(fù)雜度和空間復(fù)雜度的實(shí)驗(yàn)表明，利用線段樹(shù)改進(jìn)后的動(dòng)態(tài)規(guī)劃算法改進(jìn)后的算法都能有效的提高時(shí)間復(fù)雜度;而隨著數(shù)組數(shù)值的增大，時(shí)間復(fù)雜度的優(yōu)勢(shì)會(huì)更加明顯。雖然動(dòng)態(tài)規(guī)劃的算法在空間上占有一定優(yōu)勢(shì)，但很明顯在時(shí)間復(fù)雜度上處于劣勢(shì)。對(duì)于利用線段樹(shù)改進(jìn)后的算法嘗試將需要進(jìn)一步研究。

參考文獻(xiàn)（References）

[1] Wei Q L，etc.An optimal control scheme for a class of discrete-

time nonlinear systems with time delays using adaptive dynamic

programming[J].Acta Automatica Sinica，2010，36（1）：121-122.

[2] Vamvoudakis K G，Lewis F L.Online actor-critic algorithm

to solve the continuous-time infinite horizon optimal control

problem[J].Automatica，2010，46（5）：878-879.

[3] Qian Z D，etc.The effect of runner cone design on pressure

oscillation characteristics in a Francis hydraulic turbine[J].Journal

of Power and Energy，2012，226（1）：137-150.

作者簡(jiǎn)介：

鄒玉金（1979-），男，碩士， 副教授.研究領(lǐng)域：計(jì)算機(jī)應(yīng)用，

電子商務(wù).endprint