NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 17 题

（ ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

这题考回溯法，核心是“试→不行→退→再试”。拿到题先想：是不是在搜索过程中发现路走不通了，需要退回上一步重新选？如果是，那就是回溯。

最容易把回溯和枚举搞混。回溯是边搜索边剪枝，走不通就退回；枚举是穷举所有情况，不退回。还有学生误以为动态规划也要“回头”，其实DP是记录子问题解，不回溯。贪心更不用提，它只选当前最优，绝不回头。

回溯法

这道题考查的是回溯法。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

概念解析：回溯法实际上是一种深度优先搜索（DFS）的算法策略。它的基本思想是：从一条路往前走，能进则进，不能进则退回来，退回来再换一条路。它和枚举法的区别在于，回溯法在搜索过程中会进行剪枝，即一旦发现当前路径不可能得到最优解或可行解，就立即放弃当前路径，退回上一步，尝试其他分支。而枚举法则会遍历所有可能的情况，不管有没有希望。

命题视角：命题人喜欢考回溯法，因为它能很好地体现“试错”和“回退”的思想。在算法竞赛中，回溯法是解决组合优化问题、排列组合问题、迷宫求解等问题的常用方法。命题人可能会给出一个具体的问题场景，让学生判断哪种算法最合适，或者给出一个算法的描述，让学生判断它属于哪种算法。

思考心法：拿到题先想：是不是在搜索过程中发现路走不通了，需要退回上一步重新选？如果是，那就是回溯。如果是把所有情况都试一遍，那就是枚举。如果是记录子问题解，那就是动态规划。如果是每步选最优且不回头，那就是贪心。

避坑：最容易把回溯和枚举搞混。回溯是边搜索边剪枝，走不通就退回；枚举是穷举所有情况，不退回。还有学生误以为动态规划也要“回头”，其实DP是记录子问题解，不回溯。贪心更不用提，它只选当前最优，绝不回头。

考频与趋势：回溯法是NOIP普及组初赛的高频考点，近五年考频稳定在每年1-2次，主要出现在算法基础题中。动态规划也是高频考点，但考频略低于回溯法。枚举法和贪心算法考频较低，但偶尔会出现在算法应用题中。

预测：基于近年考频数据，回溯法在普及组初赛中的考频呈现稳定上升趋势，预计未来几年仍将是高频考点。动态规划考频略有下降，但仍是重要考点。枚举法和贪心算法考频较低，但偶尔会出现在算法应用题中。