算法导论复习重点：分治、动态规划与搜索策略

"这是一份关于《算法导论》期末复习的习题集，主要涵盖了算法、期末复习和黑皮书第三版中的习题。题目涉及了多种算法思想和方法，包括分治策略、动态规划、贪心法、回溯法等。" 1. 分治策略：二分搜索算法是分治策略的典型应用，它将大问题分解成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 2. 动态规划：动态规划算法通常包括四个步骤：找出最优解的性质、定义最优解、构造最优解和算出最优解。题目中提到的不是基本步骤的是“找出最优解的性质”，这是动态规划的首要步骤。 3. 贪心法：最大效益优先是分支界限法中常用的一种搜索方式，贪心法通常用于每一步选择局部最优解，期望得到全局最优解。 4. 回溯法：回溯法在解决旅行售货员问题等组合优化问题时，形成的解空间树是排列树，它通过穷举所有可能的解来寻找最优解。 5. 时间复杂度：衡量一个算法好坏的标准通常不只关注运行速度或占用空间，而是时间复杂度，即算法执行时间与问题规模之间的关系。 6. 分治法与动态规划：0/1背包问题不适合用分治法解决，因为它涉及到决策的不可分割性和子问题的重叠性，更适合用动态规划来处理。 7. 循环赛日程表：实现循环赛日程表常采用分治策略，通过对比赛进行合理划分，减少冲突。 8. 拉斯维加斯算法：这种随机算法在运行时可能成功也可能失败，它在解决问题时会根据概率来决定是否找到正确答案。 9. 分支界限法：广度优先、最小耗费优先和最大效益优先是分支界限法的搜索方式，而深度优先不是。 10. 备忘录法与动态规划：备忘录法是动态规划的一个变形，用于避免重复计算子问题的解。 11. 哈弗曼编码：贪心算法用于构建哈弗曼树，计算时间复杂度为O(nlogn)。 12. 回溯法：通常以深度优先方式系统搜索问题解的是回溯法，如解决旅行售货员问题等。 13. 最长公共子序列：利用动态规划法可以求解，通过构造二维表格记录子序列信息。 14. 棋盘覆盖：棋盘覆盖问题可以用分治法解决，将大问题分解为小问题进行处理。 15. 贪心算法：贪心选择性质是贪心算法的基本要素，它指在每一步选择中都采取在当前状态下最好或最优的选择。 16. 回溯法的效率：回溯法的效率与满足显约束的值的个数、计算约束函数、剪枝函数的设计等因素有关，而不直接依赖于问题的定义最优解。