算法分析与设计线下作业二

1、算法分析与设计学习中心： 专 业: 学 号: 姓 名:作业练习二一、名词解释1、MST性质2、子问题的重叠性质递归算法求解问题时， 每次产生的子问题并不总是新问题， 有些子问题被反复计算多次， 这 种性质称为子问题的重叠性质。二、简答题1 、简述动态规划算法求解的基本要素。答：动态规划算法求解的基本要素包括：1) 最优子结构是问题能用动态规划算法求解的前提；2) 动态规划算法， 对每一个子问题只解一次， 而后将其解保存在一个表格中， 当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。2、备忘录方法和动态规划算法相比有何异同简述之。答： 备忘录方法是动态规划算法的变形。 与

2、动态规划算法一样， 备忘录方法用表格保存已解 决的子问题的答案， 在下次需要解此问题时， 只要简单地查看该子问题的解答， 而不必重新 计算。 备忘录方法与动态规划算法不同的是， 备忘录方法的递归方式是自顶向下的， 而动态 规划算法则是自底向上递归的。 因此， 备忘录方法的控制结构与直接递归方法的控制结构相 同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看， 避免了相同的 子问题的重复求解，而直接递归方法没有此功能。3、贪心算法求解的问题主要具有哪些性质简述之。答：贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性

3、质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。最大子段和问题：给定由 n个整数（可能为负整数）组成的序列 a1a2an,求该序列形如i < kw j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为 max0, maxi w i w j w n X i w kw j ak 。k>2个不相交t （称为汇），2、关于多段图问题。设 8 （V , E）是一个赋权有向图，其顶点集 V被划分成 的子集V : 1 i k，其中，Vi和V

4、分别只有一个顶点s （称为源）和一个顶点 图中所有的边（u,v），u Vi，v Vi i。求由s到t的最小成本路径。 给出使用动态规划算法求解多段图问题的基本思想。使用上述方法求解如下多段图问题。ViV2V3V4V53、最优二元归并问题： 已知将两个分别包含 a 个和 b 个记录的已分类文件归并在一起得到一个分类文件需作 a+b次记录移动。现有n个已分类文件F1,F1,?,Fn,它们的记录个数分别 为l 1, 12, ?, In。现在考虑使用二元归并模式将这n个文件归并成一个分类文件，要求记录移动次数最少。 设计一个贪心算法来求解一种最优的二元归并 （即记录移动次数最少的二元 归并）。4、带限期的作业调度问题： n 个作业需要在一台机器上处理,每个作业可在单位时间内完 成。每个作业 i 都有一个截止期限 di >0（di 为整数 ） ，当且仅当作业 i 在它的截止期限之前 被完成，获得pi>0的效益。一种可行的调度方案为 n个作业的一个子集J，其中J中的每个 作