基本动态规划问题的扩展(国家集训队 俞玮)

ACM

基本动态规划问题的扩展

应用动态规划可以有效的解决许多问题，其中有许多问题的数学模型，尤其对一些自从57年就开始研究的基本问题所应用的数学模型，都十分精巧。有关这些问题的解法，我们甚至可以视为标准——也就是最优的解法。不过随着问题规模的扩大化，有些模型显出了自身的不足和缺陷。这样，我们就需要进一步优化和改造这些模型。

一. 程序上的优化：

程序上的优化主要依赖问题的特殊性。我们以f(XT)= opt{f(uT)}+ A(XT), uT Pred_Set(XT)这样的递推方程式为例（其中A(XT)为一个关于XT的确定函数，Pred_Set(XT)表示XT的前趋集）。我们设状态变量XT的维数为t，每个XT与前趋中有e维改变，则我们可以通过方程简单的得到一个时间复杂度为O(nt+e)的算法。

当然，个XT所对应的g(XT)=opt{f(uT)}，则f(XT)=g(XT)+A(XT)，问题就变为求g(XT个方面讨论这个问题：

1. Pred_Set(XT)为连续集：

在这样的情况下，我们可以用g(XT)= opt{g(Pred(XT这样一个方程式来求出g(XT)的值，并再用g(XT)的值求出f(XT)的值。这样，g(XT)和f(XT)分别作了一次动态规划，O(nt)。由IOI’99O(FV2)降为O(FV)。

2. Pred_Set(XT)为与XT有关的集合：

这样的问题比较复杂，我们以最降子序列问题为例。规划方程为：f(i)=max{f(j)}+1, d[i]≥ d[j]; i>jO(n2)。不过，这个问题只多了一个d[i]是不是也可以优化呢？我们注意到max{f(j)}的部分，它的时间复杂度为来使这个maxO(log n)。对于该问题，我们也可以用这样的方法。在计算d[i]时，（例如红黑树）对d[1]~d[i-1]进行排序。MAX域记录它的左子树中的函数f的最大值。这样，我们在计算f(i)O(log n)时间找出不比d[i]大的最大数所对应的节点，并用O(1)域就可以得出f(i)的值。并且，插入操作和更新MAX域的操的时间（我们不需要删除操作），故总时间复杂度为O(n log n)。实n=10000时用不到1秒就可以得出结果，而原来的30

再从程序设计上对问题优化时，要尽量减少问题的约束，尽可1。若不可以变为情况1，那么就要仔细考虑数据上的联系，设计好的数据结构来解决问题。

二. 方程上的优化：

对于方程上的优化，其主要的方法就是通过某些数学结论对方程进行优化，避免不必要的运算。对于某一些特殊的问题，我们可以使用数学分析的方法对写出的方程求最值，这样甚至不用状态之间的递推计算就可以解决问题。不过用该方法解决的问题数量是在有限，并且这个方法也十分复杂。不过，却的确有相当数量的比较一般的问题，在应用某些数学结论后，可以提高程序的效率。

一个比较典型的例子是最优排序二叉树问题（CTSC96）。它的规划方程如下：

C[i,j]=w(i,j)+min{C[i,k 1] C[k,j]}|1 i j n i k j

ACM

我们可以从这个规划方程上简单的得到一个时间复杂度为O(n3)的算法。但是否会有更有效的算法呢？我们考虑一下w(i, j)的性质。它表示的是结点i到结点j的频率之和。很明显，若有[i, j] [i’, j’]，则有w[i, j] w[i’, j’]，这样可知C[i, j]具有凸性[1]。为了表示方便，我们记Ck(i, j)=w(i, j)+C[i, k-1]+C[k, j]，并用Ki,j表示取到最优值C[i, j]时的Ck(i, j)的k值。我们令k=Ki,j-1，并取i< k’< k。由于k’< k j-1< j，故有：

C[k’, j-1]+ C[k, j] C[k’, j]+ C[k, j-1]

在等式两侧同时加上w(i, j-1)+ w(i, j)+C[i,. k-1]+ C[i, k’-1]，可得：

Ck’(i, j-1)+ Ck(i, j) Ck’(i, j)+ Ck(i, j-1)

由k的定义可知Ck(i, j-1) Ck’(i, j-1)，故Ck(i, j) Ck’(i, j)，所以k’ Ki,j，故Ki,j Ki,j-1。同理，我们可得Ki,j Ki+1,j，即Ki,j-1 Ki,j Ki+1,j。这样，我们就可以按对角线来划分阶段（就是按照j-i划分阶段）来求Ki,j。求Ki,j的时间复杂度为O(Ki+1,j-Ki,j-1+1)，故第dK1,1+d~Kn-d,n）共需时O(Kn-d+1,n-K1,d+n-d) O(n)。有共有n2)。

虽然这道题由于空间上的限制给这个算法的实际应用造成了困难，们以启示。

我们在考虑IOI2000的POST问题。论，直接给出规划方程Di,j min{Di 1,k w(k,j)}i 1 k j

间复杂度为O(n3)可以把方程变得简单些，变为对如下的方程执行n次：E[j] min{D[i(,j)} j i

在递推时，我们用B[i, j]表示D[i]+w(i, j)并对每一列求最小值。

事实上，这一题的w

对于a b c d，我们有 w(a, d)+ w(b, c)。

仿照上例，在两侧加上D[a]+ D[b]，可得B[a, c]+ B[b, d] B[a, d]+ B[b, c]

也就是说，若，则有B[a, d] B[b, d]。于是我们在确定了B[a, c]与B[b, c]B[a, d]与B[b, d]的大小。

B[a, h] B[b, h]的最小的h，就可以免去h之后对第aO(log n)时间内找到（若w更特殊一些，O(1)的时间找到）。并且对于每一行来说，都只需要h之后，只需用O(n)的时间对每列的第h行求值就可以O(n)+O(n log n)= O(n log n)。至于程序设计上的问题，虽然并不15分钟所可以解决的，也不是重点，略过不谈。[2]不过由于该题目可以用滚动数组的技巧解决空间的问题，故在大数据量时该算法有优异的表现。

从上面的叙述可以看出，对于方程的优化主要取决于权函数w的性质。其中应用最多的就是w(a, c)+ w(b, d) w(a, d)+ w(b, c)这个不等式。实际上，这个式子被称作函数的凸性判定不等式。在实际问题中，权函数通常都会满足这个不等式或这是它的逆不等式。故这样的优化应用是比较广泛的。还有许多特殊的不等式，若可以在程序中应用，都可以提高程序的效率。

三. 从低维向高维的转化：

在问题扩大规模时，有一种方式就是扩大问题的维数。这时，规划时决策变量的维数也要增加。这样，存储的空间也要随着成指数级增加，导致无法存储下所有的状态，这就是动

ACM

态规划的维数灾难问题。如果我们还要在这种情况下使用动态规划，那么就要使用极其复杂的数学分析方法。对于我们来说，使用这种方法显然是不现实的。这时，我们就需要改造动态规划的模型。通常我们都可以把这时的动态规划模型变为网络流模型。

对于模型的转化方法，我们有一些一般的规律。若状态转移方程只与另一个状态有关，我们可以肯定得到一个最小费用最大流的模型[3]。这个模型必然有其规律的地方，甚至用对偶算法在对网络流的求解时也还要用到动态规划的方法。不过这不是重点，我们关心的只是动态规划问题如何转化。例如说IOI’97《火星探测器》一题。这一题的一维模型是可以用动态规划来解决的（这里的维数概念是指探测器的数目）。在维数增加时，我们就可以用该方法来用网络流的方法解决问题。

除此之外，还有许多问题可以用该方法解决。例如最长区间覆盖问题，在维数增加时也同样可以用该方法解决。更进一步来说，特殊的最短路。不过一般来说转化后流量最大为1且些复杂的动态规划问题还无法转化为网络流问题（例如说最优二叉树问题）络流算法显然有些浪费，它的解决还需要进一步的研究。 参考文献：

[EGG88] David Eppstein, Zvi Galil and Raffaele Giancarlo, up Dynamic Programming

[GP90] Zvi Galil and Kunsoo Park, Dynamic Convexity, Concavity, and Sparsity

ACM

[附录]

[1] C[i, j]的凸性是指对于任意的a b c d，都有C[a, c]+ C[b, d] C[a, d]+ C[b, c]。它

的证明如下：

我们设k=Kb,c，则有C[a, c]+ C[b, d] C[a, k-1]+ …… 此处隐藏：2988字，全部文档内容请下载后查看。喜欢就下载吧 ……