基于RMQ的一種優(yōu)化動態(tài)規(guī)劃算法
——以ACM郵局選址問題為例

鄒玉金

(浙江經(jīng)貿(mào)職業(yè)技術學院 信息技術系，浙江 杭州 310018)

ZOU Yujin

(Department of Information Technology,Zhejiang Economic and Trade Polytechnic,Hangzhou 310018,China)

基于RMQ的一種優(yōu)化動態(tài)規(guī)劃算法
——以ACM郵局選址問題為例

鄒玉金

(浙江經(jīng)貿(mào)職業(yè)技術學院 信息技術系，浙江 杭州 310018)

討論了基于RMQ的一種動態(tài)規(guī)劃基本思想和解題步驟.利用線段樹優(yōu)化動態(tài)規(guī)劃，提高對大規(guī)模數(shù)據(jù)處理的方法和技巧，在線段樹基礎上利用樹狀數(shù)組合理地解決了動態(tài)規(guī)劃占用大量內(nèi)存的問題.

動態(tài)規(guī)劃；數(shù)據(jù)結構；線段樹；RMQ；優(yōu)化算法

動態(tài)規(guī)劃與分治法和貪心法類似，它們都是將問題分解為更小的、相似的子問題，但是動態(tài)規(guī)劃又有自己的特點[1-3].動態(tài)規(guī)劃可以很好地解決滿足最優(yōu)化原理和無后效性的問題，動態(tài)規(guī)劃將原來具有指數(shù)級復雜度的搜索算法改進成了具有多項式時間的算法.但是由動態(tài)規(guī)劃的基本思想可以知道其基本思路是，用一個表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計算過，就將其結果填入表中.

動態(tài)規(guī)劃實際上是采取以空間換取時間的方法，可以在時間上提高效率，但它的空間復雜程度要大于其他算法.動態(tài)規(guī)劃往往是針對最優(yōu)化問題，由于各種最優(yōu)化問題的性質不同，確定最優(yōu)解的條件也互不相同，因而不存在一種萬能的動態(tài)規(guī)劃算法可以解決各類最優(yōu)化問題.在動態(tài)規(guī)劃中有一大類問題都需要對狀態(tài)轉移進行掃描，但如果采用線性掃描，效率會非常低，尤其是數(shù)據(jù)量龐大的情況下[4].

1 動態(tài)規(guī)劃的基本算法

一般解動態(tài)規(guī)劃的問題分三步：①確定問題的狀態(tài)表示；②確定狀態(tài)的轉移；③確定初始條件.其中狀態(tài)的表示是關鍵，確定了狀態(tài)的表示往往已經(jīng)解決了問題的一半.本文主要討論的是第二步——狀態(tài)轉移.在動態(tài)規(guī)劃中有一大類問題是：如果在狀態(tài)轉移的時候采用線性掃描的方式進行狀態(tài)轉移，往往會造成效率的低下[5].本文以Post Office為例詳細討論了如何選擇合適的數(shù)據(jù)結構，減少狀態(tài)轉移的時間，從而減少動態(tài)規(guī)劃整個算法的時間.

動態(tài)規(guī)劃的主要難點在于理論上的設計，一旦設計完成，實現(xiàn)部分就會非常簡單.根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計算最優(yōu)值，但是一般將其改為遞推計算，實現(xiàn)的大體上的框架如下：

本文所討論一類動態(tài)規(guī)劃算法的基本框架(DP[state]表示狀態(tài)為state的最優(yōu)值)

DP[] = 初始值； {初始化}

For every state DP[i] that have been calculated

For(j = 1； j < N； j++) //N為狀態(tài)轉移的方式數(shù)

NewState = Trans(DP[i], j)；

If DP[NewState] > DP[i]+Cost[]//Cost[]表示這次狀態(tài)轉移所需的花費

DP[NewState] = DP[i]+Cost[]

Print(DP[N])；

}

由以上標準動態(tài)規(guī)劃算法可以看出，如果動態(tài)規(guī)劃狀態(tài)為S，那么整個算法的復雜度為O(S×N).

2 線段樹

