14.3.6 回溯法

回溯法是在解空间中按深度优先方式尝试选择；如果当前选择导致不满足约束，就撤销选择，退回上一层继续尝试其他分支。

回溯的基本过程

flowchart TD
  A["选择一个候选"] --> B{"满足约束？"}
  B -->|是| C{"形成完整解？"}
  C -->|是| D["记录解"]
  C -->|否| A
  B -->|否| E["撤销选择，回退"]
  E --> F["尝试下一个候选"]
  F --> A

关键词

关键词	对应含义
解空间树	所有可能选择形成的树
约束条件	当前选择是否合法
剪枝	提前排除不可能成功的分支
回退	撤销当前选择，返回上一层

典型问题

问题	回溯体现
八皇后	逐行放皇后，冲突则撤销
迷宫问题	尝试方向，走不通回退
子集/排列枚举	选择或不选择，逐层展开
0-1 背包穷举版	对每个物品选/不选，超重剪枝

与贪心、动态规划的区别

策略	是否尝试多分支	是否回退
贪心	通常只走一个当前最优分支	不回退
动态规划	比较多个状态，但用表保存	不按路径回退
回溯	尝试多个候选分支	失败就回退

本节例题

单选

回溯法的典型特征是：

A每次只选当前最小边B尝试选择，失败后撤销并回退C只保留最高阶项D把数组分成两半再合并

自查清单

1. 能否解释“解空间树”是什么意思？
2. 能否说明剪枝为什么能减少搜索量？
3. 能否区分回溯和贪心的决策方式？