算法：回溯法

定义

问题描述

计算问题定义为关系 $R \subseteq I \times S$，其中 $I$ 是输入实例集合，$S$ 是候选解的集合，实例 $x$ 的解是满足 $(x,s) \in R$ 的任意元素 $s \in S(x)$

对于输入实例 $x \in I$，解空间 $S(x)$ 是满足约束的所有有效解的集合：

$$S(x) = \{s \in S \mid (x,s) \in R \}$$

问题P的全局解空间定义为：

$$SP = \{s \in S(x) \mid x \in I \land (x,s) \in R\}$$

关键特征：

判定问题：解空间为二元集合（如是、否）
搜索问题：解空间包含所有有效输出
最优化问题：解空间包含所有可行解，最优解满足： $$f(s^*) = \min_{s \in S(x)} f(s) \text{ 或者 } f(s^*) = \max_{s \in S(x)} f(s)$$

解空间与状态空间

解可表示为 $n$ 维元组 $(x_1, x_2, \cdots, x_n)$，其中 $x_i$ 取自有限集合 $S_i$，根据维度是否固定可分为定长元组（FLT）和变长元组（VLT）。

FLT：$X = \{(x_1, x_2, \cdots, x_n \mid x_i \in S_i)\}$

VLT：$X = \{X^1, X^2, \cdots, X^k\}$，其中 $X^j = \{(x_{j1}, x_{j2}, \cdots, x_{jk})\}$

概念	定义
问题状态	解空间中的一个点，可验证是否满足目标条件
初始状态	开始搜索的起始状态（根节点）
解状态	从当前状态到根节点的路径构成有效解
目标状态	解空间中满足最终目标的状态

问题的状态空间可定义为五元组 $(V, E, v_0, \mathcal{S}, \mathcal{A})$。其中

$V$ 表示问题状态的集合，
$E$ 表示状态间的转移关系集合，
$v_0 \in V$ 表示初始状态的根节点，
$\mathcal{S} \subseteq V$ 表示目标状态集合，
$\mathcal{A}$ 表示状态转移函数，生成有效子节点。

每个状态 $v \in V$ 可表示为

部分解：如组合问题中的元素子集

完整解：如排序问题中的有效排列

决策路径：如回溯算法中的选择序列

八皇后问题：在标准国际象棋棋盘上放置8个皇后，使得任意两个皇后不能互相攻击。

形式表达	表示
解的表示	8维元组 $(x_1, x_2, \cdots, x_8)$
解空间大小	$8^8$
约束条件	$\forall i, j, x_i \ne x_j$，且 $\| x_i - x_j \| \ne \| j-i \|$

子集和问题：在正整数集合 $S = \{w_1, w_2, \cdots, w_n\}$ 中寻找和为 $M$ 的子集。

例如，$M = 31$，$n = 4$，$W = (11, 13, 24, 7)$，存在解 $11 + 13 + 7 = 31$ 和 $24 + 7 = 31$

解的表示	表示
FLT表示	$(x_1, x_2, \cdots, x_n)$，其中 $x_i = 1$ 表示选中元素 $w_i$
VLT表示	$(j_1, j_2, \cdots, j_k)$，其中 $j_i$ 为选中元素下标

搜索策略

问题的求解需要遍历状态空间树。节点在遍历中有三种状态：

活动节点：已到达但未完全展开。
死亡节点：所有子节点已展开。
扩展结点：当前正在展开子节点的后的子节点。

搜索策略	内容
BFS	广度优先搜索
DFS	深度优先搜索
回溯算法	DFS + 剪枝函数
分支限界	树搜索 + 限界 + 节点选择策略
最佳优先搜索	优先扩展最有潜力的节点

回溯算法原理

回溯算法是一种通过深度优先搜索结合限界函数探索解空间的算法策略。

算法将问题抽象为一棵隐式的树形结构，其中树的深度对应决策步骤，宽度对应每一步可能的选择。

