Data-Structure/Algorithm/Exam/7.md

# 第七章 回溯法 (Backtracking)

## 目录

* **7.1 回溯一般方法**

* **7.2 回溯法的效率估计**

* **7.3 n-皇后问题**

* **7.4 子集和问题**

* **7.5 图着色问题**

* **7.6 小结**


---

## 7.1 回溯的一般方法

### 1. 方法适用的问题特点

回溯法主要用于解决以下特征的问题：

* **多阶段决策问题/组合问题**：适用于这类需要分步决策的问题。


* **元组表达**：问题的解向量用元组 $(x_1, x_2, ..., x_n)$ 来表示，其中元素通常取自某个有穷集 $S_i (1 \le i \le n)$， $n$ 表示问题规模。


* **固定长 n-元组**：表示为 $(x_1, ..., x_n)$。


* **不定长 k-元组**：表示为 $(x_1, ..., x_k), k \le n$。




* **多米诺性质**：问题必须满足多米诺性质才能有效应用回溯。



#### 多阶段决策问题的细分：

* **组合搜索**：关注解的**存在性**，问题描述中**仅存在约束条件**，目标是寻找满足约束条件的一个解或所有解（可行解）。


* **组合优化**：关注解的**最优性**，问题描述中除了约束条件外，**还存在目标函数**，目标是寻找一个具有极小值或极大值的可行解，即最优解（极小化/极大化问题）。



### 2. 多米诺性质 (Domino Property)

* **定义**：设 $P(x_1, ..., x_i)$ 是关于向量 $(x_1, ..., x_i)$ 的某种性质的判定。当 $P(x_1, ..., x_{i+1})$ 为真时，一定有 $P(x_1, ..., x_i)$ 为真，其中 $0 < i < n$。


* **推论**：根据多米诺性质，如果部分解 $P(x_1, ..., x_i)$ 不成立，则其延伸出的 $P(x_1, ..., x_{i+1})$ 也必然不成立。


* **回溯应用**：满足多米诺性质的组合问题，能够根据约束条件和目标函数不断检验正在构造的部分解向量 $(x_1, ..., x_i)$。一旦发现其不成立，则**无需考虑后续 $x_{i+1}, ..., x_n$ 的取值**。


* **思考题**：利用多米诺性质能够提高算法效率，它会如何起作用？



### 3. 提高算法效率的关键机制

设约束函数 $B$ 实现问题的约束条件，对于 $n$-元组中的 $x_i \in S_i$，设其集合大小 $|S_i| = m_i$。

* **硬性处理（暴力搜索）**：向量总个数 $m = m_1 \times m_2 \times ... \times m_n$，需要对这 $m$ 个 $n$-元组逐一检测是否满足 $B(x_1, ..., x_n)$ 来找出解。


* **回溯法（利用多米诺性质）**：约束函数 $B$ 可以提前检验正在构造中的部分向量 $(x_1, ..., x_i)$。如果发现它不能导致问题的解，则立即终止该向量的继续构造（不再构造 $x_{i+1}, ..., x_n$ 的取值），从而直接**减少了 $m_{i+1} \times ... \times m_n$ 个向量**的测试。



### 4. 解空间树 (Solution Space Tree)

回溯法解决问题的过程，就是在解空间树上搜索答案状态结点的过程。树中的核心概念包括：

* **显式约束**：每个 $x_i$ 的取值集合 $S_i$，可能与问题实例有关，也可能无关。


* **隐式约束**：描述了 $x_i$ 彼此之间相互制约相关的情况，与问题实例有关，对应于**约束函数**。


* **解空间**：满足**所有显式约束条件**的元组集合。


* **解空间树**：基于解空间画成的树状结构。


* **问题状态**：解空间树中的**所有结点**。


* **解状态 X**：由树根到结点 X 的路径确定了解空间中的一个元组（解状态满足显式约束条件）。


* **答案状态 X**：由树根到解状态结点 X 的路径确定了问题的一个解（答案状态**同时满足显式约束和隐式约束条件**）。



### 5. 问题建模步骤

1. **确定元组表达形式**：选择固定长 $n$-元组 $(x_1, ..., x_n)$ 或不定长 $k$-元组 $(x_1, ..., x_k), k \le n$。


