广工算法期末复习：动态规划与贪心策略详解

在《算法分析与设计》这门课程的期末复习题中，涉及了多种核心算法和分析方法的知识点。首先，我们来看选择题部分： 1. 流水作业调度中的Johnson法则通常与动态规划算法相结合，因为动态规划能够解决这类具有最优子结构且存在重叠子问题的问题，故正确答案是D。 2. Hanoi塔问题是一个典型的递归问题，通过设计递归算法，按照规则将圆盘从一个柱子移动到另一个柱子，正确的方法是选择B，递归地解决小规模子问题。 3. 动态规划算法的基本要素包括两个：最优子结构性质和重叠子问题性质，因此C选项是正确的。 4. 在算法分析中，渐进上界用O表示，即最坏情况下的时间复杂度上限；记号[pic]表示渐进下界，即最好情况下的时间复杂度下限；而[pic]表示紧渐进界，是两者之间的边界，A、B和D都是正确的表述。 5. 渐进记号的性质中，正确的是A，表示对于任何正的常数c和足够大的n，有f(n)≤c*g(n)，而对于B选项，应该是f(n)≥c*g(n)。 6. 能够通过贪心算法求得最优解的问题往往具备最优子结构性质和贪心选择性质，因此A是正确的。 7. 回溯法在解空间树搜索中采用的是深度优先策略，即从根节点开始，尽可能深地探索每一个可能的分支。 8. 分支限界法同样采用广度优先策略来搜索解空间树，确保每次考虑所有当前可行的解决方案。 9. 回溯法中，程序块B是算法框架的一部分，用于实现递归过程中的回溯操作。 10. 回溯法的效率不依赖于问题的解空间形式，因为它的搜索策略决定了效率，而解空间的形式不影响搜索效率。 11. 常见的两种分支限界法是队列式（FIFO）分支限界法和优先队列式分支限界法，D选项正确。 12. k带图灵机的空间复杂性S(n)指的是处理长度为n的输入时，机器在k条带上的最大使用方格数，所以B是正确的。 这些题目涵盖了算法设计、分析、搜索策略以及理论模型等多个方面，帮助学生理解和巩固算法的基础理论。通过解答这些问题，可以检验对动态规划、贪心算法、回溯法、分支限界法等核心概念的理解程度，以及对时间复杂度和空间复杂性的掌握情况。