通过递归逐步构建解，并评估其成为最优解的可能性。若当前选择导致无效路径（如违反约束条件），或无法产生更优解时则回溯到上一步。

约束与限界函数

约束函数：在搜索过程中实时检查当前路径是否违反问题约束，若违反则进行剪枝。
限界函数：针对优化问题，若当前路径的代价已劣于已知的最优解，则提前终止该路径的探索。

例如，子集和问题的限界函数：

基础限界条件：当部分解的总和加上剩余元素的总和仍小于目标值时剪枝。 $$\sum_{i=1}^{k} W(i) X(i) + \sum_{i=k+1}^{n} W(i) < M$$

增强限界条件：元素非递减排序。 $$\sum_{i=1}^{k} W(i) X(i) + W(k+1) > M$$

算法的通用框架

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


k = 1;
while (k>0) 
    forall x[k] in 可行值集合 do
        // 基于已选值 x[1] ... x[k-1] 生成候选值
        if 约束条件 B(x[1], x[2], ..., x[k]) == false 
            if 当前路径构成有效解 then
                输出解 (x[1], x[2], ..., x[k]);
            k = k+1;    // 继续扩展至下一层
        else
            k = k-1;    // 回溯到上一层

// 解存储在 X(1:n) 中

例如，对于子集和问题，设：

当前部分和 $\displaystyle s = \sum_{i=1}^{k-1} W(i) X(i)$；
剩余元素和 $\displaystyle r = \sum_{i=k}^{n} W(i)$

则算法可表示为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// 扩展左子节点
if s+W(k)+W(k+1) > M then
  停止扩展左子树;
  r = r-W(k);
  转向右子树扩展;
else
  X(k) = 1;
  s = s+W(k);
  r = r-W(k);
  将当前节点设为扩展节点;

// 扩展右子节点
if s+r-W(k) < M or s+W(k+1) > M then
  停止扩展;
else
  X(k) = 0;

回溯算法的本质是系统性枚举，通过递归遍历所有可能解（状态空间树）和剪枝（约束函数和限界函数）动态排除无效路径，避免穷举。

📝 备注

回溯算法中，问题解空间被抽象为一棵隐式树形结构，树的深度对应决策步骤，宽度对应每一步的候选选择。

约束与限界函数的双重剪枝：

约束函数：实时检查路径合法性（如是否重复访问城市），若违反则剪枝。

限界函数：针对优化问题（如最短路径），若当前路径代价劣于已知最优解，则剪枝。

问题举例

两船装箱问题

给定两艘容量分别为 $c_1$ 和 $c_2$ 的货船和 $n$ 个集装箱。货箱重量分别为 $(w_1, w_2, \cdots, w_n)$ 且满足

$$\sum_{i=1}^{n} w_i \leqslant c_1 + c_2$$

需要判定是否存在一种装载方案，使得所有集装箱均可以装入两艘货船并且不超载。

基本原理

第一艘货船尽可能接近其容量装载。
剩余集装箱装入第二艘货船。

问题转化为选择集装箱子集，使其总重量尽可能接近 $c_1$ 的最优化问题：

$$\max \sum_{i=1}^{n} w_i x_i$$

约束条件：

$$\sum_{i=1}^{n} w_i x_i \leqslant c_1$$

其中 $x=(x_1, x_2, \cdots, x_n)$，$x_i=1$ 表示装载第 $i$ 个集装箱，否则记为 $0$。

例如，当 $n=4$，$c_1=12$，$w=[8,6,2,3]$ 时，状态空间树如下：

货箱装船问题

将集装箱按重量降序排列，假设当前扩展结点为第 $i-1$ 层，定义：

已装载的集装箱总重量：$\displaystyle w_c = \sum_{j=1}^{i-1} x_j w_j$
未装载集装箱总重量：$\displaystyle r = \sum_{j=i}^{n} w_j$
当前最优总重量：$w_{\text{best}}$

限界条件：

