算法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_动态规划法》请在金锄头文库上搜索。
福建莆田城厢区基层公共服务岗招考聘用94人模拟试卷【附答案解析】【4】
北京市海淀区七年级语文上学期期末考试试题新人教版
财务月工作计划与财务月工作计划参考范文汇编
全面独家详解比亚迪F3DM双模电动车E
企业价值场法评价实务及案例分析考试题
第二段缓和曲线坐标计算时常需要转换坐标系
三年级语文下册期末考试卷人教版
本科毕业论文校园网设计与建设
小学班级文化建设方案及评分细则
库管员安全生产责任制度
市场营销第三季度工作计划范文(3篇)
丙烯腈合成工段丙烯过热器的设计课程设计说明书
大班美术布贴画“春天”教案反思
瓷砖的分类的选购及施工常识
关于大学英语合班授课模式之弊端的思考
有关我们教师的数学趣联
园艺治疗园设计方案
某集团公司固定资产管理制度
全国医用设备使用人员业务能力考评网上报名操作指导
复杂高层建筑结构设计要点研究
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页