2.1 線段樹定義

目前，利用線段樹、RMQ等數(shù)據(jù)結構來優(yōu)化動態(tài)規(guī)劃算法的還比較少，主要是ACM程序設計競賽中有少量的實踐.國家隊林濤在2004年提出了線段樹在區(qū)間操作方便的應用.

本文討論的是一維的線段樹，它支持插入、修改、刪除等一些基本的操作，并且復雜度均為O(log(N))[6].二維和高維的線段樹也可以用與本文相類似的方法實現(xiàn).

圖1 T[1,8]線段樹 Fig.1 T [1,8] segment tree

2.2 線段樹的定義及性質

定義1 長度為1的線段稱為元線段.

定義2 線段樹是一種特殊的數(shù)據(jù)結構，一棵樹被稱為線段樹，當且僅當這棵樹滿足：

1)該樹是一棵二叉樹；

2)樹中每一個結點對應一條線段[a,b]；

3)樹中的所有葉子結點所代表的線段都是元線段；

4)樹中的非葉子結點都有左子樹和右子樹，左子樹根結點對應線段[a,(a+b)/2]，右子樹根結點對應線段[(a+b)/2,b].

將該線段樹記為T[a,b]，參數(shù)a,b表示該結點表示區(qū)間[a,b]，區(qū)間的長度b-a記為L.

遞歸定義T[a,b]：

T[a, (a+b)/2]為T的左子樹，T[(a+b)/2,b]為T的右子樹(l>1).T為一個葉子結點(l=1).

表示區(qū)間[1, 8]的線段樹表示如圖1所示.線段樹有兩個基本性質：

性質1 長度范圍為[1,l]的一棵線段樹的深度不超過log(l-1)+1.

性質2 線段樹把區(qū)間上的任意一條線段都分成不超過2logl條線段.

線段樹的兩個性質為線段樹能在O(logl)的時間內(nèi)完成一條線段的插入、刪除、查找等工作提供了理論依據(jù).

2.3 線段樹的數(shù)據(jù)結構和初始化構造

為方便使用，可以用結構體定義線段樹結點如下：

struct SegNode

{

int left, right；

int v；

} tree[MAXN*4]；

left和right分別表示線段樹對應區(qū)間為[left,right]，v為區(qū)間內(nèi)最小值的點.這里介紹的只是線段樹的基本結構，在實際使用中經(jīng)常根據(jù)需要在每個結點上增加一些特殊的數(shù)據(jù)域，以便對線段樹的數(shù)據(jù)進行動態(tài)維護.

根據(jù)線段樹的定義，可以采用遞歸的形式初始化構造線段樹：

Build_Segment_Tree(left, right)

Init The Node[left, right]

If Node[left, right] is not a leaf //這里規(guī)定區(qū)間長度為1的結點為葉結點

Build_Segment_Tree(left, (left+right)/2)；

Build_Segment_Tree((left+right)/2, right)；

3 線段樹的基本操作

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

3.1 線段樹的插入算法

void SegTreeInsert(int id, int p, int left, int right, int v)

{

if(tree[id][p].left == left && tree[id][p].right == right) //所要查詢的區(qū)間與樹結點p的區(qū)間相匹配

{

if(tree[id][p].v > v) tree[id][p].v = v；

return ；

}

int mid = (tree[id][p].left+tree[id][p].right)/2；//取中值

if(left < mid) //在左邊

SegTreeInsert(id, p*2, left, right, v)；

else //在右邊

SegTreeInsert(id, (p*2)+1, left, right, v)；

//更新結點的權值

…

}

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

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

3.2 線段樹的查詢算法

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

Query(Interval v)

If v is a leaf

return；

else If v is not a leaf:

If q is in the left child of v then

Perform a query in the left child of v.

Else

Perform a query in the right child of v.

如果所查詢的區(qū)間與結點相匹配，則找到該結點，返回；否則根據(jù)折半求出中值，判斷是在左子樹還是右子樹，根據(jù)判斷的結果分別在左子樹或右子樹查找.