若 $w_c + w_i > c_i$，表明无法装载第 $i$ 个集装箱，则剪枝。
若 $w_c + r \leqslant w_{\text{best}}$，表明剩余集装箱无法改善当前最优解，则剪枝。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


int x[];
int w[];
int cw;
int r;

int bestx[];
int bestw;

void maxLoading(int i) {
    // 从第i个货物开始选择
    if (i > n) {
        // 已到达叶节点（没有新的可选货物）
        for (int j = 1; j <= n; j++) {
            bestx[j] = x[j];
        }
        bestw = cw; 
        return;
    }
    // 准备展开左子树（从剩余货物中去除第i个）
    r -= w[i];
    if (cw + w[i] <= c) {
        // 选择第i个货物
        x[i] = 1;
        cw += w[i];
        maxLoading(i+1);
    }
    // 准备展开右子树
    // 若右子树被剪枝，则回溯到上一层
    cw -= w[i];
    if (cw + r > bestw) {
        // 不选第i个货物
        x[i] = 0;
        maxLoading(i+1);
    }
    // 当 cw + w[i] > c 时，则剪枝
    // 当 cw + r <= bestw 时，则剪枝
    r += w[i];
    return;
}

例如，当 $n = 4$，$c_1 = 12$，$w = [8, 6, 2 ,3]$，剪枝后的状态树如下：

货船装箱的剪枝

因此最优解 $x=[1,0,0,1]$

0/1 背包问题

假设物品按 $\displaystyle \frac{p}{w}$ 降序排序，节点 $k-1$ 为 $E-$ 节点，定义限界函数：

当前装包利润：$\displaystyle p_c = \sum_{j=1}^{k-1} x_j p_j$
剩余物品总利润（松限界）：$\displaystyle p_r = \sum_{j=k}^{n} p_j$
部分松弛后的总利润（紧限界）：$\displaystyle p_r = \sum_{j=k}^{m-1} p_j + \frac{p_m}{w_m} \cdot \text{cleft}$
当前最大利润：$p_{\text{best}}$

部分松弛后的总利润（紧限界） = 完整放入的物品利润 + 剩余容量按价值密度部分装入第一个装不下的物品所获利润

限界条件：若 $p_c + p_r \leqslant p_{\text{best}}$ 则剪枝。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


void knapsack(int i) {
    // 从第i个物品开始选择
    if (i > n) {
        // 子节点
        bestp = cp;
        return;
    }
    // 检查左子树
    if (cw + w[i] <= c) {
        cw += w[i];
        cp += p[i];
        knapsack(i+1);
    }
    cw -= w[i];
    cp -= p[i];
    if (bound(i+1) > bestp) {
        // 右子树剪枝
        knapsack(i+1);
    }
}

// 限界函数
int bound(int i) {
    // 剩余容量
    int cleft = c - cw; 
    // 利润限界
    int b = cp;
    // 可完整放入的物品利润
    while (i <= n && w[i] <= cleft) {
        cleft -= w[i];
        b += p[i];
        i++;
    }
    // 剩余容量按价值密度部分装入
    if (i <= n) {
        b += p[i]/w[i] * cleft;
    }
    return b;
}

最大团问题

子图 $G' = \left<V', E'\right>$ 是无向图 $G = \left<V, E\right>$ 的完全子图，当且仅当 $V' \subset V$ 且对 $\forall u \in V', v \in V'$，$(u,v) \in E' \subset E$

完全子图即任意两点之间都有边相连的子图。

概念	定义
团	$G$ 的完全子图且不被其他完全子图包含
最大团	图中最大尺寸的团
独立顶点集	$G$ 的无边子图且不被其他独立集包含
最大独立顶点集	图中最大尺寸的独立集

例如，在下列图中：

$\{1,2\}$ 是完全子图但不是团。
$\{1,2,5\}$，$\{1,4,5\}$，$\{2,3,5\}$ 是最大团。
$\{2,4\}$ 是最大独立顶点集。