2. **确定约束条件**：明确显式约束和隐式约束。


3. **检验多米诺性质**：确保问题满足该性质。


4. **确定解空间树**：明确树中的问题状态、解状态和答案状态。



---

### 建模对比实例：子集和问题 (Subset Sum Problem)

* **问题描述**：已知 $n+1$ 个正数 $W_i (1 \le i \le n)$ 和 $M$，要求找出 $W_i$ 的和是 $M$ 的所有子集。


* **问题实例**：$n=4$, $(w_1, w_2, w_3, w_4) = (11, 13, 24, 7)$, $M=31$。


* 可行解1：$11, 13, 7$

* 可行解2：$24, 7$




#### 表达方式一：固定长元组表达

* **元组形式**：大小固定的 4-元组 $(x_1, x_2, x_3, x_4)$。


* **显式约束**：$x_i \in \{0, 1\}$。如果选择 $W_i$ 则 $x_i = 1$，否则 $x_i = 0$。


* **隐式约束**：$\sum_{i=1}^n w_i x_i = M$。


* **多米诺性质**：如果部分解向量的和已经大于 $M$，则包含它的长解向量之和也必然大于 $M$。


* **解空间大小**：共计 $2^4 = 16$ 个元组。


* 可行解1 对应元组：$(1, 1, 0, 1)$

* 可行解2 对应元组：$(0, 0, 1, 1)$



* **解空间树特征**：问题状态（全部结点）共 **31个**；解状态（叶结点）共 **16个**（从根到叶的一条路径确定解空间的一个元组）；答案状态共 **2个**。



#### 表达方式二：不定长元组表达

* **元组形式**：大小可变的 $k$-元组 $(x_1, ..., x_k), k \le n$。


* **显式约束**：$x_i \in \{j | j \text{ 是 } w \text{ 的下标}, 1 \le j \le n\}$，且满足 $x_i < x_{i+1} (1 \le i < k)$（目的是**避免重复情况**，例如排除将 `(1,2,4)` 和 `(1,4,2)` 视为不同解）。


* **隐式约束**：相应的 $W_{x_i}$ 的和等于 $M$。


* **多米诺性质**：如果部分解向量的和已经大于 $M$，则包含它的扩展元组也必然大于 $M$。


* **解空间**：共计 16 个元组。


* 可行解1 对应元组：$(1, 2, 4)$

* 可行解2 对应元组：$(3, 4)$



* **解空间树特征**：问题状态和解状态均为 **16个**（从根到任何结点的一条路径均确定解空间中的一个元组）；答案状态共 **2个**。


* **思考题**：比较两种元组表达形式下的解空间树，请基于 $n$ 的渐进表示来描述结点个数。



---

### 6. 动态树中的结点类型

* **静态树**：即标准的解空间树，其结构**与具体的问题实例无关**。


* **动态树**：在求解过程中实际生成的树结构，其结构**与具体实例紧密相关**。


* **活结点 (Live Node)**：自身已经生成，但其儿子结点还没有全部生成的结点。


* **E-结点 (E-Node, 正在扩展的结点)**：当前正处于生成其儿子结点状态的活结点。


* **死结点 (Dead Node)**：不再进一步扩展，或者其所有儿子结点已经全部生成的结点。



### 7. 动态树结点的生成方式

* **第一种方式（深度优先 $\rightarrow$ 回溯法）**：当前的 E-结点 $R$ 一旦生成了一个新的儿子结点 $C$，这个结点 $C$ 就立即变成一个新的 E-结点。当检测完了子树 $C$ 之后，原 $R$ 结点才再次成为 E-结点，去生成下一个儿子结点。


* **第二种方式（广度优先/优先队列 $\rightarrow$ 分支限界法）**：当前结点一旦成为 E-结点，就一直处理到它变成死结点为止。其生成的所有儿子结点全部加入到“活结点表”中，然后再从活结点表中选择下一个新的 E-结点。



### 8. 回溯法的设计思想

1. 针对问题定义解空间树结构：包括元组形式、显式约束条件和隐式约束条件。


2. 检验问题是否满足多米诺性质。


