一種基于線段樹的動態規劃優化算法

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

關鍵詞：動態規劃;數據結構;線段樹

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

1?? 引言（Introduction）

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

2?? 線段樹（Segment tree）

2.1?? 線段樹定義

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

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

2.2?? 線段樹的基本操作

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

（1）線段樹的插入算法

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

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

（2）線段樹的查詢算法

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

3?? 優化動態規劃算法（Optimization of dynamic

programming algorithm）

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

3.1?? 典型的動態規劃算法

有一個比較明顯的樸素的O（N^2*M）的動態規劃算法：

我們對每個村莊先預處理一下（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]}---跟上面的情況相比，這種是在區間[right[k]+1，left[i]-1]之間的村莊都未被村莊i和村莊k覆蓋到，即right[k]

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

O（N*M）的狀態，O（N）的轉移，所以算法總的復雜度為O（N^2*M）。

3.2?? 利用線段樹改進動態規劃算法

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

通過適當的選取數據結構，把狀態轉移的時間降到O（Log（N））甚至O（1）使得整個算法的復雜度為O（S*log（N））或O（S）。

這樣改進的地方在于狀態轉移：

①對于求A的狀態轉移

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

②對于求B的狀態轉移

B=Min{dp[k][j-1]+C[i]+Cost[right[k]+1][left[i]-1]}，由于Cost[right[k]+1][left[i]-1]的值與下標k有關，所以不能像求A一樣，直接把原狀態存入線段樹。我們令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]，狀態轉移的復雜度由原來的O（N）降到了O（log（N）），從而使整個算法的復雜度從O（N^2*M）降到了O（N*M*log（N））。

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

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

algorithm）

樹狀數組是一個可以很高效的進行區間統計的數據結構。在思想上類似于線段樹，比線段樹節省空間，編程復雜度比線段樹低，但適用范圍比線段樹小。

以簡單的求和為例。設原數組為a[1...N]，樹狀數組為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這一段數的和。設一個函數lowestbit（k）為取得k的最低非零位，容易發現，根據上面的表示方法，從a[1]到a[k]的所有數的總和即為sum[k]=c[k]+c[k-lowestbit（k）]+c[k-lowestbit（k）-lowestbit（k-lowestbit（k））]+...于是可以在logk的時間內求出sum[k]。當數組中某元素發生變化時，需要改動的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]的總和。可以用類似的方法進行處理，復雜度為（logn）^k（k為維數）。

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

5?? 結論（Conclusion）

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

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