鄒玉金

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

ZOU Yujin

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

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

鄒玉金

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

討論了基于RMQ的一種動(dòng)態(tài)規(guī)劃基本思想和解題步驟.利用線段樹(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)題.

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

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

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

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

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

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

本文所討論一類(lèi)動(dòng)態(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)轉(zhuǎn)移的方式數(shù)

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

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

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

Print(DP[N])；

}

由以上標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法可以看出，如果動(dòng)態(tài)規(guī)劃狀態(tài)為S，那么整個(gè)算法的復(fù)雜度為O(S×N).

2 線段樹(shù)

2.1 線段樹(shù)定義

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

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

圖1 T[1,8]線段樹(shù) Fig.1 T [1,8] segment tree

2.2 線段樹(shù)的定義及性質(zhì)

定義1 長(zhǎng)度為1的線段稱為元線段.

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

1)該樹(shù)是一棵二叉樹(shù)；

2)樹(shù)中每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一條線段[a,b]；

3)樹(shù)中的所有葉子結(jié)點(diǎn)所代表的線段都是元線段；

4)樹(shù)中的非葉子結(jié)點(diǎn)都有左子樹(shù)和右子樹(shù)，左子樹(shù)根結(jié)點(diǎn)對(duì)應(yīng)線段[a,(a+b)/2]，右子樹(shù)根結(jié)點(diǎn)對(duì)應(yīng)線段[(a+b)/2,b].

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

遞歸定義T[a,b]：

T[a, (a+b)/2]為T(mén)的左子樹(shù)，T[(a+b)/2,b]為T(mén)的右子樹(shù)(l>1).T為一個(gè)葉子結(jié)點(diǎn)(l=1).

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

性質(zhì)1 長(zhǎng)度范圍為[1,l]的一棵線段樹(shù)的深度不超過(guò)log(l-1)+1.

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

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

2.3 線段樹(shù)的數(shù)據(jù)結(jié)構(gòu)和初始化構(gòu)造

為方便使用，可以用結(jié)構(gòu)體定義線段樹(shù)結(jié)點(diǎn)如下：

struct SegNode

{

int left, right；

int v；

} tree[MAXN*4]；

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

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

Build_Segment_Tree(left, right)

Init The Node[left, right]

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

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

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

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

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

3.1 線段樹(shù)的插入算法

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

{

if(tree[id][p].left == left && tree[id][p].right == right) //所要查詢的區(qū)間與樹(shù)結(jié)點(diǎn)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)；

//更新結(jié)點(diǎn)的權(quán)值

…

}

對(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)[7].

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

3.2 線段樹(shù)的查詢算法

線段樹(shù)支持各種查詢操作，例如要查詢一個(gè)結(jié)點(diǎn)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ū)間與結(jié)點(diǎn)相匹配，則找到該結(jié)點(diǎn)，返回；否則根據(jù)折半求出中值，判斷是在左子樹(shù)還是右子樹(shù)，根據(jù)判斷的結(jié)果分別在左子樹(shù)或右子樹(shù)查找.

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

由于線段樹(shù)結(jié)構(gòu)的遞歸定義，線段樹(shù)的測(cè)度也可以遞歸定義，增加SegNode.m表示以該結(jié)點(diǎn)為根的子樹(shù)的測(cè)度.m可以通過(guò)以下方式求得：

(1)

4 RMQ問(wèn)題

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

圖2 RMQ定義

圖3 ST算法的描述

4.1 RMQ定義

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

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

4.2 解決RMQ問(wèn)題的常見(jiàn)算法

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

1)線性掃描算法

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

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

2)線段樹(shù)實(shí)現(xiàn)

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

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

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

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

(2)

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

(3)

所以總的算法復(fù)雜度為.

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

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

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

有一個(gè)比較明顯的樸素的O(N2×M)的動(dòng)態(tài)規(guī)劃算法:

對(duì)每個(gè)村莊先預(yù)處理一下(O(N×log(N)的復(fù)雜度))，對(duì)于每個(gè)村莊I，如果該村莊建一個(gè)郵局，那么用left[I]表示第I他能夠覆蓋到的最左邊的村莊，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(N2×M).

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

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

5.2 利用RMQ改進(jìn)動(dòng)態(tài)規(guī)劃算法

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

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

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

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

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

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

6 算法驗(yàn)證及分析

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

以簡(jiǎn)單的求和為例.設(shè)原數(shù)組為a[1…N]，樹(shù)狀數(shù)組為c[1…N]，其中c[k]=a[k-(2t)+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ù)雜度是O(logN)(N為最大范圍).

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

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

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

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

7 結(jié)語(yǔ)

本文提出一種基于線段樹(shù)和RMQ的優(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ī)劃算法和利用RMQ改進(jìn)后的算法都能有效的提高時(shí)間復(fù)雜度；而隨著數(shù)組數(shù)值的增大，時(shí)間復(fù)雜度的優(yōu)勢(shì)會(huì)更加明顯；利用RMQ改進(jìn)的算法時(shí)間復(fù)雜度是最低的.雖然動(dòng)態(tài)規(guī)劃的算法在空間上占有一定優(yōu)勢(shì)，但很明顯在時(shí)間復(fù)雜度上處于劣勢(shì).由此可見(jiàn)利用RMQ改進(jìn)后的算法具有絕對(duì)的優(yōu)勢(shì).對(duì)于利用RMQ改進(jìn)后的算法嘗試將需要進(jìn)一步研究.

[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]盧照，師軍.并行最短路徑搜索算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(3):69-71.

責(zé)任編輯：時(shí)凌

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.

浙江省自然科學(xué)基金項(xiàng)目(LQ13G02000).

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

TP301

A

1008-8423(2014)04-0430-06

ZOU Yujin

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