电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

算法7_动态规划法

89页
  • 卖家[上传人]:壹****1
  • 文档编号:26282461
  • 上传时间:2017-12-24
  • 文档格式:PPT
  • 文档大小:1.68MB
  • / 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

      5、到t的最短路径。(反证)假如(v2,v3,.,vk-1,t)不是从v2到t的最短路径,另有(v2,q3,.,qk-1,t)是从v2到t的最短路径,那么路径(s,v2,q3,.,qk-1,t)显然比(s,v2,v3,.,vk-1,t)更短。与假设矛盾!多段图的最优子结构性质得证!,在分析(证明)问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。,多段图问题的递推式(向前递推),由多段图问题的最优子结构性质,容易得到多段图问题的递推式,从而由子问题的最优解来计算原问题的最优解:多段图问题的向前递推式:(式7-1)cost(i,j)是从第i阶段中的结点j,到汇点t的最短路径长度。cost(i+1,p)是从后继结点(第i+1阶段中的结点)p到汇点t的最短路径长度。(子问题的最优解)c(j,p)+cost(i+1,p)是从第i阶段结点j,经过第i+1阶段结点p到达汇点t的路径长度。cost(i,j)则是这些路径中的最短路径长度。,E表示j,p之间有边,使用式(7-1)向前递推式,

      6、由后向前计算最优解值cost(1,0)cost(5,11)=0,cost(4,10)=5, cost(4,9)=2, cost(4,8)=4,cost(3,7)=min6+cost(4,10),5+cost(4,9)=7, cost(3,6)=.=5, cost(3,5)=.=7,cost(2,4)=min8+cost(3,7),11+cost(3,6)=15, cost(2,3)=18, cost(2,2)=.=9, cost(2,1)=.=7, cost(1,0)=min9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)=16,若想求最优解,必须在计算最优解值的过程中保存一些必要信息。可用d(i,j)来记录从第i阶段结点j到汇点t的最短路径上该结点的下一个结点编号。,根据前面例7-1求最优解值cost(1,0)的过程中,产生的中间结果:cost(5,11)=0,cost(4,10)=5, cost(4,9)=2, cost(4,8)=4,cost(3,7)=min6+cost(4,10),5+cost(4,9)=7, cost(3,6)=

      7、.=5, cost(3,5)=.=7,cost(2,4)=min8+cost(3,7),11+cost(3,6)=15, cost(2,3)=18, cost(2,2)=.=9, cost(2,1)=.=7,cost(1,0)=min9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)=16,可知:d(4,10)=d(4,9)=d(4,8)=11,d(3,7)=d(3,6)=d(3,5)=9,d(2,4)=d(2,3)=7,d(2,2)=5,d(2,1)=6,d(1,0)=1或2,很容易从d的值确定最短路径上的结点,得到两条最短路径:,(0, d(1,0)=1, d(2,1)=6, d(3,6)=9, d(4,9)=11) 和(0, d(1,0)=2, d(2,2)=5, d(3,5)=9, d(4,9)=11),多段图显然具有重叠子问题性质:计算cost(3,7)、cost(3,6)、cost(3,5)时都要用到cost(4,9)的值,因此保存cost(4,9)的值可以避免重复计算。,程序7-1:多段图的向前递推动态规划算法FMultiGra

      8、ph(int k,int*p) /共k个阶段,n个结点 /带权有向图G (多段图)采用邻接表存储(见程序6-8) float *cost=new floatn; /一维数组costj保存结点j到汇点t的最短路径 int *d=new intn; /一维数组dj保存costj 对应的最短路径上的下一个结点 costn-1=0;dn-1=-1; /设置向前递推的初值(最大结点编号为n-1) for (int j=n-2;j=0;j-) /按结点编号n-2,.,0的顺序计算cost j和dj float min=INFTY; / min求得的最小值,即为当前结点j的costjfor (ENode *r=aj;r;r=r-nextArc) /用指针r遍历邻接表中aj的邻接结点int v=r-adjVex; / 当前阶段的结点j与下一阶段的结点v之间有边if (r-w+costvw+costv; q=v; costj=min; dj=q; /q是最短子路径上j的下一个结点编号 c=cost0; p0=0;/c保存的是最优解值, p0 是源点0 for (j=1;j=0;j-) /按结点编号n-2,.,0的顺序计算cost j和dj float min=INFTY; / min求得的最小值,即为当前结点j的costjfor (ENode *r=aj;r;r=r-nextArc) /用指针r遍历邻接表中aj的邻接结点int v=r-adjVex; / 当前阶段的结点j与下一阶段的结点v之间有边if (r-w+costvw+costv; q=v; costj=min; dj=q; /q是最短子路径上j的下一个结点编号 c=cost0; p0=0;/c保存的是最优解值, p0 是源点0 for (j=1;j=k-1;j+) pj=dpj-1;/数组p保存最优解,pi是最短路径上第i阶段结点,

      《算法7_动态规划法》由会员壹****1分享,可在线阅读,更多相关《算法7_动态规划法》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
     
    收藏店铺
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.