當然，線段樹的查詢操作還表現(xiàn)在它的統(tǒng)計功能中.在統(tǒng)計功能中常用到線段樹的測度這個術語.所謂線段樹的測度，就是指區(qū)間中線段覆蓋的長度，通常用m來表示.比如，在線段樹T[1，8]，該區(qū)間[1，8]上有一條線段[4，7]，其測度應該是3.

由于線段樹結構的遞歸定義，線段樹的測度也可以遞歸定義，增加SegNode.m表示以該結點為根的子樹的測度.m可以通過以下方式求得：

(1)

4 RMQ問題

合理利用線段樹能有效地提高動態(tài)規(guī)劃算法，減少動態(tài)規(guī)劃中對狀態(tài)轉移掃描的時間，由原來的o(N)提高到o(logN)，從而使動態(tài)規(guī)劃的整個算法由原來的o(N3)降為o(N2logN).但采用線段樹改進動態(tài)規(guī)劃算法后帶來了一個新的問題，那就是線段樹的插入、刪除及查詢操作增加了程序編寫的復雜程度和代碼量[8]，據(jù)實驗統(tǒng)計，平均代碼量增加約20%.因此很有必要對線段樹優(yōu)化動態(tài)規(guī)劃算法做進一步優(yōu)化，以減少程序編寫復雜程度和代碼量.經(jīng)過大量類似問題的分析和在程序設計競賽中的檢驗，發(fā)現(xiàn)多數(shù)線段樹優(yōu)化問題可合理利用RMQ(range minimum/maximum query)問題中常用的ST算法做進一步的優(yōu)化，從而使程序編寫代碼量減少，在不改變時間復雜程度的情況下，使基本操作減少，從而使效率再提高2～5倍.

圖2 RMQ定義

圖3 ST算法的描述

4.1 RMQ定義

給定一個數(shù)組A[0，n-1]，對于任意一個區(qū)間內(nèi)，要求求出這個區(qū)間內(nèi)的最小(大)值.用RMQA(i,j).表示在一個數(shù)組A中，A[i…,j]一串連續(xù)的數(shù)中的最小值.

用表示一個算法需要O(F(N))的預處理時間和O(G(N))的查詢時間.

4.2 解決RMQ問題的常見算法

解決RMQ問題存在很多算法，這里重點介紹ST(Sparse Table)算法.

1)線性掃描算法

這是最簡單的算法，對于每個詢問RMQA(i,j).我們只要數(shù)組的第i個位置開始掃描到達位置j保存一個最小值.算法的復雜度為，對于這種算法，只要查詢的次數(shù)比較多的時候，復雜度是吃不消的.

例如查詢次數(shù)M=10000則整個復雜度為O(N*M).

2)線段樹實現(xiàn)

用線段樹我們可以獲得一個的算法.線段樹之所以強大它是一種非常具有彈性的數(shù)據(jù)結構，能夠解決各式各樣的統(tǒng)計問題，尤其是在區(qū)間搜索問題上.

3)ST算法(sparse table (ST) algorithm)

第一種方法最簡單，但是效率很低，第二種方法比較容易想到，但是編程的復雜度比較高，ST算法是一個更好的算法，他的時間效率很高，而且編程量很小.它主要的思想是利用動態(tài)規(guī)劃的原理.用一個二維數(shù)組M[0,N-1][0,logN]，M[i][j]表示數(shù)組A從第i個位置開始一段長為2j的數(shù)中的最小(大)值(如圖3所示).

要計算M[i][j]，必須搜索這段區(qū)間的前半部分和后半部分.利用M[i][j]的定義，兩部分就是兩端長度為2(j-1)的區(qū)間.可以比較容易的得到如下的狀態(tài)轉移方程：

(2)

剩下的問題就是，對于任意一個詢問RMQA(i,j)怎樣確定這段區(qū)間內(nèi)的最小(大)值.這里的思想就是把這段區(qū)間分成兩部分，而且要求這段區(qū)間必須覆蓋區(qū)間[i,j].令k=[log(j-i+1)].如果要計算RMQA(i,j)的話，可以用如下的方程.

(3)

所以總的算法復雜度為.

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

