算法7_动态规划法
89页1、第7章 动态规划法,学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素(1)最优子结构性质(2)重叠子问题性质掌握设计动态规划算法的步骤。理解动态规划算法与分治法、贪心法的异同通过应用范例学习动态规划算法设计策略。(1)多段图问题、关键路径问题(2)每对结点间的最短路径(3)最长公共子序列(4)0/1背包,章节内容7.1 一般方法和基本要素7.2 每对结点间的最短路径7.4 最长公共子序列7.6 0/1背包,7.1 一般方法和基本要素,动态规划算法总体思想动态规划算法的基本要素设计动态规划算法的步骤动态规划法与分治法、贪心法的区别,动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,动态规划算法总体思想,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。,动态规划算法总体思想,如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。,动态规划算法总体思想,T(n),动态规划算法的基本要素,(1)子问题重叠性质(递归算法求解问题
2、时)每次产生的子问题并不总是新问题,有些子问题被反复计算多次,这种性质称为子问题重叠性质。动态规划算法对每一个子问题只解一次,而后将其解保存在一个表格(通常用二维数组)中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式级时间,从而获得较高的解题效率。,动态规划算法的基本要素,(2)最优子结构性质用动态规划法求解的前提。当一个问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。一个问题的活动过程可以分为若干个阶段,每个阶段可包含一个或多个状态,从初始阶段的初始状态出发做出每个阶段的决策,形成一个决策序列。利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。,设计动态规划算法的步骤,用动态规划算法求解问题的步骤:1、找出最优解的性质,并刻划其结构特征;2、递归地定义最优解值;3、自底向上求最优解值;4、根据计算最优解值时得到的信息构造一个最优解(此步只在要求得到最优解时才需要做) 。动态规划法是一种求解最优化问题的重要算法策略。,动态规划法的子问题
3、往往是重叠的。如果采用与分治法类似的直接递归方法求解将十分费时。为了避免重复计算,动态规划算法一般采用自底向上方式进行计算,并保存已经求解的子问题的最优解值。,利用最优子结构性质及所获得的递推关系式(较小子问题最优解与较大子问题最优解之间存在的数值关系)去求取最优解,可以使计算量较之穷举法急剧减少。,动态规划法与分治法,共同点:将待求解的问题分解成若干子问题,先求解子问题,然后再从这些子问题的解得到原问题的解。不同点:1、适合于用动态规划法求解的问题,分解得到的各子问题往往不是相互独立的;而分治法中子问题相互独立。2、动态规划法用表保存已求解过的子问题的解,再次碰到同样的子问题时不必重新求解,而只需查询答案,故可获得多项式级时间复杂度,效率较高;而分治法中对于每次出现的子问题均求解,导致同样的子问题被反复求解,故产生指数增长的时间复杂度,效率较低。,共同点:都是求解最优化问题;都具有最优子结构性质。不同点:1、求解方式不同:动态规划法:自底向上;贪心法:自顶向下。以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为一个规模更小的子问题。2、对子问题的依赖不同:动态规划法:
4、依赖于各子问题的解。只有在解出相关子问题后,才能作出选择;应使各子问题最优,才能保证整体最优;贪心法:不依赖于子问题的解。仅在当前状态下作出最好选择,即局部最优选择。,动态规划法与贪心法,多段图问题,一种特殊的有向无环图的最短路径问题。(例7-1)带权有向图G=(V,E)中的结点被划分成k个互不相交的子集Vi (1ik) 。其中:V1只包含源点s,Vk只包含汇点t ;图中的边均满足:若uVi则vVi+1 。求从s到t的一条长度最短的路径(P137 图7-1)。由每个阶段所作出的决策组成的决策序列,产生一条从s到t的路径多段图问题的一个可行解。目标函数(每条路径上所有边的权值之和,即路径长度)最小的一条路径为最优解,该路径长度为最优解值。,多段图的最优子结构证明,假设(s,v2,v3,.,vk-1,t)是一条从s到t的最短路径,并假定由源点s经过初始决策已经到达状态v2 。则将v2看成某个子问题的初始状态,该子问题寻找一条从v2到t的最短路径。证明(多段图具有最优子结构性质)如果(s,v2,v3,.,vk-1,t)是一条从s到t的最短路径,则(v2,v3,.,vk-1,t)必是一条从v2
《算法7_动态规划法》由会员壹****1分享,可在线阅读,更多相关《算法7_动态规划法》请在金锄头文库上搜索。
高中数学复习 专练 1.1 集合的概念及其运算
硅橡胶机械项目建议书写作模板立项-稿子代写定制
八年级语文上册13中国石拱桥课堂导学北京课改版
甘肃省靖远县靖安中学九年级地理上学期第一次月考试题无答案
生化复习资料完整版
幼儿园表扬信(15篇)【新编】
钢筋位置测定仪校准方法
光的折射定律完美版稻谷书屋
模板工程试题
关于全日制硕士专业学位研究生“企业实习报告”
ERP管理系统培训课件
县长在小麦春管暨化控会致辞
食品快检工作计划
C语言程序设计生日快乐歌
浅谈人际沟通障碍的影响因素及对策
绘本活动《山丘上的约会》
2021学年高中数学第二章空间向量与立体几何2.2空间向量的运算课后演练提升北师大版选修2-1
毕业论文水电热力分公司经营管理的调查报告及建议
文艺演出主持词汇编六篇
英语学习旅行到宇宙边缘视频的中英文对照解说词
2021-12-31 51页
2021-12-30 11页
2021-12-30 12页
2021-12-30 12页
2021-12-30 14页
2021-12-30 12页
2021-12-30 29页
2021-12-30 11页
2021-12-30 16页
2021-12-19 32页