3. 以**深度优先方式**搜索解空间树，在搜索过程中使用**约束函数 $B$** 避免无效搜索（剪枝）。


4. 对于当前 E-结点 $R$，一旦生成一个新的儿子结点 $C$， $C$ 就成为新的 E-结点，搜索向纵深方向移动。


5. 如果当前 E-结点不能满足约束函数 $B$，或者再没有多余的儿子节点，则其成为**死结点**，搜索停止向纵深移动，转而**向上回溯**至最近的一个活结点，使该活结点重新成为 E-结点。


6. 搜索过程持续进行，直到找到所要求的解，或解空间树中已没有活结点为止。



### 9. 回溯法的形式化描述

假设要找出所有的答案结点，用路径 $(x_1, x_2, ..., x_{k-1})$ 表示状态空间树中由根出发到达结点 $Y$ 的路径。 $T(x_1, ..., x_{k-1})$ 是元素的集合，使得对每个 $x_k$， $(x_1, ..., x_{k-1}, x_k)$ 是一条由根到 $Y$ 的一个儿子结点的路径。对于约束函数 $B_k$，如果路径 $(x_1, ..., x_k)$ 不可能延伸到一个答案结点，则 $B_k(x_1, ..., x_k)$ 取假值 (`false`)，否则取真值 (`true`)。

#### 算法7.1：回溯法的非递归算法形式

```pascal
procedure BACKTRACK(n)
    int k, n
    local X(1: n)
    k <- 1
    while (k > 0) do
        if (还剩有没检验的X(k) 使得 X(k) ∈ T(X(1)...X(k-1)) and B(X(1)...X(k)) == TRUE) then
            if (X(1)...X(k) 是一条抵达答案结点的路径) then 
                print (X(1)...X(k))
            endif
            k <- k + 1  // 向纵深扩展
        else 
            k <- k - 1  // 没有可用选择，向上回溯
        endif
    repeat
end BACKTRACK
```

#### 算法7.2：回溯法的递归算法形式
```pascal
procedure RBACKTRACK(k)
    // 进入算法时，解向量X中的前k-1个分量X(1)...X(k-1)已经被赋值
    global X(1:n);
    int k, n;
    for (满足下式的每个X(k), X(k) ∈ T(X(1)...X(k-1)) and B(X(1),...X(k)) == true) do
        if ((X(1),...,X(k)) 是一条抵达答案结点的路径) then
            print (X(1)...X(k)) 
        endif
        call RBACKTRACK(k+1)  // 递归调用，扩展下一层
    repeat
end RBACKTRACK
```

---

## 7.2 回溯法的效率分析

### 1. 决定回溯法效率的因素
回溯算法的执行效率主要由以下四个因素决定：
1. **生成下一个 $X(k)$ 的时间**（即生成一个子结点所需的计算时间）。
2. **满足显式约束条件的 $X(k)$ 的数目**（即该结点的子结点个数）。
3. **约束函数 $B_k$ 的计算时间**（即检验一个子结点合法性所需的时间）。
4. **使 $B$ 为真的 $X(k)$ 的数目**（即真正通过检验、未被限界的子结点个数）。

* **约束函数 $B$ 的剪枝作用**：旨在避免生成那些不包含可行解的子树。然而，设计更强的约束函数会增加单次计算时间，因此需要在**计算时间**和**结点减少程度**之间进行折中。
* **思考题**：上述哪一个因素体现出不同实例产生的结点数不同？（提示：第四个因素——使 $B$ 为真的数目）。

### 2. 回溯法的效率估计与蒙特卡罗方法
* **最坏时间复杂度**：如果解空间的完全树结点数是 $2^n$ 或 $n!$，回溯算法最坏情况下的时间复杂度为 $O(p(n)2^n)$ 或 $O(q(n)n!)$，其中 $p(n)$ 和 $q(n)$ 为关于 $n$ 的多项式（包含计算 $B$ 的花费）。
* **估算的必要性**：由于回溯法在解决同一问题的不同实例时表现出的工作量具有**巨大差异**，对某些实例非常高效，而对某些实例极慢。因此，在实际运行巨大规模实例前，应该对算法的工作能效进行估算（即估计活结点的个数/动态树结点个数）。
* **估算工具**：处理一棵树实际所要生成的结点数，可以用**蒙特卡罗方法 (Monte Carlo Method)** 估算出来。

