# 回溯法

> 回溯法（英语：backtracking）是暴力搜索法中的一种。对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。在经典的教科书中，八皇后问题展示了回溯法的用例。

- ID: m06025
- 分类: create
- 领域: 创新方法

## 定义

一种通过探索所有可能的候选解来寻找解决方案的算法。当发现当前候选解不可能是有效解时，就回退（Backtrack）到上一步，尝试其他路径。脚手架作用： 试错与撤销。在探索未知领域（如科研、创新）时，走死胡同是必然的。关键在于要有“回退机制”——意识到错了能退回来，而不是一条道走到黑。保留撤退的权利，是探索的前提。

## 机制

回溯法是一种系统地尝试求解的方法：沿一条路径深入，遇死路则退回上一步（撤销选择）换岔路再试。它是深度优先搜索加“试错—撤销”，适合约束满足与组合问题。

## 练习

把问题建模为带约束的选择序列；每步做一选择并验证约束；违反则回溯到上一决策点换选；用剪枝提前排除无效分支；记录已搜空间避免重复。

## 脚手架用法

试错与撤销。在探索未知领域（如科研、创新）时，走死胡同是必然的。关键在于要有“回退机制”——意识到错了能退回来，而不是一条道走到黑。保留撤退的权利，是探索的前提。

[阅读网页](https://thinkingmodels.site/entries/detail/m06025)