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

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

關鍵詞：動態(tài)規(guī)劃;數(shù)據(jù)結構;線段樹

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

1?? 引言（Introduction）

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

2?? 線段樹（Segment tree）

2.1?? 線段樹定義

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

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

2.2?? 線段樹的基本操作

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

（1）線段樹的插入算法

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

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

（2）線段樹的查詢算法

線段樹支持各種查詢操作，例如要查詢一個結點q在區(qū)間Interval v位置，我們仍然以較為容易理解的遞歸的形式執(zhí)行查詢操作。

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

programming algorithm）

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

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

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

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

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

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

令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）的轉移，所以算法總的復雜度為O（N^2*M）。

3.2?? 利用線段樹改進動態(tài)規(guī)劃算法

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

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

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

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

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

②對于求B的狀態(tài)轉移

B=Min{dp[k][j-1]+C[i]+Cost[right[k]+1][left[i]-1]}，由于Cost[right[k]+1][left[i]-1]的值與下標k有關，所以不能像求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無關，這樣同樣利用求A的方法，可以求得B。

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

這里有個很好的優(yōu)化：假如，我們已經求出了建設對于N個村莊，建設j個郵局的最優(yōu)值a，在我們利用動態(tài)規(guī)劃求出建設N個村莊建設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é)省空間，編程復雜度比線段樹低，但適用范圍比線段樹小。

以簡單的求和為例。設原數(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ù)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的時間內求出sum[k]。當數(shù)組中某元素發(fā)生變化時，需要改動的c值是c[k]，

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

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

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

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

5?? 結論（Conclusion）

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

參考文獻（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-），男，碩士， 副教授.研究領域：計算機應用，

電子商務.endprint