[算法设计与分析-从入门到入土] 回溯法

[算法设计与分析-从入门到入土] 回溯法

个人导航

知乎：https://www.zhihu.com/people/byzh_rc

CSDN：https://blog.csdn.net/qq_54636039

注：本文仅对所述内容做了框架性引导，具体细节可查询其余相关资料or源码

参考文章：各方资料

回溯法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对应的可选元素集合

步骤

算法以“空向量”为初始状态，逐步向向量末尾添加元素，过程中通过“有效性判断”决定“推进”或“回溯”:

1. 初始启动：从空向量开始，选择X 1 X_1X1​中的最小元素作为x 1 x_1x1​，得到部分向量( x 1 ) (x_1)(x1​)
2. 迭代构建：假设已得到部分向量( 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​)
3. 有效性判断与分支处理：对新向量v vv进行判断，分三种情况处理：
   1. 情况1：v 是最终解：记录该解；若问题只需要一个解，算法直接终止
   2. 情况2：v 是部分解（非最终但可继续扩展）：继续推进，选择X j + 2 X_{j+2}Xj+2​的最小元素，重复步骤2
   3. 情况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​，以此类推，直到找到可替换的元素或回溯至空向量（无更多解）