### 3. 蒙特卡罗方法的一般思想
1. 假定约束函数是固定的，在状态空间树中**生成一条随机路径**。
2. 设 $x$ 是这条路径上位于第 $i$ 级的一个结点。
3. 设约束函数确定该结点 $x$ 满足条件、可用的儿子结点数目为 $m_i$。
4. 从这 $m_i$ 个可用儿子结点中**随机选中一个**，重复上述过程，直到当前结点是叶结点或者儿子结点都被限界（为0）为止。
5. **不受限界结点的估计总数公式**：
   $$m = 1 + m_1 + m_1 \cdot m_2 + m_1 \cdot m_2 \cdot m_3 + ...$$
   其中 $m_i$ 表示第 $i$ 级结点平均没受限界的儿子结点数。

#### 统计推断原理图解：
* 第一级：共1个根结点 $\rightarrow$ 经 $B$ 检验保留 1 个。
* 第二级：通过 $B$ 检验的结点有个数 $m_1$ 个（推断第二级总共有 $m_1$ 个结点）。从这 $m_1$ 个结点中随机抽一个。
* 第三级：被抽中结点的子结点中，共有 $m_2$ 个满足 $B$ 函数检验。据此代表性抽样推断：第三级通过 $B$ 检验的结点总数一共有 $m_1 \cdot m_2$ 个，以此类推。

#### 算法7.3：效率估计算法
```pascal
Procedure ESTIMATE()
    // 程序沿着状态空间树中一条随机路径产生这棵树中不受限界结点的估计数
    m <- 1; r <- 1; k <- 1
    loop
        T_k <- {X(k) : X(k) ∈ T(X(1),...,X(k-1)) and B_k(X(1),...,X(k))}
        if SIZE(T_k) == 0 then exit endif
        r <- r * SIZE(T_k)  // 推算第k级的期望结点总数
        m <- m + r          // 累加得到前k级的估计结点总数
        X(k) <- CHOOSE(T_k) // 从集合 T_k 中随机地挑选一个元素作为下一步路径
        k <- k + 1
    repeat
    return m
end ESTIMATE
```

### 4. 蒙特卡罗方法的特点
* **优点**：特别适用于需要**找到所有答案结点**的情况；当约束函数固定不变时，计算非常方便，对树中同一级结点的评估均适用。
* **缺点**：若算法的目标**只需寻找一个解**，实际生成的结点数往往远远小于估计值 $m$；另外，在实际搜索中，随着检索的进行，约束条件通常会动态变强，从而使实际的 $m$ 值比估计值更小。

---

## 7.3 n-皇后问题 (n-Queens Problem)

### 1. 问题描述与建模
* **问题定义**：在一个 $n \times n$ 的棋盘上放置 $n$ 个皇后，使得任何两个皇后之间都不能互相“攻击”。即任意两个皇后都不能处于同一行、同一列以及同一条斜角线上。
* **回溯建模表达**：
    * **n-元组 $(x_1, ..., x_n)$**：其下标 $i$ 表示第 $i$ 行，分量 $x_i$ 表示第 $i$ 行的皇后放置在第 $x_i$ 列上（天然隐含了不同行）。
    * **显式约束条件**：$x_i \in \{1, 2, ..., n\}, 1 \le i \le n$，且任意两个 $x_i$ 互不相同（确保不同列）。其对应的完全解空间元组个数为 **$n!$**。
    * **隐式约束条件**：任意两个皇后不能在同一条斜角线上。

