回溯法求解简单组合优化问题

• 此为课题组所指导本科生和低年级硕士生学习组合优化问题汇报
• 所用教材：北京大学屈婉玲教授《算法设计与分析》
• 课程资料：https://www.icourse163.org/course/PKU-1002525003
  承诺不用于任何商业用途，仅用于学术交流和分享

• 更多内容请关注许志伟课题组官方中文主页：https://JaywayXu.github.io/zh-cn/

1. 四皇后问题 （9.2）

• 问题描述：在 $4\times 4$ 的方格棋盘上放置 4 个皇后，使得没有两个皇后在同一行、同一列、也不在同一条 45 度的斜线上。问有多少种可能的布局？
• 由于皇后没有区别、可以将行固定只考虑列维度，用 4 维向量 $ <x_1, x_2, x_3, x_4> $ 进行表示，例如：满足这种条件的解可以为 $<2,4,1,3>,<3,1,4,2>$

• 可以用四叉树的方式来表示解的搜索过程：

• 在 4 皇后问题中，我们需要在 $4\times 4$ 的棋盘上放置 4 个皇后，使得每两个皇后之间互不冲突（即不在同一行、同一列或同一对角线）。4叉树是表示这个问题搜索过程的有效结构。在这个分析中，我们将系统化地说明如何利用 4 叉树进行搜索、实现深度优先遍历、进行回溯和剪枝处理。

1.1. 4 叉树的搜索空间结构

1. 节点表示：
   每个节点表示部分解的状态，即已经放置了若干个皇后的方案。例如，节点 <2, 4> 表示前两行的皇后分别放在第 2 列和第 4 列。

2. 分支代表：
   每个节点有 4 个子节点，分别表示在当前行的 1、2、3、4 列 位置上放置皇后：

   • 第 $i$ 层的节点 对应于棋盘的第 $i$ 行，在这一层需要为该行选择一个皇后的位置。
   • 树叶节点 是最深层的节点（即到达第 4 层时），表示一个完整的解。

3. 搜索空间大小：
   理论上，4 叉树的所有路径总数为 $4^4=256$ 条。然而，在搜索过程中会遇到大量冲突，这些路径会被剪枝，因此实际搜索的复杂度比全树遍历要低。

1.2. 深度优先搜索（DFS）的实现

深度优先搜索（DFS） 是搜索这棵 4 叉树的主要算法。它通过递归探索每一条路径，直到找到完整解或发现冲突。

DFS 的搜索步骤：

1. 从根节点开始：
   初始状态为空向量 < >，表示尚未放置任何皇后。

2. 逐层放置皇后：

   • 第 1 层：尝试将第一个皇后放在 1、2、3、4 列 中的任一位置。
   • 第 2 层：根据第 1 层的选择，在不冲突的列中放置第二个皇后。
   • 第 3、4 层：依次为每一行的皇后选择合适的列位置。

3. 判断冲突：
   每当为某一层选择了一个列位置后，需要判断是否与之前放置的皇后冲突（即是否在同一列或同一对角线）。

4. 递归与回溯：

   • 如果当前路径符合条件，继续深入下一层。
   • 如果遇到冲突，则立即回溯到上一个节点，尝试其他列的选择。

1.3. 示例解读：

图中的路径 <2, 4, 1, 3> 是一个合法解的示例：

1. 第 1 行： 皇后放在第 2 列
2. 第 2 行： 皇后放在第 4 列
3. 第 3 行： 皇后放在第 1 列
4. 第 4 行： 皇后放在第 3 列

这个解满足所有约束条件，没有任何两个皇后处于同一列或同一对角线上。

1.4. 回溯与剪枝

在 4 皇后问题的搜索过程中，为了避免不必要的计算，我们会使用回溯和剪枝技术。

1. 回溯：
   当当前路径无解时，我们会回退到上一层的节点，尝试其他分支。

2. 剪枝：
   在每一层选择列时，如果某个选择会导致后续必然冲突，我们可以提前放弃该路径。例如：

   • 如果第 1 行的皇后放在第 1 列，那么第 2 行的皇后不能放在第 1 列或对角线位置。
   • 通过剪枝减少了不必要的搜索，提高了算法效率。

1.5. 算法效率与复杂度

