一种基于线段树的动态规划优化算法

摘  要：动态规划是解决多阶段决策最优化问题的一种思想方法，也是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