《算法合集之《基本动态规划问题的扩展》》由会员分享，可在线阅读，更多相关《算法合集之《基本动态规划问题的扩展》（5页珍藏版）》请在金锄头文库上搜索。
1、基本动态规划问题的扩展基本动态规划问题的扩展应用动态规划可以有效的解决许多问题，其中有许多问题的数学模型，尤其对一些自 从 57 年就开始研究的基本问题所应用的数学模型，都十分精巧。有关这些问题的解法，我 们甚至可以视为标准也就是最优的解法。不过随着问题规模的扩大化，有些模型显出 了自身的不足和缺陷。这样，我们就需要进一步优化和改造这些模型 一. 程序上的优化： 程序上的优化主要依赖问题的特殊性。我们以 f(XT)= optf(uT)+ A(XT), uT Pred_Set(XT)这样的递推方程式为例（其中 A(XT)为一个关于 XT的确定函数，Pred_Set(XT)表 示 XT的前趋集）
2、。我们设状态变量 XT的维数为 t，每个 XT与前趋中有 e 维改变，则我们可 以通过方程简单的得到一个时间复杂度为 O(nt+e)的算法。 当然，这样的算法并不是最好的算法。为了简化问题，得到一个更好的算法。我们设 每个 XT所对应的 g(XT)=optf(uT)，则 f(XT)=g(XT)+A(XT)，问题就变为求 g(XT)的值。下面 分两个方面讨论这个问题： 1.Pred_Set(XT)为连续集： 在这样的情况下，我们可以用 g(XT)= optg(Pred(XT), f(Pred(XT)这样一个方程式 来求出 g(XT)的值，并再用 g(XT)的值求出 f(XT)的值。这样，虽然我们
3、相当于对 g(XT)和 f(XT)分别作了一次动态规划，但由于两个规划是同时进行的，时间复杂度却降为了 O(nt)。由于我们在实际使用中的前趋即通常都是连续的，故这个方法有很多应用。例 如 IOI99 的小花店一题就可以用该方法把表面上的时间复杂度 O(FV2)降为 O(FV)。2.Pred_Set(XT)为与 XT有关的集合： 这样的问题比较复杂，我们以最长不下降子序列问题为例。规划方程为：f(i)=maxf(j)+1, di dj; ij。通常认为，这个问题的最低可行时间复杂度为 O(n2)。不 过，这个问题只多了一个 didj的限制，是不是也可以优化呢？我们注意到 maxf(j) 的部分
4、，它的时间复杂度为 O(n)。但对于这样的式子，我们通常都可以用一个优先队 列来使这个 max 运算的时间复杂度降至 O(log n)。对于该问题，我们也可以用这样的方 法。在计算 di时，我们要先有一个平衡排序二叉树（例如红黑树）对 d1di-1进行 排序。并且我们在树的每一个节点新增一个 MAX 域记录它的左子树中的函数 f 的最大 值。这样，我们在计算 f(i)时，只需用 O(log n)时间找出不比 di大的最大数所对应的 节点，并用 O(1)的时间访问它的 MAX 域就可以得出 f(i)的值。并且，插入操作和更新 MAX 域的操作也都只用 O(log n)的时间（我们不需要删除操作）
5、 ，故总时间复杂度为 O(n log n)。实际运行时这样的程序也是十分快的，n=10000 时用不到 1 秒就可以得出 结果，而原来的程序需要 30 秒。 从以上的讨论可以看出，再从程序设计上对问题优化时，要尽量减少问题的约束，尽 可能的化为情况 1。若不可以变为情况 1，那么就要仔细考虑数据上的联系，设计好的数据 结构来解决问题。 二. 方程上的优化： 对于方程上的优化，其主要的方法就是通过某些数学结论对方程进行优化，避免不必 要的运算。对于某一些特殊的问题，我们可以使用数学分析的方法对写出的方程求最值， 这样甚至不用状态之间的递推计算就可以解决问题。不过用该方法解决的问题数量是在有 限，
6、并且这个方法也十分复杂。不过，却的确有相当数量的比较一般的问题，在应用某些 数学结论后，可以提高程序的效率。 一个比较典型的例子是最优排序二叉树问题（CTSC96） 。它的规划方程如下：nji1|j ,kC1Ci,kmin,j)+Ci,j=w(i jki 我们可以从这个规划方程上简单的得到一个时间复杂度为 O(n3)的算法。但是否会有更 有效的算法呢？我们考虑一下 w(i, j)的性质。它表示的是结点 i 到结点 j 的频率之和。很明 显，若有i, ji, j，则有 wi, j wi, j，这样可知 Ci, j具有凸性1。为了表示方便， 我们记 Ck(i, j)=w(i, j)+Ci, k-1
7、+Ck, j，并用 Ki,j表示取到最优值 Ci, j时的 Ck(i, j)的 k 值。 我们令 k=Ki,j-1，并取 i k k。由于 k k j-1 j，故有：Ck, j-1+ Ck, j Ck, j+ Ck, j-1 在等式两侧同时加上 w(i, j-1)+ w(i, j)+Ci,. k-1+ Ci, 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
8、，即 Ki,j-1Ki,jKi+1,j。这样，我们就可以按对角线来划分阶 段（就是按照 j-i 划分阶段）来求 Ki,j。求 Ki,j的时间复杂度为 O(Ki+1,j-Ki,j-1+1)，故第 d 阶段 （即计算 K1,1+dKn-d,n）共需时 O(Kn-d+1,n-K1,d+n-d) O(n)。有共有 n 个阶段，故总时间复 杂度为 O(n2)。 虽然这道题由于空间上的限制给这个算法的实际应用造成了困难，不过这种方法却给 我们以启示。 我们在考虑 IOI2000 的 POST 问题。这一题的数学模型不是讨论的重点，我们先不加讨论，直接给出规划方程。从规划方程直接得出的算法的)j ,k(wD
9、minDk, 1i jk1ij, i 时间复杂度为 O(n3)。从这个规划方程可以看出，它的每一阶段都只与上一阶段有关。故我 们可以把方程变得简单些，变为对如下的方程执行 n 次：)j , i (wi DminjE ij 在递推时，阶段之间时没有优化的余地的，故优化的重点就在于这个方程的优化上。 我们用 Bi, j表示 Di+w(i, j)，而原算法就是求出 B 并对每一列求最小值。 事实上，这一题的 w 有其特殊的性质： 对于 a b c d，我们有 w(a, c)+ w(b, d) w(a, d)+ w(b, c)。 这一性质对解题是应该有所帮助的。仿照上例，在两侧加上 Da+ Db，可得
10、 Ba, c+ Bb, d Ba, d+ Bb, c。 也就是说，若 Ba, c Bb, c，则有 Ba, d Bb, d。于是我们在确定了 Ba, c与 Bb, c的大小关系之后，就可以决定是不是需要比较 Ba, d与 Bb, d的大小。 更进一步的，我们只要找出满足 Ba, h Bb, h的最小的 h，就可以免去 h 之后对第 a 列的计算。而这样的 h，我们可以用二分查找法在 O(log n)时间内找到（若 w 更特殊一些， 例如说是确定的函数，我们甚至可以在 O(1)的时间找到） 。并且对于每一行来说，都只需 要执行一次二分查找。在求出所有的 h 之后，只需用 O(n)的时间对每列的第
11、 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)这个不等式。实际上，这个式子被称作函数的凸 性判定不等式。在实际问题中，权函数通常都会满足这个不等式或这是它的逆不等式。故 这样的优化应用是比较广泛的。还有许多特殊
12、的不等式，若可以在程序中应用，都可以提 高程序的效率。三. 从低维向高维的转化： 在问题扩大规模时，有一种方式就是扩大问题的维数。这时，规划时决策变量的维数 也要增加。这样，存储的空间也要随着成指数级增加，导致无法存储下所有的状态，这就 是动态规划的维数灾难问题。如果我们还要在这种情况下使用动态规划，那么就要使用极 其复杂的数学分析方法。对于我们来说，使用这种方法显然是不现实的。这时，我们就需 要改造动态规划的模型。通常我们都可以把这时的动态规划模型变为网络流模型。 对于模型的转化方法，我们有一些一般的规律。若状态转移方程只与另一个状态有关， 我们可以肯定得到一个最小费用最大流的模型3。这个模
13、型必然有其规律的地方，甚至用 对偶算法在对网络流的求解时也还要用到动态规划的方法。不过这不是重点，我们关心的 只是动态规划问题如何转化。例如说 IOI97火星探测器一题。这一题的一维模型是可 以用动态规划来解决的（这里的维数概念是指探测器的数目） 。在维数增加时，我们就可以 用该方法来用网络流的方法解决问题。 除此之外，还有许多问题可以用该方法解决。例如最长区间覆盖问题，在维数增加时 也同样可以用该方法解决。更进一步来说，甚至图论的最短路问题也可以做同样的转化来 求出特殊的最短路。不过一般来说转化后流量最大为 1，有许多特殊的性质也没有得到应 用，并且些复杂的动态规划问题还无法转化为网络流问题
14、（例如说最优二叉树问题） ，故标 准的网络流算法显然有些浪费，它的解决还需要进一步的研究。 参考文献：参考文献： EGG88 David Eppstein, Zvi Galil and Raffaele Giancarlo, Speeding up Dynamic Programming GP90 Zvi Galil and Kunsoo Park, Dynamic Programming with Convexity, Concavity, and Sparsity附录附录 1 Ci, j的凸性是指对于任意的 a b c d，都有 Ca, c+ Cb, d Ca, d+ Cb, c。 它的证
15、明如下： 我们设 k=Kb,c，则有 Ca, c+ Cb, d Ca, k-1+ Ck, c+ Cb, k-1+ Ck, d+ w(a, c) + w(b, d)= Ca, k-1+ Ck, d+ w(a, d)+ Cb, k-1+ Ck, c+ w(b, c)= Ca, d+ Cb, c。 得证。 2 有关这个问题的伪代码如下： beginE1D1;Queue.Add(K:1, H:n);for j2 to n dobeginif B(j-1, j) B(Queue.Khead, j) thenbeginEjB(j-1, j);Queue.Empty;Queue.Add(K:j-1, H:n+1);end elsebeginEjB(Queue.Khead, j);while B(j-1, Queue.Htail-1) B(Queue.Ktail, Queue.Htail-1) do Queue.Delete(tail);Queue.Htailh(Queue.Ktail, j-1);if h_OK then Queue.Add(K:j-1, H:n+1);end;if Queue.Hhead=j+1 then Queue.SkipHead;en