下面以郵局選址問題為例，以上面介紹的方法進行分析.

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

有一個比較明顯的樸素的O(N2×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(N2×M).

圖4 第一種狀態(tài)轉移(A)

圖5 第二種狀態(tài)轉移(B)

5.2 利用RMQ改進動態(tài)規(guī)劃算法

本題需要的操作有1個：查詢一段區(qū)間內(nèi)的最小值.

只要開兩個RMQ數(shù)組，分別實現(xiàn)狀態(tài)轉移A和狀態(tài)轉移B，也可以完成線段樹的功能.

對于這個操作，RMQ(range minimum query)也可以在O(1)實現(xiàn)查詢，O(N×log(N))構造RMQ，在查詢上比線段樹更加優(yōu)秀，而且編程復雜度大大降低(可以將近減少50行的代碼量).

實踐證明RMQ效率也遠高于線段樹：快了將近5倍.跟線段樹相比，總的算法復雜度沒有改變，但是在時間效率上有這么大的提高，主要原因有以下幾點：

1)雖然總的復雜度相同，但是線段樹在查詢時候的復雜度為O(log(N))，而RMQ的ST算法在查詢時，復雜度為O(1).

2)觀察代碼可以發(fā)現(xiàn)，RMQ ST算法實現(xiàn)相當簡單，只有十來行，而線段樹涉線段樹的構造，查詢都涉及到了遞歸，而且里面有很多的基本操作.不像ST算法里面只有兩層循環(huán)和幾次比較操作.所以雖然算法復雜度相同但是，前面的常系數(shù)卻又很大的不同.

6 算法驗證及分析

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

以簡單的求和為例.設原數(shù)組為a[1…N]，樹狀數(shù)組為c[1…N]，其中c[k]=a[k-(2t)+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的時間內(nèi)求出sum[k].當數(shù)組中某元素發(fā)生變化時，需要改動的c值是c[k],c[k+lowestbit(k)],c[k+lowestbit(k)+lowestbit(k+lowestbit(k))]…這個復雜度是O(logN)(N為最大范圍).

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

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

表1 數(shù)據(jù)驗證A

表2 數(shù)據(jù)驗證B

7 結語

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

[1]Nasreddine, Saadouli. Computationally efficient solution algorithm for a large scale stochastic dynamic program[J].Procedia Computer Science,2010,5(1):1397-1405.

[2]Mario R F.Benevides,L J.Menasché Schechter.A Propositional Dynamic Logic for Concurrent Programs Based on the π-Calculus[J].Electronic Notes in Theoretical Computer Science,2010,262(12):49-64.

[3]Tayssir Touili,Mohamed Faouzi Atig.Verifying parallel programs with dynamic communication structures[J].Theoretical Computer Science, 2010, 411(38):3460-3468.

[4]Ganesh Janakiraman,Sridhar Seshadri.Parametric concavity in stochastic dynamic programs[J].Computers & Industrial Engineering,2011,61(8):98-102.

[5]Wei Q L,Zhang H G,Liu D R,et al.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.

[6]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.

[7]Qian Z D,Li W,Huai W X,et al.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.

[8]盧照，師軍.并行最短路徑搜索算法的設計與實現(xiàn)[J].計算機工程與應用,2010,46(3):69-71.

責任編輯：時凌

OptimalDynamicProgrammingAlgorithmBasedonRMQ

This paper discusses the basic idea of the dynamic programming and problem-solving steps based on RMQ. Using segment tree optimization dynamic programming problem cleverly, we can improve methods and techniques for large-scale data processing, and rationally solve the problem of dynamic programming running memory intensively by the tree array which based on the segment tree.

dynamic programming;data structure;segment tree;RMQ;optimization algorithm

2014-11-01.

浙江省自然科學基金項目(LQ13G02000).

鄒玉金(1979-)，男，碩士，副教授，主要從事計算機應用、電子商務有研究.

TP301

A

1008-8423(2014)04-0430-06

ZOU Yujin

(Department of Information Technology,Zhejiang Economic and Trade Polytechnic,Hangzhou 310018,China)