### 2. 4-皇后问题回溯搜索实例
以 $n=4$ 为例（解空间满叶子结点数为 $4! = 24$）：
1. 根结点(1)作为初始唯一的活结点，变为 E-结点，路径为 `()`。
2. 生成儿子结点2，路径变为 `(1)`，代表将皇后1放在第1行第1列。
3. 结点2变成 E-结点，尝试生成其儿子。生成结点3，路径变为 `(1, 2)`。经检验冲突，结点3被杀死（死结点 `B`），算法回溯到结点2。
4. 在结点2下生成另一个儿子结点8，路径变为 `(1, 3)`。结点8成为新 E-结点。
5. 结点8尝试生成儿子：生成结点9 `(1, 3, 2)` 和结点11 `(1, 3, 4)`，经检验均因冲突被杀死，导致结点8也变成死结点，算法再次回溯。
6. 回溯到结点2，生成儿子结点13，路径为 `(1, 4)`。经检测其后续儿子不可能导致答案，结点13被杀死，回溯。
7. 此时结点2的所有儿子都被处理完毕，结点2死亡。算法回溯到根结点(1)，生成右侧新分支结点18，路径变为 `(2)`（皇后1放在第2列）。
8. 结点18扩展出结点19 `(2, 1)` 和结点24 `(2, 3)`，均被杀死。
9. 结点18继续生成儿子结点29，路径为 `(2, 4)`，结点29成为 E-结点。
10. 结点29生成儿子结点30，路径为 `(2, 4, 1)`。
11. 结点30生成儿子结点31，路径为 `(2, 4, 1, 3)`。此时 $k=4=n$，成功找到 4-皇后问题的一个可行解。
* **统计**：整个搜索树过程中一共仅生成了 **16个活结点**。

### 3. 约束函数设计思想
要在棋盘上判断斜线冲突，可以分析矩阵坐标规律：
* **同一主斜角线（左上到右下）**：线上的每个元素坐标具有相同的 **“行 - 列”** 差值，即 $i - x_i = k - x_k$。
* **同一副斜角线（右上到左下）**：线上的每个元素坐标具有相同的 **“行 + 列”** 和值，即 $i + x_i = k + x_k$。
* **冲突等价公式**：两个皇后放置在 $(i, X(i))$ 和 $(k, X(k))$ 冲突，当且仅当：
  $$i - X(i) = k - X(k) \quad \text{或} \quad i + X(i) = k + X(k)$$
  合并绝对值形式即为：
  $$|X(i) - X(k)| = |i - k|$$

因此，当确定前 $k-1$ 行皇后已经放好，现在欲将第 $k$ 行的皇后放在第 $X(k)$ 列时，只需令 $X(k)$ 与前文已放好的所有 $X(i) (i=1..k-1)$ 逐个比较。若存在 $X(k) = X(i)$（同列）或 $|X(i) - X(k)| = |i - k|$（同斜线），则当前位置非法。

#### 算法7.4：能否放置一个新皇后（约束函数 PLACE）
```pascal
procedure PLACE(k)
    // 若一个皇后能放在第k行和第X(k)列，则返回true，否则返回false。
    // X是全局数组，进入此过程时已置入了当前前k个值，ABS是绝对值函数。
    int i, k
    i <- 1
    while (i < k) do
        if (X(i) == X(k) or ABS(X(i) - X(k)) == ABS(i - k)) then 
            return false
        endif
        i <- i + 1
    repeat
    return true
end PLACE
```

#### 算法7.5：n-皇后问题的整体回溯算法
```pascal
procedure NQUEENS(n)
    int k, n, X(1: n)
    X(1) <- 0; k <- 1
    while (k > 0) do
        X(k) <- X(k) + 1  // 尝试下一列
        while (X(k) <= n and not PLACE(k)) do
            X(k) <- X(k) + 1; // 当前列不能放皇后k时，继续移向下一列
        repeat 
        if (X(k) <= n) then
            if (k == n) then 
                print (X)  // 成功抵达最后一层，打印可行解
            else 
                k <- k + 1; X(k) <- 0  // 纵深向下，准备求解下一个皇后
            endif
        else 
            k <- k - 1;  // 当前行无合适位置，回溯到上一行
        endif
    repeat
end NQUEENS
```

### 4. 8-皇后问题的效率估计
* **完全状态空间树结点数**：若仅满足显式约束（互不同列），树中总结点数为：
  $$1 + 8 + (8 \times 7) + (8 \times 7 \times 6) + ... + 8! = 109,601 \text{ 个}$$
