算法分析与设计线下作业二样本_第1页
算法分析与设计线下作业二样本_第2页
算法分析与设计线下作业二样本_第3页
算法分析与设计线下作业二样本_第4页
算法分析与设计线下作业二样本_第5页
已阅读5页，还剩2页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。《算法分析与设计》学习中心:专业:学号:姓名:作业练习二一、名词解释1、MST性质2、子问题的重叠性质递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被重复计算多次,这种性质称为子问题的重叠性质。二、简答题1、简述动态规划算法求解的基本要素。答:动态规划算法求解的基本要素包括:1)最优子结构是问题能用动态规划算法求解的前提;2)动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果,即重叠子问题。2、备忘录方法和动态规划算法相比有何异同?简述之。答:备忘录方法是动态规划算法的变形。与动态规划算法一样,备忘录方法用表格保存已解决的子问题的答案,在下次需要解此问题时,只要简单地查看该子问题的解答,而不必重新计算。备忘录方法与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上递归的。因此,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同的子问题的重复求解,而直接递归方法没有此功能。3、贪心算法求解的问题主要具有哪些性质?简述之。答:贪心算法求解的问题一般具有二个重要的性质:一是贪心选择性质,这是贪心算法可行的第一个基本要素;另一个是最优子结构性质,问题的最优子结构性质是该问题可用贪心算法求解的关键特征。三、算法编写及算法应用分析题1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。最大子段和问题:给定由n个整数(可能为负整数)组成的序列a1a2…an,求该序列形如Σi≤k≤jak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求的最优值为max{0,max1≤i≤j≤nΣi≤k≤jak}2、关于多段图问题。设G＝(V,E)是一个赋权有向图,其顶点集V被划分成k>2个不相交的子集Vi:,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),图中所有的边(u,v),,。求由s到t的最小成本路径。①给出使用动态规划算法求解多段图问题的基本思想。使用上述方法求解如下多段图问题。3、最优二元归并问题:已知将两个分别包含a个和b个记录的已分类文件归并在一起得到一个分类文件需作a+b次记录移动。现有n个已分类文件F1,F1,⋯,Fn,它们的记录个数分别为l1,l2,⋯,ln。现在考虑使用二元归并模式将这n个文件归并成一个分类文件,要求记录移动次数最少。设计一个贪心算法来求解一种最优的二元归并(即记录移动次数最少的二元归并)。4、带限期的作业调度问题:n个作业需要在一台机器上处理,每个作业可在单位时间内完成。每个作业i都有一个截止期限di>0(di为整数),当且仅当作业i在它的截止期限之前被完成,获得pi>0的效益。一种可行的调度方案为n个作业的一个子集J,其中J

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论