[算法设计与分析-从入门到入土] 回溯法
个人导航
知乎：https://www.zhihu.com/people/byzh_rc
CSDN：https://blog.csdn.net/qq_54636039
注：本文仅对所述内容做了框架性引导，具体细节可查询其余相关资料or源码
参考文章：各方资料
文章目录
- [算法设计与分析-从入门到入土] 回溯法
- 个人导航
- 回溯法Backtracking
- 1.三色着色问题(3-coloring problem)
- 2.八皇后问题(8-queens problem)
- 通用回溯法
- 适用问题
- 解向量
- 步骤
回溯法Backtracking
本质:有组织的穷举搜索
核心目标: 避免搜索所有可能性，将搜索空间缩减到更小范围
1.三色着色问题(3-coloring problem)
给定无向图G = ( V , E ) G=(V,E)G=(V,E)，用三种颜色（如1、2、3）为 V 中每个顶点着色
要求：任意两个相邻顶点颜色不同
总可能方案数：n个顶点的图，共3 n 3^n3n种合法/非法着色方案
搜索树：所有可能着色集合可表示为“完全三叉树”
部分解：不完全着色方案中，所有已着色的相邻顶点颜色均不同
终止条件：找到一种合法解即终止
回溯规则：
- 若部分解变为“死节点”，返回上一个节点
- 若回溯至根节点，则修改根节点颜色
无需存储整个搜索树，仅需存储“根节点到当前活动节点的路径”
实际上无物理节点生成，整棵树是隐式的，只需跟踪颜色分配情况
例子:
2.八皇后问题(8-queens problem)
在8×8棋盘上放置8个皇后，使得任意两个皇后无法相互攻击
两个皇后处于同一行、同一列或同一对角线上时，可相互攻击
为简化理解，通常以“四皇后问题”为示例展开分析（核心逻辑与八皇后完全一致）
例子:
通用回溯法
适用问题
适用于“解为向量形式”的搜索问题，解的通用形式为：( x 1 , x 2 , … , x i ) (x_1, x_2, \dots, x_i)(x1,x2,…,xi)，其中 i 的取值：
- 固定i：如3着色问题、8皇后问题
- 可变i：部分问题中，不同解对应的i可能不同
解向量
元素取值：解向量中每个x i x_ixi属于有限的线性有序集合X i X_iXi
遍历规则：按字典序遍历笛卡尔积X 1 × X 2 × ⋯ × X n X_1 \times X_2 \times \dots \times X_nX1×X2×⋯×Xn中的元素
X i X_iXi是位置i对应的可选元素集合
步骤
算法以“空向量”为初始状态，逐步向向量末尾添加元素，过程中通过“有效性判断”决定“推进”或“回溯”:
- 初始启动：从空向量开始，选择X 1 X_1X1中的最小元素作为x 1 x_1x1，得到部分向量( x 1 ) (x_1)(x1)
- 迭代构建：假设已得到部分向量( x 1 , x 2 , … , x j ) (x_1, x_2, \dots, x_j)(x1,x2,…,xj)，下一步尝试添加X j + 1 X_{j+1}Xj+1的最小元素，得到新向量v = ( x 1 , x 2 , … , x j , x j + 1 ) v = (x_1, x_2, \dots, x_j, x_{j+1})v=(x1,x2,…,xj,xj+1)
- 有效性判断与分支处理：对新向量v vv进行判断，分三种情况处理：
- 情况1：v 是最终解：记录该解；若问题只需要一个解，算法直接终止
- 情况2：v 是部分解（非最终但可继续扩展）：继续推进，选择X j + 2 X_{j+2}Xj+2的最小元素，重复步骤2
- 情况3：v 无效（既非最终解也非部分解）：
- 子情况3.1：X j + 1 X_{j+1}Xj+1仍有未选元素：将x j + 1 x_{j+1}xj+1替换为X j + 1 X_{j+1}Xj+1的下一个元素，重复步骤3
- 子情况3.2：X j + 1 X_{j+1}Xj+1无未选元素：执行回溯——将x j x_jxj替换为X j X_jXj的下一个元素；若X j X_jXj也无未选元素，继续回溯至x j − 1 x_{j-1}xj−1，以此类推，直到找到可替换的元素或回溯至空向量（无更多解）