* **使用蒙特卡罗方法估计剪枝后的树结点数**：
    * 在某一次随机路径探路实验中：第一级有1个结点，第二级有8个分支通过检测，第三级有5个分支通过（估计该级有 $8 \times 5 = 40$ 结点），第四级有4个通过（估计 $8 \times 5 \times 4 = 160$），最终某次通路算出的估计结果可能为 1649 或 1401。
    * **多次实验取平均值**：最终得到的动态估计结点数为 **1625 个**。
    * **剪枝效率**：实际不受限结点的数量大约只占原始状态空间树总节点数的：
      $$\frac{1625}{109601} \approx 1.48\%$$
      说明约束函数 `PLACE` 提供了极强的剪枝能力。

---

## 7.4 子集和问题 (Subset Sum Problem)

### 1. 问题描述与回溯建模
* **问题定义**：假定有 $n$ 个不同的正数权值 $W(1:n)$ 和一个目标和 $M$，找出这些数中所有使得元素之和恰好等于 $M$ 的组合。
* **元组建模表达**：
    * 使用固定长的 **n-元组 $(x_1, ..., x_n)$** 表示。
    * **显式约束条件**：$x_i \in \{0, 1\}, 1 \le i \le n$。若选择将 $W_i$ 纳入子集，则 $x_i = 1$，否则 $x_i = 0$。
    * **隐式约束条件**：$\sum_{i=1}^n w_i x_i = M$。

### 2. 核心约束函数优化机制
为了能够高效地进行提前剪枝，必须**首先将输入的正数权值 $W(i)$ 按非降（从小到大）次序进行预排序**。
设当前已决定了前 $k$ 个元素的状态，则定义：
* **条件一（可行性检验）**：若满足当前已选和加上后续所有剩余权值之和大于等于 $M$，即：
  $$\sum_{i=1}^{k} W(i)X(i) + \sum_{i=k+1}^{n} W(i) \ge M$$
  则说明当前的局部解序列 $(X(1),...,X(k))$ 依然有可能导致最终的一个答案结点。
* **条件二（基于排序的超重限界）**：由于权值已从小到大排序，如果当前已选和加上下一个最小的权值 $W(k+1)$ 都已经超过了 $M$，即：
  $$\sum_{i=1}^{k} W(i)X(i) + W(k+1) > M$$
  那么在其后无论选哪个更重的元素都必然超重，因此当前路径**绝不可能**导致答案结点。

**综上所述**，约束函数 $B_k(X(1)...X(k)) = \text{true}$ 当且仅当：
$$\sum_{i=1}^{k} W(i)X(i) + \sum_{i=k+1}^{n} W(i) \ge M \quad \text{且} \quad \sum_{i=1}^{k} W(i)X(i) + W(k+1) \le M$$

### 3. 算法7.6：子集和的回溯递归算法
```pascal
Procedure SUMOFSUB(s, k, r)
    // s: 当前已确定的前 k-1 个分量的权值之和 = \sum_{j=1}^{k-1} W(j)X(j)
    // r: 剩余还未做决策的所有元素的总权值之和 = \sum_{j=k}^{n} W(j)
    // 进入此过程时，W(j) 必须已经按非降次序排列，且满足 W(1) <= M 以及 \sum_{i=1}^n W(i) >= M
    integer W(1:n), M, n;
    boolean X(1:n);
    integer s, k, r;

    // 1. 生成左儿子（选择当前元素，即 X(k) <- 1）
    // 由于在上层判断过 B_{k-1} == true，进入时天然满足 s + W(k) <= M 且 s + r >= M
    X(k) <- 1;
    if (s + W(k) == M) then 
        print(X) // 恰好凑齐M，打印一个可行解
    else if (s + W(k) + W(k+1) <= M) then
        call SUMOFSUB(s + W(k), k + 1, r - W(k)) // 剩余空间足够，继续向深层递归
    endif

    // 2. 生成右儿子（不选当前元素，即 X(k) <- 0）并计算约束函数B的值
    if (s + r - W(k) >= M and s + W(k+1) <= M) then
        X(k) <- 0; 
        call SUMOFSUB(s, k + 1, r - W(k)) // 放弃当前元素，将r扣除后向深层递归
    endif
end SUMOFSUB

// 初始调用方式：
SUMOFSUB(0, 1, \sum_{i=1}^n W(i))
```

