基于RMQ的一种优化动态规划算法
——以ACM邮局选址问题为例
2014-08-25邹玉金
邹玉金
(浙江经贸职业技术学院 信息技术系，浙江 杭州 310018)
ZOU Yujin
(Department of Information Technology,Zhejiang Economic and Trade Polytechnic,Hangzhou 310018,China)
基于RMQ的一种优化动态规划算法
——以ACM邮局选址问题为例
邹玉金
(浙江经贸职业技术学院 信息技术系，浙江 杭州 310018)
讨论了基于RMQ的一种动态规划基本思想和解题步骤.利用线段树优化动态规划，提高对大规模数据处理的方法和技巧，在线段树基础上利用树状数组合理地解决了动态规划占用大量内存的问题.
动态规划；数据结构；线段树；RMQ；优化算法
动态规划与分治法和贪心法类似，它们都是将问题分解为更小的、相似的子问题，但是动态规划又有自己的特点[1-3].动态规划可以很好地解决满足最优化原理和无后效性的问题，动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法.但是由动态规划的基本思想可以知道其基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中.
动态规划实际上是采取以空间换取时间的方法，可以在时间上提高效率，但它的空间复杂程度要大于其他算法.动态规划往往是针对最优化问题，由于各种最优化问题的性质不同，确定最优解的条件也互不相同，因而不存在一种万能的动态规划算法可以解决各类最优化问题.在动态规划中有一大类问题都需要对状态转移进行扫描，但如果采用线性扫描，效率会非常低，尤其是数据量庞大的情况下[4].
1 动态规划的基本算法
一般解动态规划的问题分三步：①确定问题的状态表示；②确定状态的转移；③确定初始条件.其中状态的表示是关键，确定了状态的表示往往已经解决了问题的一半.本文主要讨论的是第二步——状态转移.在动态规划中有一大类问题是：如果在状态转移的时候采用线性扫描的方式进行状态转移，往往会造成效率的低下[5].本文以Post Office为例详细讨论了如何选择合适的数据结构，减少状态转移的时间，从而减少动态规划整个算法的时间.
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单.根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：
本文所讨论一类动态规划算法的基本框架(DP[state]表示状态为state的最优值)
DP[] = 初始值； {初始化}
For every state DP[i] that have been calculated
For(j = 1； j < N； j++) //N为状态转移的方式数
NewState = Trans(DP[i], j)；
If DP[NewState] > DP[i]+Cost[]//Cost[]表示这次状态转移所需的花费
DP[NewState] = DP[i]+Cost[]
Print(DP[N])；
}
由以上标准动态规划算法可以看出，如果动态规划状态为S，那么整个算法的复杂度为O(S×N).
2 线段树
2.1 线段树定义
目前，利用线段树、RMQ等数据结构来优化动态规划算法的还比较少，主要是ACM程序设计竞赛中有少量的实践.国家队林涛在2004年提出了线段树在区间操作方便的应用.
本文讨论的是一维的线段树，它支持插入、修改、删除等一些基本的操作，并且复杂度均为O(log(N))[6].二维和高维的线段树也可以用与本文相类似的方法实现.
图1 T[1,8]线段树 Fig.1 T [1,8] segment tree
2.2 线段树的定义及性质
定义1 长度为1的线段称为元线段.
定义2 线段树是一种特殊的数据结构，一棵树被称为线段树，当且仅当这棵树满足：
1)该树是一棵二叉树；
2)树中每一个结点对应一条线段[a,b]；
3)树中的所有叶子结点所代表的线段都是元线段；
4)树中的非叶子结点都有左子树和右子树，左子树根结点对应线段[a,(a+b)/2]，右子树根结点对应线段[(a+b)/2,b].
将该线段树记为T[a,b]，参数a,b表示该结点表示区间[a,b]，区间的长度b-a记为L.
递归定义T[a,b]：
T[a, (a+b)/2]为T的左子树，T[(a+b)/2,b]为T的右子树(l>1).T为一个叶子结点(l=1).
表示区间[1, 8]的线段树表示如图1所示.线段树有两个基本性质：
性质1 长度范围为[1,l]的一棵线段树的深度不超过log(l-1)+1.
性质2 线段树把区间上的任意一条线段都分成不超过2logl条线段.
线段树的两个性质为线段树能在O(logl)的时间内完成一条线段的插入、删除、查找等工作提供了理论依据.
2.3 线段树的数据结构和初始化构造
为方便使用，可以用结构体定义线段树结点如下：
struct SegNode
{
int left, right；
int v；
} tree[MAXN*4]；
left和right分别表示线段树对应区间为[left,right]，v为区间内最小值的点.这里介绍的只是线段树的基本结构，在实际使用中经常根据需要在每个结点上增加一些特殊的数据域，以便对线段树的数据进行动态维护.
根据线段树的定义，可以采用递归的形式初始化构造线段树：
Build_Segment_Tree(left, right)
Init The Node[left, right]
If Node[left, right] is not a leaf //这里规定区间长度为1的结点为叶结点
Build_Segment_Tree(left, (left+right)/2)；
Build_Segment_Tree((left+right)/2, right)；
3 线段树的基本操作
一维线段树能在o(logl)的时间内完成一条线段的插入、删除和查找工作，下面对这些基本操作做简要的说明.
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) //所要查询的区间与树结点p的区间相匹配
{
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的区间相匹配，那么显然该结点上的覆盖线段数为1；否则二分取中值，如在左边则只对左树做插入，如在右边则对右树插入.递归直到所要插入的结点的区间与树结点p的区间相匹配.由于插入时做了二分取中值，故时间复杂度为o(logN)[7].
线段树的删除算法跟插入算法类似，这里就不再详细展开.
3.2 线段树的查询算法
线段树支持各种查询操作，例如要查询一个结点q在区间Intervalv位置，仍然以较为容易理解的递归的形式执行查询操作.
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.
如果所查询的区间与结点相匹配，则找到该结点，返回；否则根据折半求出中值，判断是在左子树还是右子树，根据判断的结果分别在左子树或右子树查找.
当然，线段树的查询操作还表现在它的统计功能中.在统计功能中常用到线段树的测度这个术语.所谓线段树的测度，就是指区间中线段覆盖的长度，通常用m来表示.比如，在线段树T[1，8]，该区间[1，8]上有一条线段[4，7]，其测度应该是3.
由于线段树结构的递归定义，线段树的测度也可以递归定义，增加SegNode.m表示以该结点为根的子树的测度.m可以通过以下方式求得：
(1)
4 RMQ问题
合理利用线段树能有效地提高动态规划算法，减少动态规划中对状态转移扫描的时间，由原来的o(N)提高到o(logN)，从而使动态规划的整个算法由原来的o(N3)降为o(N2logN).但采用线段树改进动态规划算法后带来了一个新的问题，那就是线段树的插入、删除及查询操作增加了程序编写的复杂程度和代码量[8]，据实验统计，平均代码量增加约20%.因此很有必要对线段树优化动态规划算法做进一步优化，以减少程序编写复杂程度和代码量.经过大量类似问题的分析和在程序设计竞赛中的检验，发现多数线段树优化问题可合理利用RMQ(range minimum/maximum query)问题中常用的ST算法做进一步的优化，从而使程序编写代码量减少，在不改变时间复杂程度的情况下，使基本操作减少，从而使效率再提高2～5倍.
图2 RMQ定义
图3 ST算法的描述
4.1 RMQ定义
给定一个数组A[0，n-1]，对于任意一个区间内，要求求出这个区间内的最小(大)值.用RMQA(i,j).表示在一个数组A中，A[i…,j]一串连续的数中的最小值.
用
4.2 解决RMQ问题的常见算法
解决RMQ问题存在很多算法，这里重点介绍ST(Sparse Table)算法.
1)线性扫描算法
这是最简单的算法，对于每个询问RMQA(i,j).我们只要数组的第i个位置开始扫描到达位置j保存一个最小值.算法的复杂度为
例如查询次数M=10000则整个复杂度为O(N*M).
2)线段树实现
用线段树我们可以获得一个
3)ST算法(sparse table (ST) algorithm)
第一种方法最简单，但是效率很低，第二种方法比较容易想到，但是编程的复杂度比较高，ST算法是一个更好的算法，他的时间效率很高，而且编程量很小.它主要的思想是利用动态规划的原理.用一个二维数组M[0,N-1][0,logN]，M[i][j]表示数组A从第i个位置开始一段长为2j的数中的最小(大)值(如图3所示).
要计算M[i][j]，必须搜索这段区间的前半部分和后半部分.利用M[i][j]的定义，两部分就是两端长度为2(j-1)的区间.可以比较容易的得到如下的状态转移方程：
(2)
剩下的问题就是，对于任意一个询问RMQA(i,j)怎样确定这段区间内的最小(大)值.这里的思想就是把这段区间分成两部分，而且要求这段区间必须覆盖区间[i,j].令k=[log(j-i+1)].如果要计算RMQA(i,j)的话，可以用如下的方程.
(3)
所以总的算法复杂度为
5 优化动态规划算法
下面以邮局选址问题为例，以上面介绍的方法进行分析.
5.1 典型的动态规划算法
有一个比较明显的朴素的O(N2×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(N2×M). 图4 第一种状态转移(A) 图5 第二种状态转移(B) 5.2 利用RMQ改进动态规划算法 本题需要的操作有1个：查询一段区间内的最小值. 只要开两个RMQ数组，分别实现状态转移A和状态转移B，也可以完成线段树的功能. 对于这个操作，RMQ(range minimum query)也可以在O(1)实现查询，O(N×log(N))构造RMQ，在查询上比线段树更加优秀，而且编程复杂度大大降低(可以将近减少50行的代码量). 实践证明RMQ效率也远高于线段树：快了将近5倍.跟线段树相比，总的算法复杂度没有改变，但是在时间效率上有这么大的提高，主要原因有以下几点： 1)虽然总的复杂度相同，但是线段树在查询时候的复杂度为O(log(N))，而RMQ的ST算法在查询时，复杂度为O(1). 2)观察代码可以发现，RMQ ST算法实现相当简单，只有十来行，而线段树涉线段树的构造，查询都涉及到了递归，而且里面有很多的基本操作.不像ST算法里面只有两层循环和几次比较操作.所以虽然算法复杂度相同但是，前面的常系数却又很大的不同. 树状数组是一个可以很高效的进行区间统计的数据结构.在思想上类似于线段树，比线段树节省空间，编程复杂度比线段树低，但适用范围比线段树小. 以简单的求和为例.设原数组为a[1…N]，树状数组为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这一段数的和.设一个函数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))]…这个复杂度是O(logN)(N为最大范围). 扩展到多维情况：以二维为例，用c[k1][k2]表示c[k1-(2t1)+1][k2-(2t2)+1]+…+c[k1][k2]的总和.可以用类似的方法进行处理.复杂度为O(logn)k(k为维数) 树状数组相比线段树的优势：空间复杂度略低，编程复杂度低，容易扩展到多维情况.劣势：适用范围小，对可以进行的运算也有限制，比如每次要查询的是一个区间的最小值，似乎就没有很好的解决办法. 表1 数据验证A 表2 数据验证B 本文提出一种基于线段树和RMQ的优化动态规划算法.通过在同样的机器上面运行程序的时间复杂度和空间复杂度的实验表明，利用线段树改进后的动态规划算法和利用RMQ改进后的算法都能有效的提高时间复杂度；而随着数组数值的增大，时间复杂度的优势会更加明显；利用RMQ改进的算法时间复杂度是最低的.虽然动态规划的算法在空间上占有一定优势，但很明显在时间复杂度上处于劣势.由此可见利用RMQ改进后的算法具有绝对的优势.对于利用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]卢照，师军.并行最短路径搜索算法的设计与实现[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)
6 算法验证及分析
7 结语