最大团示例

问题：寻找图 $G$ 的最大团。

使用固定长度元组 $X = x[1…n]$（$x_i = 1$ 表示包含顶点 $i$）表示解空间。状态空间树为子集树。限界条件：

从根到节点 $i$ 的顶点不能构成完全子图。
根到节点 $i$ 的顶点数加上剩余顶点数不超过当前最优解 $n_{best}$ 。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


int MaxClique(int v[]) {
    // 初始化
    x = new int [n+1];
    cn = 0;
    bestn = 0;
    bestx = v;
    maxClique(1);
    delete [] x;
    return bestn;
}

// 寻找最大团
void maxClique(int i) {
    if (i > n) {
        // 更新最大团
        for (int j = 1; j <= n; j++) {
            bestx[j] = x[j];
        }
        bestn = cn;
        return;
    }
    // 检查节点i是否与其他节点相连
    int OK = 1;
    for (int j = 1; j < i; j++) {
        if (x[j] && a[i][j] == NoEdge) {
            // 存在一对不相连的节点对则剪枝
            OK = 0;
            break;
        }
    }
    if (OK) {
        // 将i添加到集合中
        x[i] = 1; 
        cn++;
        maxClique(i+1);
        x[i] = 0;  
    }
    
    cn--;
    if (cn + n - i > bestn) {
        x[i] = 0;
        maxClique(i+1);
    }
}

旅行商问题

TSP问题的输入可以表示为一个图结构 $G = (V, E)$，其中：

$V = \{v_1, v_2, \cdots, v_n\}$ 为顶点集合（表示城市）
$E$ 为边集合（表示城市间的路径）
每条边 $e = (v_i, v_j)$ 关联一个非负权重 $a_{ij} \in \mathbb{R^+}$

TSP 的目标是寻找一个哈密尔顿回路（Hamiltonian cycle）$C$，满足：

$C$ 访问每个顶点恰好一次。
$C$ 是闭合回路（起点 = 终点）
回路的总权重（总距离）最小

定义 $x = x[1\cdots n]$（$x_i$ 为路径中第 $i$ 个节点的序号）表示解，目标函数

$$\sum_{i=1}^n a_{x_i, x_{i+1}}$$

其中 $(x_{n+1} = x_1)$，状态空间树为排列树。

限界条件：

若不存在连接 $x_i$ 与 $x_{i−1}$ 的边，则限界。
若从根到 $x_i$ 的路径距离超过当前最优解 $c_{best}$（已知最短路径），则限界。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


// 全局变量
int n;              // 城市数量
int[][] dist;       // 距离矩阵（dist[i][j] 表示城市i到j的距离）
boolean[] visited;  // 访问标记数组
int bestc = INF;    // 当前最优解（初始化为无穷大）
int[] bestpath;     // 最优路径
int[] current_path; // 当前路径

//主函数
void TSP_Backtrack() {
    visited[0] = true;
    // 初始化当前路径
    current_path.add(0);
    // 初始调用：当前城市0，已访问1个城市，路径长度0
    backtrack(0, 1, 0);
}

// 递归回溯函数
void backtrack(int current_city, int count, int current_length) {
    if (count == n) { 
        // 所有城市已访问，需返回起点
        int total_length = current_length + dist[current_city][0];
        if (total_length < bestc) {
            bestc = total_length;
            // 保存当前最优路径
            bestpath = copy(current_path); 
        }
        return;
    }
    // 遍历未访问城市
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            // 若当前路径+到i的距离已超过最优解，则跳过
            if (current_length + dist[current_city][i] >= bestc) {
                continue; 
            }
            // 选择城市i
            visited[i] = true;
            current_path.add(i);
            // 递归扩展
            backtrack(i, count+1, current_length + dist[current_city][i]);
            // 回溯
            visited[i] = false; 
            // 恢复路径
            current_path.remove_last();
        }
    }
}