#### 核心思考题：
1. 如果不对数组 $W$ 进行预排序，算法应该怎样设计？算法的执行效率会发生怎样的变化？
2. 为什么在左子树分支中，能够极大地简化约束条件的判定代码？

### 4. 实例分析与效率估计
* **测试实例**：$n=6, M=30, W=(5, 10, 12, 13, 15, 18)$。初始时 $s=0, r=73$。
* **暴力树开销**：在不施加任何约束函数前，全状态解空间树的所有结点都会被访问，其中叶结点（解状态）有 $2^6 = 64$ 个，部分解结点有 63 个，总共 127 个结点。
* **蒙特卡罗预估**：设定某一探索路径为 1-3-4-7-9，基于该路径统计出各层的可用分支数，估算出不受限界的结点总数：
  $$m = 1 + 2 + (2 \times 2) + (2 \times 2 \times 1) + (2 \times 2 \times 1 \times 1) + 0 = 15 \text{ 个}$$
* **实际运行结果**：在添加了本节设计的约束函数后进行实际运行，整棵动态树**一共仅仅生成了 26 个结点**。算法在执行中寻找（或提前剪枝识别出）了 **3个答案结点**，其实际产生的结点开销与蒙特卡罗方法的估计结果（15个不受限结点）非常接近。

---

## 7.5 图着色问题 (Graph Coloring Problem, GCP)

### 1. 问题描述与判定变体
* **经典图着色问题**：最著名的 **NP-完全问题** 之一。给定一个无向连通图 $G=(V, E)$，用不同的颜色给图中的顶点进行着色，要求**任何两个相邻的顶点不能着相同的颜色**。数学上追求的目标是：最少需要多少种颜色？
* **图的 m-着色判定问题**：本节着重解决其判定形式——给定图 $G$ 和固定的 $m$ 种不同颜色，问：是否存在一种合法的着色方案，使得任何两个相邻顶点的颜色都不同？如果判定为“是”，则要求利用回溯法给出具体的着色方案。

### 2. 问题建模与解空间树
* **元组表达**：使用固定长 $n$-元组 $X=(x_1, x_2, ..., x_n)$，其中分量 $x_i$ 表示图中的第 $i$ 个顶点所涂的颜色编号。
* **显式约束**：$1 \le x_i \le m$。
* **隐式约束**：如果顶点 $i$ 和顶点 $j$ 之间在图中存在边（即 $(i, j) \in E$），则它们的颜色不能相同，即 $x_i \ne x_j$。
* **树形结构**：对应的完全解空间树是一棵**完全 $m$ 叉树**。例如，当顶点数 $n=4$，颜色数 $m=3$ 时，树的第4层将拥有非常密集的解状态叶结点。

### 3. 算法实现

#### 算法7.7：判断当前顶点 k 的着色是否合法（约束函数 OK）
```pascal
procedure OK(k)
    // C 是全局颜色决策数组，进入此过程时，前 k 个顶点的值已由上层尝试置入。
    int i, k
    i <- 1
    while (i < k) do
        if (i 和 k 之间有边存在 and C(i) == C(k)) then 
            return false  // 相邻且颜色冲突，非法
        endif
        i <- i + 1
    repeat
    return true  // 与前文所有相邻顶点都不冲突，合法
end OK
```

#### 算法7.8：图着色判定问题的回溯算法
```pascal
Procedure MCOLORING(V, E, C, n, m)
    // 图 G=(V,E)，n 个顶点，m 种颜色
    C(1:n) <- 0; k <- 1  // 初始化颜色数组，C记录决策序列，从第1个顶点开始尝试
    while (k >= 1) do
        C(k) <- C(k) + 1  // 尝试为当前顶点更涂下一种颜色
        while (not OK(k) and C(k) <= m) do 
            C(k) <- C(k) + 1  // 如果当前颜色冲突且没超出最大颜色数，继续试探下一种颜色
        repeat
        if (C(k) <= m) then
            if (k == n) then 
                print(C); return true  // 所有的顶点都已经成功合法着色，打印结果并成功返回
            else 
                k <- k + 1; C(k) <- 0  // 成功解决当前顶点，准备为下一个新顶点着色
            endif
        else 
            k <- k - 1  // 1到m种颜色都无法让顶点k合法，此时发生冲突，清除当前状态并向前回溯
        endif
    repeat  // 如果回溯导致 k 减小到 0，说明整棵树已遍历完毕且无解
    return false
END MCOLORING
```

