动态规划算法的基本要素最优子结构.ppt

  1. 1、本文档共48页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第章动态规划算法总体思想动态规划基本步骤找出最优解的性质并刻划其结构特征递归地定义最优值以自底向上的方式计算出最优值根据计算最优值时得到的信息构造最优解完全加括号的矩阵连乘积矩阵连乘问题分析最优解的结构建立递归关系计算最优值用动态规划法求最优解动态规划算法的基本要素一最优子结构二重叠子问题三备忘录方法最长公共子序列若给定序列则另一序列是的子序列是指存在一个严格递增下标序列使得对于所有有例如序列是序列的子序列相应的递增下标序列为给定个序列和当另一序列既是的子序列又是的子序列时称是序列和的公共子序列

第3章 动态规划 算法总体思想 动态规划基本步骤 找出最优解的性质,并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息,构造最优解。 完全加括号的矩阵连乘积 矩阵连乘问题 分析最优解的结构 建立递归关系 计算最优值 用动态规划法求最优解 动态规划算法的基本要素 一、最优子结构 二、重叠子问题 三、备忘录方法 最长公共子序列 若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。 给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。 最长公共子序列的结构 子问题的递归结构 计算最优值 算法的改进 凸多边形最优三角剖分 三角剖分的结构及其相关问题 最优子结构性质 最优三角剖分的递归结构 多边形游戏 最优子结构性质 图像压缩 电路布线 流水作业调度 Johnson不等式 流水作业调度的Johnson法则 算法描述 0-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)。 电路布线 (1)当i=1时 (2)当i1时 n个作业{1,2,…,n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。 分析: 直观上,一个最优调度应使机器M1没有空闲时间,且机器M2的空闲时间最少。在一般情况下,机器M2上会有机器空闲和作业积压2种情况。 设全部作业的集合为N={1,2,…,n}。S?N是N的作业子集。在一般情况下,机器M1开始加工S中作业时,机器M2还在加工其他作业,要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 流水作业调度 设?是所给n个流水作业的一个最优调度,它所需的加工时间为 a?(1)+T’。其中T’是在机器M2的等待时间为b?(1)时,安排作业?(2),…,?(n)所需的时间。 记S=N-{?(1)},则有T’=T(S,b?(1))。 证明:事实上,由T的定义知T’?T(S,b?(1))。若T’T(S,b?(1)),设?’是作业集S在机器M2的等待时间为b?(1)情况下的一个最优调度。则?(1), ?’(2),…, ?’(n)是N的一个调度,且该调度所需的时间为a?(1)+T(S,b?(1))a?(1)+T’。这与?是N的最优调度矛盾。故T’?T(S,b?(1))。从而T’=T(S,b?(1))。这就证明了流水作业调度问题具有最优子结构的性质。 由流水作业调度问题的最优子结构性质可知, 对递归式的深入分析表明,算法可进一步得到简化。 设?是作业集S在机器M2的等待时间为t时的任一最优调度。若

文档评论(0)

wangsux + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档