欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    算法合集之动态规划算法时间效率的优化精.ppt

    • 资源ID:51217823       资源大小:896KB        全文页数:13页
    • 资源格式: PPT        下载积分:18金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要18金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    算法合集之动态规划算法时间效率的优化精.ppt

    算法合集之动态规划算法时间效率的优化第1页,本讲稿共13页动态规划算法的时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间第2页,本讲稿共13页一、减少状态总数二、减少每个状态转移的状态数三、减少状态转移的时间1、改进状态表示;(例一)1、减少决策时间(例三)方法:采用恰当的数据结构;2、减少计算递推式的时间方法:进行预处理,利用计算结果等;2、其他方法:选取恰当的规划方向等;1、根据最优解的性质减少决策量;(例二)2、其他方法:利用四边形不等式证明决策的单调性等;第3页,本讲稿共13页例一、RaucousRockers演唱组(USACO96)问题描述现有n首由RaucousRockers演唱组录制的歌曲,计划从中选择一些歌曲来发行m张唱片,每张唱片至多包含t分钟的音乐,唱片中的歌曲不能重叠。按下面的标准进行选择:(1)这组唱片中的歌曲必须按照它们创作的顺序排序;(2)包含歌曲的总数尽可能多。输入n,m,t,和n首歌曲的长度,它们按照创作顺序排序,没有一首歌超出一张唱片的长度,而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。第4页,本讲稿共13页设n首歌曲按照创作顺序排序后的长度为long1.n,则动态规划的状态表示描述为:gi,j,k,(0in,0jm,0kt),表示前i首歌曲,用j张唱片另加k分钟来录制,最多可以录制的歌曲数目。状态转移方程为:当klongi,i1时:gi,j,k=maxgi-1,j,k-longi+1,gi-1,j,k当klongi,i1时:gi,j,k=maxgi-1,j-1,t-longi+1,gi-1,j,k规划的边界条件为:当0jm,0kt时:g0,j,k=0;问题的最优解为:gn,m,0。算法的时间复杂度为:O(n*m*t)。第5页,本讲稿共13页改进的状态表示描述为:gi,j=(a,b),0in,0ji,0am,0bt,表示在前i首歌曲中选取j首录制所需的最少唱片为:a张唱片另加b分钟。状态转移方程为:gi,j=mingi-1,j,gi-1,j-1+longi其中(a,b)+longi=(a,b)的计算方法为:当b+longit时:a=a;b=b+longi;当b+longit时:a=a+1;b=longi;规划的边界条件:当0in时,gi,0=(0,0)题目所求的最大值是:answer=maxk|gn,k(m-1,t)算法的时间复杂度为:O(n2)。Back第6页,本讲稿共13页例三、石子合并问题(NOI95)问题描述在一个操场上摆放着一圈n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆的石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。本例只考虑最大得分。第7页,本讲稿共13页ij规划的边界条件为:mi,i=0令si,j=k,表示合并的最优断开位置。算法的时间复杂度为O(n3)。设各堆的石子数依次为d1.n,则动态规划的状态表示为:mi,j,1i,jn,表示合并di.j所得到的最大得分:令 ,则状态转移方程为:第8页,本讲稿共13页合并第i堆到第j堆石子的最优断开位置si,j要么等于i,要么等于j-1,也就是说最优合并方案只可能是:(i)(i+1 j)或 (i j-1)(j)证明:设合并第i堆到第j堆石子的最优断开位置si,j=p,且ipj-1。情况1、ti,ptp+1,j由于ip,所以可以设q=si,p。于是最优合并方案为:(iq)(q+1.p)(p+1j)它的得分F1=mi,q+mq+1,p+mp+1,j+ti,j+ti,pti,p我们可以构造如下的合并方案:(iq)(q+1.p)(p+1j)它的得分F2=mi,q+mq+1,p+mp+1,j+ti,j+tq+1,jtq+1,j由于qp,所以ti,ptp+1,jtq+1,j所以F1tp+1,j与情况1是对称的。第9页,本讲稿共13页状态转移方程优化为:mi,j=maxmi+1,j,mi,j-1+ti,jij规划的边界条件是:mi,i=0算法的时间复杂度O(n2)。Back第10页,本讲稿共13页例三、LOSTCITY(NOI2000)问题描述现给出一张单词表、特定的语法规则和一篇文章:文章和单词表中只含26个小写英文字母az。单词表中的单词只有名词,动词和辅词这三种词性,且相同词性的单词互不相同。单词的个数不超过1000,单词的长度均不超过20。语法规则可简述为:名词短语:任意个辅词前缀接上一个名词;动词短语:任意个辅词前缀接上一个动词;句子:以名词短语开头,名词短语与动词短语相间连接而成。文章的长度不超过5k。且已知文章是由有限个句子组成的,句子只包含有限个单词。编程将这篇文章划分成最少的句子,在此前提之下,要求划分出的单词数最少。第11页,本讲稿共13页我们分别用v,u,a表示动词,名词和辅词,给出的文章用L1.M表示,则状态表示描述为:F(v,i):表示将L的前i个字符划分为以动词结尾(当iM时,可带任意个辅词后缀)的最优分解方案下划分的句子数与单词数;F(u,i):表示将L的前i个字符划分为以名词结尾(当iM时,可带任意个辅词后缀)的最优分解方案下划分的句子数与单词数。状态转移方程为:F(v,i)=minF(u,j)+(0,1),L(j+1.i)为动词;F(v,j)+(0,1),L(j+1.i)为辅词,iM;F(u,i)=minF(u,j)+(1,1),L(j+1.i)为名词;F(v,j)+(0,1),L(j+1.i)为名词;F(u,j)+(0,1),L(j+1.i)为辅词,iM;边界条件:F(v,0)=(1,0);F(u,0)=(,);问题的解为:minF(v,M),F(u,M);第12页,本讲稿共13页顺序查找二分查找哈希表检索树算法的时间复杂度O(20*M*N)O(20*M*log2N)O(20*M)O(M)最坏情况下的比较次数1081061055*103Input.009超时1.27s0.32s0.05sInput.010超时1.33s0.33s0.05sBack采用不同的方法查找字符串的比较:设单词表的规模为N(N的最大值为1000)设文章的长度为M(M的最大值为5000)(测试环境:Pentium200/32MB)第13页,本讲稿共13页

    注意事项

    本文(算法合集之动态规划算法时间效率的优化精.ppt)为本站会员(石***)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开