许志伟课题组官方中文主页：https://JaywayXu.github.io/zh-cn/
节点表示：
每个节点表示部分解的状态，即已经放置了若干个皇后的方案。例如，节点 <2, 4> 表示前两行的皇后分别放在第 2 列和第 4 列。
分支代表：
每个节点有 4 个子节点，分别表示在当前行的 1、2、3、4 列 位置上放置皇后：
搜索空间大小：
理论上，4 叉树的所有路径总数为 \(4^4 = 256\) 条。然而，在搜索过程中会遇到大量冲突，这些路径会被剪枝，因此实际搜索的复杂度比全树遍历要低。
深度优先搜索（DFS） 是搜索这棵 4 叉树的主要算法。它通过递归探索每一条路径，直到找到完整解或发现冲突。
从根节点开始：
初始状态为空向量 < >，表示尚未放置任何皇后。
逐层放置皇后：
判断冲突：
每当为某一层选择了一个列位置后，需要判断是否与之前放置的皇后冲突（即是否在同一列或同一对角线）。
递归与回溯：
图中的路径 <2, 4, 1, 3> 是一个合法解的示例：
这个解满足所有约束条件，没有任何两个皇后处于同一列或同一对角线上。
在 4 皇后问题的搜索过程中，为了避免不必要的计算，我们会使用回溯和剪枝技术。
回溯：
当当前路径无解时，我们会回退到上一层的节点，尝试其他分支。
剪枝：
在每一层选择列时，如果某个选择会导致后续必然冲突，我们可以提前放弃该路径。例如：
搜索空间：
4 叉树的所有叶子节点数为 \(4^4 = 256\)，但由于剪枝，实际遍历的路径数远少于 256 条。
时间复杂度：
尽管理论上是 \(O(n^n)\) 的复杂度，但剪枝大大减少了计算量。
内存使用：
深度优先搜索使用递归栈，因此内存消耗较低，只需存储当前路径。
\[x_i = \begin{cases} 1, & \text{如果第 } i \text{ 种物品被选入背包} \\ 0, & \text{否则} \end{cases} \]
\[\sum_{i=1}^n w_i \cdot x_i \leq B \]
\[\max \sum_{i=1}^n v_i \cdot x_i \]
搜索空间：
使用 二叉树（子集树） 表示所有可能的解。
二叉树遍历：
在回溯过程中，我们可以提前终止某些路径的探索，这就是剪枝。剪枝策略有以下几种常见形式：
货郎问题（也称为旅行商问题，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\} \]
搜索空间：
TSP问题的解空间可以表示为排列树，每条路径对应一种城市的遍历顺序。
树的结构：
\[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 \]
<1, 2> 表示起点为城市1，下一步选择城市2。<1, 2, 4, 3> 是完整的一条路径。
<1, 2, 4, 3>\[5 + 2 + 7 + 9 = 23 \]
回溯法：
使用递归逐层选择城市，并判断当前路径是否可能成为最优解。
剪枝策略：
在遍历过程中，若发现当前路径的部分长度已经超过已知的最优解，则终止该路径的进一步探索。
在解决货郎问题（TSP问题）时，我们使用了排列树来表示搜索空间。这部分将详细讲解排列树的定义及其与N叉树的区别，帮助我们更深入理解排列树的结构及其在TSP问题中的应用。
排列树是一种表示所有排列组合的树结构。
例子：对集合 \(\{1, 2, 3\}\) 进行排列
排列树的结构如下：
根节点（空集）
/ |
1 2 3
/ \ / \ /
2 3 1 3 1 2
| | | | | |
3 2 3 1 2 1
[1, 2, 3]、[1, 3, 2] 等。N叉树是一种每个节点最多有N个子节点的树结构。它是更广义的树结构形式。
示例：4叉树
根节点
/ | |
1 2 3 4
/ | \ / | \ / | \ / |
5 6 7 8 9 10 11 12 13 14 15
在这种结构中，每个节点有4个子节点。
| 特点 | 排列树 | N叉树 |
|---|---|---|
| 结构 | 每层根据剩余元素选择排列组合 | 每层节点最多有N个子节点 |
| 叶节点数量 | \(n!\)（n个元素的全排列） | \(N^n\)（每层最多N个选择） |
| 深度 | 总深度为 \(n\) | 深度可变 |
| 用途 | 用于排列问题，如TSP | 用于多种搜索问题 |
| 示例问题 | 货郎问题（TSP） | 八皇后问题的解空间 |
在货郎问题中，我们使用排列树来表示搜索空间。假设有 \(n\) 个城市需要访问，排列树的每条路径代表一种城市的访问顺序。
在八皇后问题中，我们的搜索空间用的是N叉树。每一层代表棋盘的一行，节点的子节点代表该行中皇后可以放置的位置。
在许多经典的组合优化问题中，解通常用向量来表示。以n皇后问题、0-1背包问题和 货郎问题（TSP） 为例，这些问题的解空间都可以抽象成向量：
在回溯算法中，搜索过程通常可以被抽象为树结构，其中每个节点代表一个部分解：
在回溯算法中，适用条件和多米诺性质是确保算法能够正确、高效求解问题的核心概念。它们为解空间的有效遍历提供了理论依据，确保了算法能够通过剪枝避免无效路径的探索。
在回溯算法的每一步，都会生成一个部分解，该部分解可以表示为一个向量：
\[\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)\) 为真。
多米诺性质是回溯算法的核心原则，其数学表述为：
\[P(x_1, x_2, \dots, x_{k+1}) \implies P(x_1, x_2, \dots, x_k) \]
这意味着，如果一个 \(k+1\) 维的部分向量满足约束条件，则其前 \(k\) 维的部分向量也必然满足条件。这一性质确保了算法在扩展解向量时，能够逐步构建符合约束的完整解。
反之，如果某个部分解不满足约束条件，则扩展后的 \(k+1\) 维向量也一定不满足条件。在这种情况下，算法会停止当前路径的探索，进行回溯，尝试其他路径。这一剪枝策略使得算法能够有效减少计算量。
多米诺性质的逆否命题为：
\[\neg P(x_1, x_2, \dots, x_k) \implies \neg P(x_1, x_2, \dots, x_{k+1}) \]
该命题的含义是：若 \(k\) 维向量不满足约束条件，则无需扩展到 \(k+1\) 维向量，因为它也一定不满足条件。这一逆否命题为剪枝策略提供了理论支持，保证算法在检测到无效路径时能够迅速回溯，避免无效计算。
在 n 皇后问题 中，若当前已放置的 \(k\) 个皇后存在攻击关系，则再放置第 \(k+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 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\) 后整个不等式仍可能成立。这会导致算法误以为部分解无效，提前回溯，从而漏掉正确解。
为了使问题满足多米诺性质，我们对变量 \(x_3\) 进行如下变换：
\[x_3 = 3 - x_3' \]
将该变换代入不等式后，得到：
\[5x_1 + 4x_2 + x_3' \leq 13 \]
此时，\(x_3'\) 的取值范围为：
\[0 \leq x_3' \leq 2 \]
变换后的不等式满足了多米诺性质：如果部分解满足当前条件，则扩展后的解也必然满足条件。这一变换使得算法能够正确判断哪些路径需要剪枝，避免误判和回溯错误。
在变换后的约束条件下，使用回溯算法可以找到所有满足条件的解。在求得 \(x_1, x_2, x_3'\) 的组合后，我们通过公式：
\[x_3 = 3 - x_3' \]
将结果还原为原始问题的解，确保所有可能的解都已找到，并且没有遗漏。
定义解向量和每个分量的取值范围
解向量可以表示为：
\[\langle x_1, x_2, \dots, x_n \rangle \]
每个分量 \(x_i\) 的取值集合为 \(X_i\)，其中 \(i = 1, 2, \dots, n\)。
计算分量的取值范围
在部分向量 \(\langle x_1, x_2, \dots, x_{k-1} \rangle\) 的基础上，确定第 \(k\) 维分量 \(x_k\) 的可取集合：
\[S_k \subseteq X_k \]
由于前 \(k-1\) 维分量的取值，\(S_k\) 可能会缩小，因此需要动态计算其当前的取值范围。
确定节点儿子的排列规则
每个节点的子节点代表不同方向的分支。排列规则可根据 \(S_k\) 中值的大小排序（如从小到大）来确定遍历顺序。
判断是否满足多米诺性质
在进行搜索前，需要判断问题是否满足多米诺性质。只有满足多米诺性质时，回溯算法才能正确剪枝，保证不丢失解。
确定每个节点分支的约束条件
定义节点扩展和回溯的条件。如果某一节点不满足约束条件，则需要回溯到父节点，停止该方向的搜索。
确定搜索策略
根据问题的性质，选择合适的搜索策略，包括：
确定数据结构以存储搜索路径
搜索过程中需要存储当前的路径，通常使用链表结构即可满足存储需求。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。