BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 9 题

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

这题考算法思想里的回溯法定义。拿到‘选优搜索’‘退回重选’这些关键词，立马就能锁定答案。

容易把回溯法和枚举法、贪心法搞混。枚举是穷举所有可能，不会回头；贪心是一次性选局部最优，也不回头。只有回溯法才会在发现路径不通时‘退一步’，重新选别的分支。

这道题考查的是算法设计中的回溯法概念，属于基础算法思想范畴。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。它本质上是在一棵解空间树上进行深度优先搜索（DFS），在搜索过程中，每走一步都要判断是否满足约束条件，若满足则继续深入，若不满足或达到目标则回溯到上一步，尝试其他分支。

命题人喜欢在这类概念题里挖坑：一是混淆回溯与枚举，枚举是穷举所有解，不会‘回头’；二是混淆回溯与贪心，贪心每一步都选局部最优，也不回头；三是把分层遍历、剪枝等概念混进来。本题题干中‘选优搜索’‘退回一步重新选择’就是回溯法最典型的描述。

思考心法：看到‘搜索’‘退回’‘重新选择’，先想是不是在解空间树上做DFS，再想有没有剪枝或约束判断。这类题不需要计算，关键是记住定义。

避坑：不要误选B枚举法，枚举法不‘退回’；不要误选C动态规划，DP是递推求最优解，不是搜索；不要误选D贪心，贪心不回头。正确答案是A回溯法。

考频与趋势：回溯法在BCSP-X近五年考频为3次，NOIP考频为5次，CSP-J/S考频为2次，GESP考频为4次，合计14次。回溯法是信息学竞赛高频考点，常与树形DP、排列组合、棋盘问题结合，也常作为大题的搜索框架。未来仍可能以概念辨析或结合具体问题的搜索框架形式出现。