【算法分析与设计】动态规划（下）（三）

8.1 算法改进

  由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。

  对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+1]={(0，0)}。

8.2 一个例子

  n=3，c=6，w={4，3，2}，v={5，2，1}。

8.3 算法改进

  函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集p[i+1]与函数m(i+1，j-wi)+vi的跳跃点集q[i+1]的并集中。易知，(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]。因此，容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]}

  另一方面，设(a，b)和(c，d)是p[i+1]q[i+1]中的2个跳跃点，则当ca且d<b时，(c，d)受控于(a，b)，从而(c，d)不是p[i]中的跳跃点。除受控跳跃点外，p[i+1]q[i+1]中的其它跳跃点均为p[i]中的跳跃点。

  由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]。

8.4 一个例子

  n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。

  初始时p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6](w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5](w4,v4)={(5,4),(9,10)}。

  从跳跃点集p[5]与q[5]的并集p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}。

  q[4]=p[4](6，5)={(6，5)，(10，11)}

  p[3]={(0，0)，(4，6)，(9，10)，(10，11)}

  q[3]=p[3](2，3)={(2，3)，(6，9)}

  p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}

  q[2]=p[2](2，6)={(2，6)，(4，9)，(6，12)，(8，15)}

  p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}

  p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。

8.5 算法复杂度分析

  上述算法的主要计算量在于计算跳跃点集pi。由于q[i+1]=p[i+1](wi，vi)，故计算q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间。从跳跃点集p[i]的定义可以看出，p[i]中的跳跃点相应于xi,…,xn的0/1赋值。

  因此，p[i]中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集p[i]所花费的计算时间为

  从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2n})。

九、最优二叉搜索树

9.1 二叉搜索树

  （1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

  （2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

  （3）它的左、右子树也分别为二叉排序树在随机的情况下，二叉查找树的平均查找长度和logn是等数量级的。

9.2 二叉搜索树的期望耗费

  搜索成功与不成功的概率：

  二叉搜索树的期望耗费：

  有 个节点的二叉树的个数为：穷举搜索法的时间复杂度为指数级：

9.3 二叉搜索树的期望耗费示例

9.4 最优二叉搜索树

  最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由 最优二叉搜索树问题的最优子结构性质 可建立计算pij的递归式如下

  记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为

  注意到，

  可以得到O(n2)的算法。

十、小结

  动态规划算法和分治法的相同点是什么？

  动态规划算法和分治法的不同之处在哪里？

  用“表”记录所有已有子问题的答案！避免重复计算，从而得到多项式时间复杂度。

  动态规划通常用来计算“最优”解，不适合计算“合并”解。