题目
下面哪些是贪心算法的特点()A. 每一步都需要考虑全局最优解B. 每一步都采取局部最优解C. 无后效性D. 贪心算法必需使用递归实现
下面哪些是贪心算法的特点()
A. 每一步都需要考虑全局最优解
B. 每一步都采取局部最优解
C. 无后效性
D. 贪心算法必需使用递归实现
题目解答
答案
BC
B. 每一步都采取局部最优解
C. 无后效性
B. 每一步都采取局部最优解
C. 无后效性
解析
贪心算法的特点主要体现在两个核心点上:
- 局部最优选择:每一步都选择当前状态下的最优解,不考虑全局情况。
- 无后效性:已做出的选择不会因后续步骤而改变,即当前选择对未来决策没有负面影响。
选项中需排除全局最优直接考虑和递归实现强制要求,因为贪心算法的本质是通过局部决策逐步逼近全局最优,且实现方式灵活(不限于递归)。
选项分析
A. 每一步都需要考虑全局最优解
错误。贪心算法的核心是局部最优选择,而非直接考虑全局。全局最优是通过一系列局部最优解间接达到的。
B. 每一步都采取局部最优解
正确。贪心算法的定义明确要求每一步都选择当前条件下的最优解,例如找零钱问题中优先使用最大面值的硬币。
C. 无后效性
正确。贪心算法的正确性依赖于“无后效性”,即已选择的局部最优解不会因后续步骤而改变。例如,活动选择问题中已选的最早结束活动不会因后续选择而调整。
D. 贪心算法必需使用递归实现
错误。贪心算法通常通过迭代或贪心策略排序实现(如贪心排序后贪心选择),递归并非必要条件。