第3章 节 动态规划 计算机算法设计与分析.pptVIP

第3章 动态规划;动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题;算法总体思想;但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。;如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;分析最优解的结构;建立递归关系;计算最优值;用动态规划法求最优解;动态规划算法的基本要素;二、重叠子问题;三、备忘录方法;最长公共子序列;最长公共子序列的结构;子问题的递归结构;计算最优值;算法的改进;凸多边形最优三角剖分;三角剖分的结构及其相关问题;最优子结构性质;最优三角剖分的递归结构;计算最优值;多边形游戏;最优子结构性质;由于断开位置s有1?s ?j-1的j-1种情况，所以有;图像压缩;图像压缩;电路布线;记 。N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。 (1)当i=1时， (2)当i1时， 2.1 jπ(i)。此时， 。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。 2.2 j≥π(i)，(i,π(i))∈MNS(i,j) 。 则对任意(t,π(t)) ∈MNS(i,j)有ti且π(t)π(i)。在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。 2.3 若 ，则对任意(t,π(t)) ∈MNS(i,j)有 ti。从而 。因此，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背包问题;算法改进;算法改进;典型例子（一）;典型例子（二）;算法复杂度分析;最优二叉有哪些信誉好的足球投注网站树;二叉查找树的期望耗费;二叉查找树的期望耗费示例;最优二叉有哪些信誉好的足球投注网站树