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

news/2024/10/23 13:02:40

此为课题组所指导本科生和低年级硕士生学习组合优化问题汇报
所用教材：北京大学屈婉玲教授《算法设计与分析》
课程资料：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 叉树的搜索空间结构

节点表示：
每个节点表示部分解的状态，即已经放置了若干个皇后的方案。例如，节点 <2, 4> 表示前两行的皇后分别放在第 2 列和第 4 列。
分支代表：
每个节点有 4 个子节点，分别表示在当前行的 1、2、3、4 列 位置上放置皇后：
- 第 $i$ 层的节点 对应于棋盘的第 $i$ 行，在这一层需要为该行选择一个皇后的位置。
- 树叶节点 是最深层的节点（即到达第 4 层时），表示一个完整的解。
搜索空间大小：
理论上，4 叉树的所有路径总数为 $4^4 = 256$ 条。然而，在搜索过程中会遇到大量冲突，这些路径会被剪枝，因此实际搜索的复杂度比全树遍历要低。

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

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

DFS 的搜索步骤：

从根节点开始：
初始状态为空向量 < >，表示尚未放置任何皇后。
逐层放置皇后：
- 第 1 层：尝试将第一个皇后放在 1、2、3、4 列 中的任一位置。
- 第 2 层：根据第 1 层的选择，在不冲突的列中放置第二个皇后。
- 第 3、4 层：依次为每一行的皇后选择合适的列位置。
判断冲突：
每当为某一层选择了一个列位置后，需要判断是否与之前放置的皇后冲突（即是否在同一列或同一对角线）。
递归与回溯：
- 如果当前路径符合条件，继续深入下一层。
- 如果遇到冲突，则立即回溯到上一个节点，尝试其他列的选择。

1.3. 示例解读：

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

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

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

1.4. 回溯与剪枝

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

回溯：
当当前路径无解时，我们会回退到上一层的节点，尝试其他分支。
剪枝：
在每一层选择列时，如果某个选择会导致后续必然冲突，我们可以提前放弃该路径。例如：
- 如果第 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, \ldots, n$. 问如何选择放入背包的物品, 使得总重量不超过 $B$, 而价值达到最大？
- 给定 $n$ 种物品，每种物品有对应的价值 $v_i$ 和重量 $w_i$。
- 目标是在背包容量 $B$ 以内，选择若干物品，使得总价值最大。

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

实例：$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\}$，以及城市之间的距离 $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\}$
城市之间的距离：
\[d(1, 2) = 5, \quad d(1, 3) = 9, \quad d(1, 4) = 4 \]
\[d(2, 3) = 13, \quad d(2, 4) = 2, \quad 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/ \      / \      / \
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叉树的区别

特点	排列树	N叉树
结构	每层根据剩余元素选择排列组合	每层节点最多有N个子节点
叶节点数量	$n!$（n个元素的全排列）	$N^n$（每层最多N个选择）
深度	总深度为 $n$	深度可变
用途	用于排列问题，如TSP	用于多种搜索问题
示例问题	货郎问题（TSP）	八皇后问题的解空间

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 部分解与约束条件的表示

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

\[\langle x_1, x_2, \dots, x_k \rangle \]

对于该部分向量，需要检验它是否满足问题的约束条件。满足条件可以用一个谓词 $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}) \implies 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) \implies \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 \leq 10 \]

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

\[1 \leq x_k \leq 3 \quad (k = 1, 2, 3) \]

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

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

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

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

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

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

\[5 x_1+4 x_2-x_3 \leq 10 \nRightarrow 5 x_1+4 x_2 \leq 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' \]

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

\[5x_1 + 4x_2 + x_3' \leq 13 \]

此时，$x_3'$ 的取值范围为：

\[0 \leq x_3' \leq 2 \]

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

5.4.4 求解与验证

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