一種基于線段樹的動態(tài)規(guī)劃優(yōu)化算法

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

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

中圖分類號：TP301?????????? 文獻標識碼：A

1?? 引言（Introduction）

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

2?? 線段樹（Segment tree）

2.1?? 線段樹定義

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

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

2.2?? 線段樹的基本操作

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

（1）線段樹的插入算法

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

線段樹的刪除算法跟插入算法類似，這里就不再詳細展開。

（2）線段樹的查詢算法

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

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

programming algorithm）

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

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

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

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

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

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

令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?? 利用線段樹改進動態(tài)規(guī)劃算法

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

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

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

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

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

②對于求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]的值與下標k有關(guān)，所以不能像求A一樣，直接把原狀態(tài)存入線段樹。我們令F[i][j]=dp[i][j]+Cost[right[i]+1][N]也就前面i個村的費用加上后面N-i個村莊的費用（如果該村莊未被覆蓋）。

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

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

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

4?? 算法驗證及分析（Verification and analysis

algorithm）

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

以簡單的求和為例。設(shè)原數(shù)組為a[1...N]，樹狀數(shù)組為c[1...N]，其中c[k]=a[k-（2^t）+1]+...+a[k]。比如c[6]=c[5]+c[6]。也就是說，把k表示成二進制1***10000，那么c[k]就是1***00001+1***00010+...+1***10000這一段數(shù)的和。設(shè)一個函數(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的時間內(nèi)求出sum[k]。當數(shù)組中某元素發(fā)生變化時，需要改動的c值是c[k]，

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

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

擴展到多維情況：以二維為例，用c[k1][k2]表示c[k1-（2^t1）+1][k2-（2^t2）+1]+...+c[k1][k2]的總和?？梢杂妙愃频姆椒ㄟM行處理，復(fù)雜度為（logn）^k（k為維數(shù)）。

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

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

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

參考文獻（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.

作者簡介：

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

電子商務(wù).endprint