算法_动态规划法ppt课件.ppt

《算法_动态规划法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章动态规划法学习要点：理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。理解动态规划算法与分治法、贪心法的异同通过应用范例学习动态规划算法设计策略。（1）多段图问题、关键路径问题（2）每对结点间的最短路径（3）最长公共子序列（4）0/1背包（5）流水作业调度问题章节内容7.1一般方法和基本要素7.2每对结点间的最短路径7.4最长公共子序列7.60/1背包7.7流水作业调度7.1一般方法和基本要素动态规划算法总体思想动态规划算法的

2、基本要素设计动态规划算法的步骤动态规划法与分治法、贪心法的区别动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题动态规划算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。动态规划算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/

3、4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)动态规划算法的基本要素（1）子问题重叠性质（递归算法求解问题时）每次产生的子问题并不总是新问题，有些子问题被反复计算多次，

4、这种性质称为子问题重叠性质。动态规划算法对每一个子问题只解一次，而后将其解保存在一个表格（通常用二维数组）中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式级时间，从而获得较高的解题效率。动态规划算法的基本要素（2）最优子结构性质——用动态规划法求解的前提。当一个问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。一个问题的活动过程可以分为若干个阶段，每个阶段可包含一个或多个状态，从初始阶段的初始状

5、态出发做出每个阶段的决策，形成一个决策序列。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。设计动态规划算法的步骤用动态规划算法求解问题的步骤：1、找出最优解的性质，并刻划其结构特征；2、递归地定义最优解值；3、自底向上求最优解值；4、根据计算最优解值时得到的信息构造一个最优解（此步只在要求得到最优解时才需要做）。动态规划法是一种求解最优化问题的重要算法策略。动态规划法的子问题往往是重叠的。如果采用与分治法类似的直接递归方法求解将十分费时。为了避免重复计算

6、，动态规划算法一般采用自底向上方式进行计算，并保存已经求解的子问题的最优解值。利用最优子结构性质及所获得的递推关系式（较小子问题最优解与较大子问题最优解之间存在的数值关系）去求取最优解，可以使计算量较之穷举法急剧减少。动态规划法与分治法共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。不同点：1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必

7、重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。共同点：都是求解最优化问题；都具有最优子结构性质。不同点：1、求解方式不同：动态规划法：自底向上；贪心法：自顶向下。以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。2、对子问题的依赖不同：动态规划法：依赖于各子问题的解。只有在解出相关子问题后,才能作出选择；应使各子问题最优，才能保证整体最优；贪

8、心法：不依赖于子问题的解。仅在当前状态下作出最好选择，即局部最优选择。动态规划法与贪心法多段图问题一种特殊的有向无环图的最短路径问题。（例7-1）带权有向图G=(V,E)中的结点被划分成k个互不相交的子集Vi(1≤i≤k)。其中：V1只包含源点s，Vk只包含汇点t；图中的边均满足：若uVi则vVi+1。求从s到t的一条长度最短的路径（P124图7-1）。由每个阶段所作出的决策组成的决策序列，产生一条从s到t的路径——多段图问题的一个可行解。目标函数（每条