### 4. 实例分析
* **分析实例**：考虑一个包含 $n=5$ 个顶点的无向图，给定颜色数 $m=3$。
* **空间开销**：由于解空间树是完全 $m$ 叉树，最后一层（第5层）拥有的完全叶子结点个数为：
  $$m^n = 3^5 = 243 \text{ 个}$$
* **搜索轨迹示例**：算法从顶点 A 开始分配：$A=1 \rightarrow B=1$(经OK检验相邻冲突，杀死结点3) $\rightarrow B=2$(通过) $\rightarrow C=1$(通过) $\rightarrow$ 随后由于图的边连通关系，在深层多次遇到颜色耗尽冲突，在死结点处触发回溯，最终在搜索树的右侧状态结点14处成功找到了一组全局合法解并打印。
* **遗留思考题**：
    1. 基于当前的判定算法，如果要求出最少需要多少种颜色的“最优解”（组合优化），其整体的时间复杂度是多少？
    2. 图着色问题是否同样适用于蒙特卡洛方法进行算法效率估计？

---

## 7.6 本章小结

### 1. 回溯法适用核心总结
* 回溯法核心适用于解决**多阶段决策问题 / 组合问题**，且问题必须满足**多米诺性质**。
* **设计思想的通用概述步骤**：
  1. 确定最适合描述解的向量形式（固定长 $n$-元组 或 不定长 $k$-元组）。
  2. 将问题的总约束拆分解构为显式约束和隐式约束条件。
  3. 确定解空间树的逻辑结构。
  4. 设计出高效、能在极早期切断无效分支的**约束函数 $B$**。
  5. 以**深度优先（DFS）方式**动态搜索树，配合约束函数完成智能剪枝与回溯。

### 2. 解空间树的两大基本分类
* **集合树 (Subset Tree)**：问题的解本质上是对已知集合中各个元素的**一种“取舍”决策**（即选或不选，分支通常为0/1）。
    * *典型代表*：子集和问题、0/1背包问题。
* **排列树 (Permutation Tree)**：问题的解是对已知集合中各个元素进行的一种**空间顺序上的重组或排列**。
    * *典型代表*：n-皇后问题、图着色判定问题。

### 3. 回溯法的效率控制与改进方向
* **效率决定者**：静态解空间树的大小决定了算法在最坏情况下的理论时间上限；而约束函数 $B$ 的强弱与剪枝能力直接决定了求解时动态树的实际生成规模。在追求找出**所有解**时，可以通过蒙特卡罗方法对效率进行离线预估。
* **进阶改进策略**：
    1. **分支优先策略**：根据树的局部形态，优先搜索那些包含儿子结点数较少或产生可行解概率更高的优势分支。
    2. **利用对称性剪枝**：充分挖掘问题在物理或数学结构上的对称性，对结构完全对称的子树直接进行大范围裁剪。
    3. **子问题分解合并**：将大规模问题横向分解为多个相互独立的子问题，各自独立求解完毕后再行合并，以减小单次搜索的指数爆炸惩罚。

### 4. 章节学习掌握要求
* **7.1 节**：必须透彻掌握回溯法适用的问题特点、解空间树基本结构、三种状态结点（问题、解、答案状态）、动态树结点的两种生成方式，能熟练写出两类算法框架。
* **7.2 节**：掌握影响回溯法效率的四个关键要素，理解并能手动运用蒙特卡罗方法对动态树结点数进行统计推算。
* **7.3 - 7.5 节**：要求对 **n-皇后问题、子集和问题、图着色问题** 这三大经典案例的解空间树画法、专有约束函数设计、整体回溯算法代码实现达到烂熟于心的程度，掌握约束优化剪枝的思想，能够独立识别、建模并设计解决全新的可计算性组合问题。