• 搜索空间：
  4 叉树的所有叶子节点数为 $4^4=256$，但由于剪枝，实际遍历的路径数远少于 256 条。

• 时间复杂度：
  尽管理论上是 $O(n^n)$ 的复杂度，但剪枝大大减少了计算量。

• 内存使用：
  深度优先搜索使用递归栈，因此内存消耗较低，只需存储当前路径。

2. 0-1背包问题 （9.2）

2.1. 0-1 背包问题的建模

• 问题描述：

• 问题描述：有 $n$ 种物品, 每种物品只有 1 个. 第 $i$ 种物品价值为 $v_i$, 重量为 $w_i,i=1,2,\dots ,n$. 问如何选择放入背包的物品, 使得总重量不超过 $B$, 而价值达到最大？
  • 给定 $n$ 种物品，每种物品有对应的价值 $v_i$ 和重量 $w_i$。
  • 目标是在背包容量 $B$ 以内，选择若干物品，使得总价值最大。

• 数学建模：
  • 物品选择使用0-1向量表示：
    $$x_i=\{\begin{array}{ll}1,& \text{如果第 }i\text{ 种物品被选入背包}\\ 0,& \text{否则}\end{array}$$
  • 约束条件： 背包内物品总重量不得超过容量 $B$：
    $$\sum _{i=1}^n{w}_i\cdot x_i\le B$$
  • 目标函数： 最大化物品的总价值：
    $$\max \sum _{i=1}^n{v}_i\cdot x_i$$

• 实例： V = { 12 , 11 , 9 , 8 } , W = { 8 , 6 , 4 , 3 } , B = 13 V=\{12,11,9,8\}, W=\{8,6,4,3\}, B=13 V={12,11,9,8},W={8,6,4,3},B=13
• 最优解：$<0,1,1,1>$, 价值：28，重量：13

2.2. 搜索空间与解的表示

• 搜索空间：
  使用 二叉树（子集树） 表示所有可能的解。

  • 每个节点表示物品是否选择：$ <x_1, x_2, …, x_k> $（部分向量）。
  • 树的叶节点是完整解，总共有 $2^n$ 个叶节点。

• 二叉树遍历：

  • 左分支代表当前物品未选入背包（$x_i=0$）。
  • 右分支代表当前物品选入背包（$x_i=1$）。

2.3. 回溯法与剪枝策略

2.3.1 回溯法

• 回溯法采用递归探索所有可能的解空间。
• 遍历过程中：
  • 每次选择是否将当前物品放入背包。
  • 若走到叶子节点（即所有物品都做出选择），则判断当前解是否满足约束条件并计算其总价值。

2.3.2 剪枝策略

在回溯过程中，我们可以提前终止某些路径的探索，这就是剪枝。剪枝策略有以下几种常见形式：

1. 容量约束剪枝

• 当当前路径上物品的总重量已经超过背包容量 $B$ 时，无需继续探索该路径。

2. 上界剪枝（估值剪枝）

• 在当前节点，根据剩余未选物品的最大可能价值计算出一个上界。
• 如果这个上界加上当前已选物品的总价值仍小于当前已知最优解，则提前终止该路径。

3. 可行性剪枝

• 如果在某一层中做出选择后，剩余的物品即使全选也无法填满背包或超越已知最优价值，则该路径无解，立即剪枝。

4. 优先分支策略

• 在搜索树中，优先探索可能性较大的分支（例如优先选择价值密度较高的物品），通过贪心策略减少搜索时间。

2.4. 示例

• 虚线代表剪枝手段
  

3. TSP（9.2）

3.1 问题描述

货郎问题（也称为旅行商问题，TSP）是经典的组合优化问题。目标是在给定的一组城市中，找到一条恰好经过每个城市一次的回路，并使得总路径长度最小。

• 输入：
  给定 $n$ 个城市组成的城市集 C = { c 1 , c 2 , . . . , c n } C = \{c_1, c_2, ..., c_n\} C={c1​,c2​,...,cn​}，以及城市之间的距离 $d(c_i,c_j)$（两城市间的距离是对称的，即 $d(c_i,c_j)=d(c_j,c_i)$）。

• 输出：
  一个遍历所有城市的最优排列 $k_1,k_2,...,k_n$，使得总路径长度最小。回路的总长度计算公式为：

  $$\min \left\{\sum _{i=1}^{n-1}d(c_{k_i},c_{k_{i+1}})+d(c_{k_n},c_{k_1})\right\}$$

• 当然，最后的回程要计算进其中。

3.2 建模与搜索空间

3.2.1 排列树

• 搜索空间：
  TSP问题的解空间可以表示为排列树，每条路径对应一种城市的遍历顺序。

  • 对于 $n$ 个城市，排列树的叶节点数量为 $(n-1)!$，因为我们固定起点城市后，剩下的城市需要进行全排列。

• 树的结构：

  • 根节点表示起始城市。
  • 每层节点代表一个城市的选择。
  • 每条从根到叶节点的路径表示一种遍历顺序。

3.3 具体实例分析

3.3.1 实例输入

• 城市集： C = { 1 , 2 , 3 , 4 } C = \{1, 2, 3, 4\} C={1,2,3,4}
• 城市之间的距离：
  $$d(1,2)=5,d(1,3)=9,d(1,4)=4$$
  $$d(2,3)=13,d(2,4)=2,d(3,4)=7$$

3.3.2 排列树示例

• 在图示排列树中，部分路径如下：
  • <1, 2> 表示起点为城市1，下一步选择城市2。
  • <1, 2, 4, 3> 是完整的一条路径。

3.3.3 最优解

• 路径： <1, 2, 4, 3>
• 总长度：
  $$5+2+7+9=23$$

3.4 求解方法

3.4.1 暴力搜索

• 枚举所有可能的路径，计算每条路径的总长度，并找出其中最短的路径。这种方法的时间复杂度为 $O(n!)$，不适用于大规模问题。

3.4.2 回溯法与剪枝优化

• 回溯法：
  使用递归逐层选择城市，并判断当前路径是否可能成为最优解。

• 剪枝策略：
  在遍历过程中，若发现当前路径的部分长度已经超过已知的最优解，则终止该路径的进一步探索。

4. 排列树与N叉树的详细比较

在解决货郎问题（TSP问题）时，我们使用了排列树来表示搜索空间。这部分将详细讲解排列树的定义及其与N叉树的区别，帮助我们更深入理解排列树的结构及其在TSP问题中的应用。

4.1 什么是排列树？

排列树是一种表示所有排列组合的树结构。

• 排列是指对给定元素集中的所有元素进行重新排序。
• 在排列树中，每条从根节点到叶节点的路径都代表一种元素的排列。

排列树的特性

• 规模： 对于 $n$ 个元素的排列，排列树的叶节点总数为 $n!$（所有元素的全排列）。
• 深度： 树的深度为 $n$，因为我们需要在每一层依次选择一个未被使用的元素。
• 子节点数量：
  • 在排列树的第 $i$ 层，每个节点的子节点数量为 $n-i$（即剩余未选择的元素数量）。

排列树结构的示例

例子：对集合 { 1 , 2 , 3 } \{1, 2, 3\} {1,2,3} 进行排列

排列树的结构如下：

     根节点（空集）
    /      |      \
  1        2        3
 / \      / \      / \
2   3    1   3    1   2
|   |    |   |    |   |
3   2    3   1    2   1

• 叶节点包含所有排列，如：[1, 2, 3]、[1, 3, 2] 等。
• 这棵树共有 $3!=6$ 个叶节点。

4.2 什么是N叉树？

N叉树是一种每个节点最多有N个子节点的树结构。它是更广义的树结构形式。

• 根节点：是树的起点节点。
• 子节点：每个节点可以有0到N个子节点。
• 深度：树的深度可以不固定。

N叉树的特性

• N叉树的每一层表示每个节点可以向下延伸出至多 $N$ 个子节点。
• 搜索空间的大小：
  • 对于有 $n$ 层的 N叉树，其可能的叶节点数目为 $N^n$。

示例：4叉树

                 根节点
        /      |      |      \
       1       2      3       4
     / | \   / | \   / | \   / | \
    5  6  7  8  9 10 11 12 13 14 15

在这种结构中，每个节点有4个子节点。

4.3 排列树与N叉树的区别

4.4 货郎问题中的排列树

在货郎问题中，我们使用排列树来表示搜索空间。假设有 $n$ 个城市需要访问，排列树的每条路径代表一种城市的访问顺序。

• 树的规模： 排列树的叶节点数量为 $(n-1)!$，因为我们固定了起始城市，其余城市需要排列。
• 路径： 每条路径从根节点开始，逐层选择一个未访问的城市，直到访问完所有城市。

4.5 八皇后问题中的N叉树

在八皇后问题中，我们的搜索空间用的是N叉树。每一层代表棋盘的一行，节点的子节点代表该行中皇后可以放置的位置。

• 树的结构： 每层有 $n$ 个子节点，因为每一行有 $n$ 个可供选择的位置。
• 路径： 每条路径代表一种棋盘上皇后放置的方案。

4.6 总结

• 排列树适用于解决需要排列组合的优化问题，如货郎问题（TSP）。
• N叉树适用于具有多种选择的搜索问题，如八皇后问题。
• 两者在搜索空间的结构和大小上有所不同，但都通过递归和回溯技术探索解空间。

5. 回溯法的设计思想和适用条件 （9.3）

5.1 问题分析

• 满足约束条件就继续向前搜索，不满足约束条件就回溯到父节点，并且裁剪掉当前节点下的子树

5.2 回溯算法的基本思想与设计思路

• 回溯算法是一种求解搜索问题和优化问题的重要方法。其本质是通过递归地遍历问题的解空间，将问题分解为多个子问题，并在满足约束条件的情况下扩展解向量。如果在某一阶段发现当前路径无法满足问题的约束条件，算法将回退到上一步，尝试其他路径，直到找到满足条件的解或遍历所有可能的路径。

5.2.1 解的表示与向量结构

在许多经典的组合优化问题中，解通常用向量来表示。以n皇后问题、0-1背包问题和 货郎问题（TSP） 为例，这些问题的解空间都可以抽象成向量：

• n皇后问题：使用一个n维向量，其中每个元素代表一行中皇后所在的列位置。
• 0-1背包问题：解是一个0-1向量，每个元素的取值为0或1，表示对应物品是否被选择。
• 货郎问题（TSP）：解为一个排列向量，描述了访问所有城市的顺序。

5.2.2 搜索空间与树结构

在回溯算法中，搜索过程通常可以被抽象为树结构，其中每个节点代表一个部分解：

• n皇后问题：搜索空间为n叉树，每层代表一行，节点的分支表示皇后可能放置的列位置。
• 0-1背包问题：对应的搜索空间是子集树，每个节点表示一个物品的选择状态（选或不选）。
• 货郎问题（TSP）：其解空间是一棵排列树，节点表示访问城市的顺序。

• 在树结构中，根节点表示初始状态，内部节点代表部分解，叶节点则表示完整的解。当搜索路径无法满足约束条件时，算法会回退到父节点，进行路径的探索，这一过程称为回溯。

5.2.3 搜索方式与策略选择

• 回溯算法的搜索过程采用系统化的遍历，常见的搜索策略包括：

• 深度优先搜索（DFS）：沿着某一条路径尽可能深入，当无路可走时回退至上一级节点。
• 广度优先搜索（BFS）：逐层遍历所有节点，直到找到可行解或遍历完所有节点。
• 函数优先搜索：基于某种启发函数选择优先路径。
• 宽深结合搜索：将广度优先与深度优先结合，在某些层次采用广度优先，后续采用深度优先。

• 这几种策略各有优劣，深度优先能够节省空间，但可能陷入无效路径；广度优先能够尽早找到解，但需要更多的存储空间。

5.2.4 剪枝与约束条件

• 在搜索过程中，为了避免遍历无效的路径，回溯算法会使用剪枝策略，即在发现某个节点不满足约束条件时，立即停止对该路径的进一步探索。常见的约束条件包括：

• n皇后问题：不同皇后不能位于同一行、同一列或同一斜线上。
• 0-1背包问题：已选择的物品的总重量不能超过背包的容量。
• 货郎问题（TSP）：每个城市只能访问一次。

• 通过剪枝，算法能够显著减少搜索空间，提高求解效率。

5.2.5 节点动态状态管理

• 回溯算法在搜索过程中使用不同的节点状态来管理访问进度：

• 白节点：尚未访问。
• 灰节点：正在访问该节点，但其子节点未遍历完。
• 黑节点：该节点的子树已经遍历完，搜索完成后不再访问。

• 这种状态管理能够避免重复访问节点，确保搜索过程高效进行。

5.2.6 存储与路径管理

• 在回溯算法中，需要保存当前路径，以便在回溯时能够恢复状态。通常使用链表结构来存储路径，因为链表能够动态增加和删除节点，适应搜索过程中的需求。

5.3 回溯算法的适用条件与多米诺性质：系统性讲解

在回溯算法中，适用条件和多米诺性质是确保算法能够正确、高效求解问题的核心概念。它们为解空间的有效遍历提供了理论依据，确保了算法能够通过剪枝避免无效路径的探索。

5.3.1 部分解与约束条件的表示

在回溯算法的每一步，都会生成一个部分解，该部分解可以表示为一个向量：

$$⟨x_1,x_2,\dots ,x_k⟩$$

对于该部分向量，需要检验它是否满足问题的约束条件。满足条件可以用一个谓词 $P(x_1,x_2,\dots ,x_k)$ 表示。如果该谓词为真，则当前部分解有效，可以继续扩展；若为假，则需要回溯。

例如，在n皇后问题中，若当前放置的 $k$ 个皇后彼此不攻击，则表示该部分解满足约束条件，即 $P(x_1,x_2,\dots ,x_k)$ 为真。

5.3.2 多米诺性质的概念

多米诺性质是回溯算法的核心原则，其数学表述为：

$$P(x_1,x_2,\dots ,x_{k+1})⟹P(x_1,x_2,\dots ,x_k)$$

这意味着，如果一个 $k+1$ 维的部分向量满足约束条件，则其前 $k$ 维的部分向量也必然满足条件。这一性质确保了算法在扩展解向量时，能够逐步构建符合约束的完整解。

反之，如果某个部分解不满足约束条件，则扩展后的 $k+1$ 维向量也一定不满足条件。在这种情况下，算法会停止当前路径的探索，进行回溯，尝试其他路径。这一剪枝策略使得算法能够有效减少计算量。

5.3.3 逆否命题与剪枝策略

多米诺性质的逆否命题为：

$$\neg P(x_1,x_2,\dots ,x_k)⟹\neg P(x_1,x_2,\dots ,x_{k+1})$$

该命题的含义是：若 $k$ 维向量不满足约束条件，则无需扩展到 $k+1$ 维向量，因为它也一定不满足条件。这一逆否命题为剪枝策略提供了理论支持，保证算法在检测到无效路径时能够迅速回溯，避免无效计算。

5.3.4 多米诺性质在 n 皇后问题中的应用

在 n 皇后问题 中，若当前已放置的 $k$ 个皇后存在攻击关系，则再放置第 $k+1$ 个皇后是没有意义的，因为无论如何放置，冲突仍然存在。因此，算法会在此时回溯到上一级节点，尝试其他放置方式。

这种基于多米诺性质的剪枝策略，使得回溯算法能快速排除无效解路径，提升算法效率。

5.3.5 回溯算法不丢解的依据

多米诺性质是回溯算法不丢解的重要依据。在解空间的遍历过程中，算法依赖这一性质，确保不会遗漏任何有效解。当某条路径不满足约束条件时，算法能确定其后续路径也无法生成有效解，因此可以安全地进行剪枝和回溯。

回溯算法的高效性来源于合理的适用条件和多米诺性质。这些理论确保了算法能够通过系统的搜索和剪枝策略，有效避免无效路径的探索。在实际应用中，确保问题结构满足多米诺性质是至关重要的，这样才能保证回溯算法的正确性和性能。

在应用回溯算法时，需要仔细分析问题的性质和约束条件，确保它们符合回溯算法的适用条件。通过递归构建部分解和剪枝无效路径，算法可以高效地在解空间中找到可行解或最优解。

5.4 回溯算法的反例：不满足多米诺性质的情况与改进

在回溯算法的应用中，合理的约束条件设计对于算法的正确性和高效性至关重要。如果约束条件不满足多米诺性质，算法在搜索路径上可能会出现错误，导致遗漏解或产生冗余计算。以下通过一个具体的不等式求解问题，系统性地展示不满足多米诺性质的问题，并通过数学变换使其满足多米诺性质。

5.4.1 问题描述

考虑如下不等式约束问题：

$$5x_1+4x_2-x_3\le 10$$

其中，变量 $x_1,x_2,x_3$ 的取值范围为：

$$1\le x_k\le 3(k=1,2,3)$$

目标是找到所有满足该不等式的整数解。这一问题的求解需要通过遍历不同变量的组合，并检查哪些组合满足上述约束。

5.4.2 约束条件的初始设计与问题分析

我们定义如下谓词用于判断部分解是否满足约束条件：

• $P(x_1)$：$5x_1\le 10$
• $P(x_1,x_2)$：$5x_1+4x_2\le 10$
• $P(x_1,x_2,x_3)$：$5x_1+4x_2-x_3\le 10$

这些谓词判断是否可以继续扩展部分解。如果当前部分解满足条件，则继续扩展；若不满足，则回溯到上一层节点。

然而，该问题的设计存在一个关键缺陷：它不满足多米诺性质。具体而言：

$$5x_1+4x_2-x_3\le 10\nRightarrow 5x_1+4x_2\le 10$$

即使 $x_1,x_2,x_3$ 的三维向量满足不等式，也不能推断 $x_1,x_2$ 的部分向量必然满足条件。这导致回溯算法在错误的路径上回溯，并可能漏解。

例如，当 $x_3$ 取较大值时，即使 $5x_1+4x_2$ 超过 10，但减去 $x_3$ 后整个不等式仍可能成立。这会导致算法误以为部分解无效，提前回溯，从而漏掉正确解。

5.4.3 变换以满足多米诺性质

为了使问题满足多米诺性质，我们对变量 $x_3$ 进行如下变换：

$$x_3=3-x_3^{\prime }$$

将该变换代入不等式后，得到：

$$5x_1+4x_2+x_3^{\prime }\le 13$$

此时，$x_3^{\prime }$ 的取值范围为：

$$0\le x_3^{\prime }\le 2$$

变换后的不等式满足了多米诺性质：如果部分解满足当前条件，则扩展后的解也必然满足条件。这一变换使得算法能够正确判断哪些路径需要剪枝，避免误判和回溯错误。

5.4.4 求解与验证

在变换后的约束条件下，使用回溯算法可以找到所有满足条件的解。在求得 $x_1,x_2,x_3^{\prime }$ 的组合后，我们通过公式：

$$x_3=3-x_3^{\prime }$$

将结果还原为原始问题的解，确保所有可能的解都已找到，并且没有遗漏。

5.5 小结：回溯算法的适用条件与设计步骤

5.5.1 回溯算法的适用条件

• 回溯算法的核心适用条件是多米诺性质。该性质确保，当某一部分解满足约束条件时，扩展后的完整解也会满足。这一性质的满足可以保证算法在扩展和回溯过程中不丢失解，并且能够有效剪枝，提高搜索效率。

5.5.2 回溯算法的设计步骤

1. 定义解向量和每个分量的取值范围
   解向量可以表示为：

   $$⟨x_1,x_2,\dots ,x_n⟩$$

   每个分量 $x_i$ 的取值集合为 $X_i$，其中 $i=1,2,\dots ,n$。

2. 计算分量的取值范围
   在部分向量 $⟨x_1,x_2,\dots ,x_{k-1}⟩$ 的基础上，确定第 $k$ 维分量 $x_k$ 的可取集合：

   $$S_k\subseteq X_k$$

   由于前 $k-1$ 维分量的取值，$S_k$ 可能会缩小，因此需要动态计算其当前的取值范围。

3. 确定节点儿子的排列规则
   每个节点的子节点代表不同方向的分支。排列规则可根据 $S_k$ 中值的大小排序（如从小到大）来确定遍历顺序。

4. 判断是否满足多米诺性质
   在进行搜索前，需要判断问题是否满足多米诺性质。只有满足多米诺性质时，回溯算法才能正确剪枝，保证不丢失解。

5. 确定每个节点分支的约束条件
   定义节点扩展和回溯的条件。如果某一节点不满足约束条件，则需要回溯到父节点，停止该方向的搜索。

6. 确定搜索策略
   根据问题的性质，选择合适的搜索策略，包括：

   • 深度优先搜索（DFS）
   • 宽度优先搜索（BFS）
   • 混合搜索策略

7. 确定数据结构以存储搜索路径
   搜索过程中需要存储当前的路径，通常使用链表结构即可满足存储需求。