算法合集之《基本动态规划问题的扩展》.doc

基本动态规划问题的扩展
应用动态规划可以有效的解决许多问题，其中有许多问题的数学模型，尤其对一些自从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)的值。下面分两个方面讨论这个问题：
Pred_Set(XT)为连续集：
在这样的情况下，我们可以用g(XT)=opt{g(Pred(XT)),f(Pred(XT))}这样一个方程式来求出g(XT)的值，并再用g(XT)的值求出f(XT)的值。这样，虽然我们相当于对g(XT)和f(XT)分别作了一次动态规划，但由于两个规划是同时进行的，时间复杂度却降为了O(nt)。由于我们在实际使用中的前趋即通常都是连续的，故这个方法有很多应用。例如IOI’99的《小花店》一题就可以用该方法把表面上的时间复杂度O(FV2)降为O(FV)。
Pred_Set(XT)为与XT有关的集合：
这样的问题比较复杂，我们以最长不下降子序列问题为例。规划方程为：f(i)=max{f(j)}+1,d[i]≥d[j];i>j。通常认为，这个问题的最低可行时间复杂度为O(n2)。不过，这个问题只多了一个d[i]≥d[j]的限制，是不是也可以优化呢？我们注意到max{f(j)}的部分，它的时间复杂度为O(n)。但对于这样的式子，我们通常都可以用一个优先队列来使这个max运算的时间复杂度降至O(logn)。对于该问题，我们也可以用这样的方法。在计算d[i]时，我们要先有一个平衡排序二叉树（例如红黑树）对d[1]~d[i-1]进行排序。并且我们在树的每一个节点新增一个MAX域记录它的左子树中的函数f的最大值。这样，我们在计算f(i)时，只需用O(logn)时间找出不比d[i]大的最大数所对应的节点，并用O(1)的时间访问它的MAX域就可以得出f(i)的值。并且，插入操作和更新MAX域的操作也都只用O(logn)的时间（我们不需要删除操作），故总时间复杂度为O(nlogn)。实际运行时这样的程序也是十分快的，n=10000时用不到1秒就可以得出结果，而原来的程序需要30秒。
从以上的讨论可以看出，再从程序设计上对问题优化时，要尽量减少问题的约束，尽可能的化为情况1。若不可以变为情况1，那么就要仔细考虑数据上的联系，设计好的数据结构来解决问题。
方程上的优化：
对于方程上的优化，其主要的方法就是通过某些数学结论对方程进行优化，避免不必要的运算。对于某一些特殊的问题，我们可以使用数学分析的方法对写出的方程求最值，这样甚至不用状态之间的递推计算就可以解决问题。不过用该方法解决的问题数量是在有限，并且这个方法也十分复杂。不过，却的确有相当数量的比较一般的问题，在应用某些数学结论后，可以提高程序的效率。
一个比较典型的例子是最优排序二叉树问题（CTSC96）。它的规划方程如下：

我们可以从这个规划方程上简单的得到一个时间复杂度为O(n3)的算法。但是否会有更有效的算法呢？我们考虑一下w(i,j)的性质。它表示的是结点i到结点j的频率之和。很明显，若有[i,j][i’,j’]，则有w[i,j]w[i’,j’]，这样可知C[i,j]具有凸性HYPERLINK\l"Appendix_1"[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，即K