第3章 动态规划.ppt

第3章动态规划动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划基本步骤完全加括号的矩阵连乘积矩阵连乘问题矩阵连乘问题矩阵连乘问题分析最优解的结构建立递归关系计算最优值用动态规划法求最优解动态规划算法的基本要素二、重叠子问题三、备忘录方法最长公共子序列最长公共子序列的结构子问题的递归结构计算最优值算法的改进凸多边形最优三角剖分三角剖分的结构及其相关问题最优子结构性质最优三角剖分的递归结构多边形游戏最优子结构性质图像压缩图像压缩电路布线记。N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。
(1)当i=1时，

(2)当i>1时，
2.1j<π(i)。此时，。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。
2.2j≥π(i)，(i,π(i))∈MNS(i,j)。则对任意(t,π(t))∈MNS(i,j)有t<i且π(t)<π(i)。在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。
2.3若，则对任意(t,π(t))∈MNS(i,j)有
t<i。从而。因此，Size(i,j)≤Size(i-1,j)。
另一方面，故又有Size(i,j)≥Size(i-1,j)，
从而Size(i,j)=Size(i-1,j)。流水作业调度流水作业调度Johnson不等式流水作业调度的Johnson法则算法描述0-1背包问题0-1背包问题算法改进典型例子（一）算法改进典型例子（二）算法复杂度分析最优二叉搜索树二叉查找树的期望耗费二叉查找树的期望耗费示例最优二叉搜索树