mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4mobile wallpaper 5mobile wallpaper 6
Profile Image of the Author
黎明
公告
欢迎来到黎明的小站。本站用于堆叠平时的技术痕迹，记录一些值得留存的想法。
标签
3400 字
9 分钟
旅行售货员问题（回溯法与分支限界法）
2026-06-15 10:10:02
Algorithm
Algorithm
/
回溯法
/
分支限界
/
旅行商问题

1. 什么是旅行售货员问题？#

旅行售货员问题（Traveling Salesman Problem，简称 TSP），也叫旅行商问题，是组合优化和计算机科学中最著名的难题之一。

问题的描述很简单：

有一个售货员要拜访 nn 个城市，每个城市恰好拜访一次，最后回到出发城市。已知任意两个城市之间的距离，求总路程最短的环游路线。

例如，44 个城市 A、B、C、D，售货员从 A 出发，一条合法路线是：

A→B→D→C→AA \rightarrow B \rightarrow D \rightarrow C \rightarrow A

它经过了所有城市各一次，并回到了起点。

NOTE

TSP 表面上像一个”排路线”的小问题，但它是经典的 NP-Hard 问题。目前没有任何多项式时间的精确算法，规模一大就只能靠剪枝、近似或启发式方法来求解。

2. 问题的数学描述#

把城市看作图的顶点，城市之间的道路看作带权边，TSP 就是：在一个 带权完全图 上，找一条权重最小的哈密顿回路（Hamiltonian cycle）。

设 nn 个城市编号为 0,1,…,n−10, 1, \ldots, n-1，距离矩阵为 dijd_{ij}，表示城市 ii 到城市 jj 的距离。一条环游可以表示为一个排列：

x=(x0, x1, …, xn−1)x = (x_0,\ x_1,\ \ldots,\ x_{n-1})

其中 x0x_0 是出发城市，x1,…,xn−1x_1, \ldots, x_{n-1} 是其余城市的访问顺序。总路程为：

L(x)=∑i=0n−2dxi, xi+1+dxn−1, x0L(x) = \sum_{i=0}^{n-2} d_{x_i,\ x_{i+1}} + d_{x_{n-1},\ x_0}

第一项是从出发城市一路走到最后一个城市的距离，第二项是从最后一个城市回到起点的距离。目标是：

min⁡xL(x)\min_{x} L(x)
NOTE

距离矩阵不一定是对称的（去程和回程距离可以不同），也不一定满足三角不等式。本文为方便演示，使用对称的距离矩阵。

3. 解空间：排列树#

由于售货员要给除起点外的每个城市排定一个访问顺序，所以 TSP 的解空间就是排列。

固定出发城市为 x0=0x_0 = 0（因为环游从哪个城市出发都是等价的），剩下的 n−1n-1 个城市做全排列。因此解空间是一棵排列树，这和 素数环问题 的结构是一样的。

不同的环游方案数上界为：

(n−1)!(n-1)!
为什么是 (n−1)!(n-1)! 而不是 n!n!

因为环游是一个回路，起点选哪个城市不影响结果，所以固定一个出发城市，只排列剩下的 n−1n-1 个城市即可。如果距离对称，正向和反向是同一条回路，还可以再除以 22，即 (n−1)!2\dfrac{(n-1)!}{2}。

排列树长这样（以 n=4n = 4 为例）：

                 起点 0
                /   |   \
            选 1   选 2   选 3
           /  \    ...    ...
        选 2  选 3
         |     |
        选 3  选 2
         |     |
      回到 0  回到 0

回溯法就是在这棵排列树上做深度优先遍历：能走就走，走不通或明显不优就回头。

4. 回溯法#

4.1 基本思路#

回溯法的核心步骤：

  1. 固定出发城市为 00，标记已访问。
  2. 从第 22 个位置开始，依次尝试每个未访问的城市。
  3. 把选中城市加入路径，累加距离，递归进入下一层。
  4. 当所有城市都访问完，加上回到起点的距离，得到一条完整环游的总路程，更新最优解。
  5. 递归返回后，撤销选择（回溯），尝试下一个城市。
回溯核心口诀

做出选择 →\rightarrow 递归探索下一层 →\rightarrow 撤销选择（恢复现场）。

4.2 关键剪枝：代价超过当前最优即放弃#

纯排列树遍历是 O((n−1)!)O((n-1)!)，规模稍大就爆炸。最直接的剪枝是：

如果当前已经走过的距离 currentCost 加上下一步的距离，已经大于等于已知的最优解 bestCost，那么这条路再走下去只会更差，直接剪掉。

currentCost+d当前, 下一城市≥bestCost⇒剪枝\text{currentCost} + d_{\text{当前},\ \text{下一城市}} \ge \text{bestCost} \Rightarrow \text{剪枝}

这就是分支限界思想的雏形：用一个界来判断某个分支是否还有希望。

5. 以 4 个城市为例走一遍#

设 44 个城市 A、B、C、D（编号 0,1,2,30, 1, 2, 3），距离矩阵为：

      A    B    C    D
A     ∞   10   15   20
B    10    ∞   35   25
C    15   35    ∞   30
D    20   25   30    ∞

从 A（城市 00）出发，列出所有合法环游（共 3!=63! = 6 条，对称距离下成对相等）：

A→B→C→D→A：10 + 35 + 30 + 20 = 95
A→B→D→C→A：10 + 25 + 30 + 15 = 80   ← 最优
A→C→B→D→A：15 + 35 + 25 + 20 = 95
A→C→D→B→A：15 + 30 + 25 + 10 = 80   ← 最优（上一条的逆向）
A→D→B→C→A：20 + 25 + 35 + 15 = 95
A→D→C→B→A：20 + 30 + 35 + 10 = 95

最优总路程是 8080，对应路线 A→B→D→C→AA \rightarrow B \rightarrow D \rightarrow C \rightarrow A。

下面按代码中的 DFS 顺序演示搜索过程。bestCost 初始为 +∞+\infty。

第 1 步：固定起点 A，path = [A]。

第 2 步：选 B。

A → B   currentCost = 10

第 3 步：选 C。

A → B → C   currentCost = 10 + 35 = 45

第 4 步：只剩 D，选 D，回到 A。

A → B → C → D → A   总路程 = 45 + 30 + 20 = 95

得到一个解，bestCost = 95。回溯。

回到第 3 步：换成选 D。

A → B → D → C → A   总路程 = 10 + 25 + 30 + 15 = 80

80<9580 < 95，更新 bestCost = 80。回溯。

回到第 2 步：换成选 C。进入后：

A → C   currentCost = 15

继续尝试剩余城市。

  • 选 B：A → C → B 的 currentCost = 15 + 35 = 50，再选 D 并回到 A，总路程为 50 + 25 + 20 = 95，不更新。
  • 选 D：A → C → D 的 currentCost = 15 + 30 = 45，再选 B 并回到 A：
A → C → D → B → A   总路程 = 45 + 25 + 10 = 80

80=bestCost80 = \text{bestCost}，没有更优，不更新。

回到第 2 步：最后换成选 D。进入后 A → D 的 currentCost = 20。

  • 选 B：A → D → B 的 currentCost = 20 + 25 = 45。再尝试 C 时，nextCost = 45 + 35 = 80，已经不小于 bestCost = 80，剪枝。
  • 选 C：A → D → C 的 currentCost = 20 + 30 = 50。再尝试 B 时，nextCost = 50 + 35 = 85，也被剪枝。

搜索结束，最终最优解为 8080。

NOTE

第一次找到的解（这里 9595）会成为 bestCost。后续一旦某个部分路径的 nextCost >= bestCost，就可以提前放弃；当 bestCost 更新为 8080 后，剪枝会更强。

6. Java 实现（回溯法）#

public class TSPBacktracking {


    private static int n;
    private static int[][] dist;       // 距离矩阵
    private static boolean[] visited;  // 标记城市是否已访问
    private static int[] path;         // 当前路径
    private static int[] bestPath;     // 最优路径
    private static int currentCost;    // 当前已走距离
    private static int bestCost;       // 最优总路程


    public static int solve(int[][] matrix) {
        n = matrix.length;
        dist = matrix;
        visited = new boolean[n];
        // 第 n 个位置用于存放回到起点的城市
        path = new int[n + 1];
        bestPath = new int[n + 1];
        bestCost = Integer.MAX_VALUE;
        currentCost = 0;


        // 固定从城市 0 出发
        visited[0] = true;
        path[0] = 0;


        backtrack(1);
        return bestCost;
    }


    private static void backtrack(int index) {
        // 所有城市都已访问，加上回到起点的距离
        if (index == n) {
            int total = currentCost + dist[path[n - 1]][0];
            if (total < bestCost) {
                bestCost = total;
                path[n] = 0; // 回到起点
                System.arraycopy(path, 0, bestPath, 0, n + 1);
            }
            return;
        }


        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }


            // 剪枝：当前代价 + 这一步 已经不优于最优解，放弃
            int nextCost = currentCost + dist[path[index - 1]][i];
            if (nextCost >= bestCost) {
                continue;
            }


            // 做出选择
            visited[i] = true;
            path[index] = i;
            currentCost = nextCost;


            // 递归进入下一层
            backtrack(index + 1);


            // 撤销选择
            currentCost -= dist[path[index - 1]][i];
            visited[i] = false;
        }
    }


    public static void main(String[] args) {
        // 用 ∞ 表示不存在的边，这里城市 0..3 对应 A..D
        int INF = Integer.MAX_VALUE >> 1; // 取半是为了防止相加溢出
        int[][] matrix = {
            {INF,  10,  15,  20},
            { 10, INF,  35,  25},
            { 15,  35, INF,  30},
            { 20,  25,  30, INF}
        };


        int result = solve(matrix);


        System.out.println("最短路程：" + result);
        System.out.print("最优路线：");
        for (int i = 0; i <= n; i++) {
            System.out.print((char) ('A' + bestPath[i]));
            if (i != n) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }
}

运行结果：

最短路程：80
最优路线：A -> B -> D -> C -> A
INF 取值的注意点

代码里用 Integer.MAX_VALUE >> 1 表示无穷大，是为了防止两个 INF 相加时溢出变成负数，从而被误判为”更优”。处理带权图时这是常见的细节坑。

7. 复杂度分析（回溯法）#

  • 时间复杂度：最坏情况 O((n−1)!)O((n-1)!)。
  • 空间复杂度：O(n)O(n)，包括 path、bestPath、visited 数组和递归调用栈。

为什么是阶乘？因为排列树在第 11 层有 n−1n-1 个分支，第 22 层每个节点最多 n−2n-2 个分支，依次递减，叶子节点数为：

(n−1)×(n−2)×⋯×1=(n−1)!(n-1) \times (n-2) \times \cdots \times 1 = (n-1)!

实际运行中，“代价超过最优即剪枝”会砍掉大量分支，但最坏情况仍是阶乘级。对这类 NP-Hard 问题，精确算法通常需要配合更强的剪枝或状态压缩，才能把可处理规模向前推进。

8. 用下界剪枝：分支限界思想#

第 6 节的剪枝只用到了”当前已走距离”，这个界太松——它完全不考虑剩余城市还要花多少距离。分支限界法（Branch and Bound） 的核心是：给每个部分解估算一个更紧的下界，下界越大，越能提前剪枝。

8.1 什么是好的下界？#

下界必须满足：

下界≤从该部分解出发的任意完整环游的真实最短路程\text{下界} \le \text{从该部分解出发的任意完整环游的真实最短路程}

我们要找的是更短路线。

若某个分支的下界已经 ≥bestCost\ge \text{bestCost}，说明它再往下搜也不可能得到更短结果，可以直接剪掉。

8.2 矩阵归约法（经典下界）#

一种经典且较紧的下界来自距离矩阵归约（matrix reduction），思路是：

一条环游从每个城市出发一次，也到达一次。因此从距离矩阵每一行减去该行最小值、每一列减去该列最小值，所减掉的总量，是任何环游都必须至少付出的代价。

先用一个生活例子理解“下界”。

假设你要买 4 样东西，每样都必须买一次。你还不知道最后具体在哪家店买，但已经知道：

第 1 样东西最便宜也要 10 元
第 2 样东西最便宜也要 10 元
第 3 样东西最便宜也要 15 元
第 4 样东西最便宜也要 20 元

那你可以先得到一个肯定成立的结论：

总价至少是 10 + 10 + 15 + 20 = 55 元

最后真正花的钱可能是 80、95 或 120，但不可能低于 55。这个“至少要花 55 元”就是下界。

矩阵归约法在 TSP 里做的事情类似：虽然还不知道最终路线怎么走，但每个城市至少要选一条离开的边，也至少要选一条进入的边。于是可以先估算：无论最后怎么绕，这条环游至少要花多少钱。

具体步骤：

  1. 行归约：每一行减去本行最小元素，记录所有行最小值之和 r1r_1。
  2. 列归约：对行归约后的矩阵，每一列减去本列最小元素，记录所有列最小值之和 r2r_2。
  3. 下界：
下界=r1+r2\text{下界} = r_1 + r_2

为什么这是合法下界？因为环游在每一行恰好选一个元素（从该城市出发的一条边），在每一列也恰好选一个元素（到达该城市的一条边）。每行至少贡献行最小值，每列至少贡献列最小值，所以减掉的总量是任何环游的下界。

8.3 用同一个例子算下界#

原始矩阵：

      A    B    C    D
A     ∞   10   15   20
B    10    ∞   35   25
C    15   35    ∞   30
D    20   25   30    ∞

第一步：行归约。 各行最小值为 10, 10, 15, 2010,\ 10,\ 15,\ 20，和为 r1=55r_1 = 55。每行减去最小值：

      A    B    C    D
A     ∞    0    5   10
B     0    ∞   25   15
C     0   20    ∞   15
D     0    5   10    ∞

第二步：列归约。 各列最小值为 0, 0, 5, 100,\ 0,\ 5,\ 10，需要减的只有 C 列（减 55）和 D 列（减 1010），和为 r2=15r_2 = 15。归约后：

      A    B    C    D
A     ∞    0    0    0
B     0    ∞   20    5
C     0   20    ∞    5
D     0    0    5    ∞

下界：

下界=r1+r2=55+15=70\text{下界} = r_1 + r_2 = 55 + 15 = 70

而本例最优解是 8080，70≤8070 \le 80，下界成立。

下界越紧，剪枝越强

朴素剪枝只看当前已走距离 currentCost，相当于把“剩下还要走的路”估成 00。这个估计一定安全，但太乐观。

矩阵归约会给剩余部分也估一个“至少还要花多少”的下界。把它加到 currentCost 上，就能得到更接近真实总路程的判断：

当前已走距离+剩余部分下界\text{当前已走距离} + \text{剩余部分下界}

如果这个值已经不小于 bestCost，说明这条分支就算后面每一步都走得很理想，也不可能超过当前最优解，可以提前剪掉。

8.4 在搜索中维护下界#

实际搜索时，每个节点都要回答一个问题：

我已经走到这里了，如果把剩下的路用最乐观的方式估一下，这条分支还有机会超过当前最优解吗？

例如现在已经找到一条完整路线，bestCost = 80。搜索到某个部分路径时：

A → D
currentCost = 20

如果用矩阵归约估出“剩下的城市至少还要花 65”，那么这条分支的乐观总成本就是：

20 + 65 = 85

由于 85≥8085 \ge 80，即使后面每一步都按最理想情况走，也不可能得到更短路线，所以这整个分支可以直接剪掉。

维护这个下界时，每选定一条边（比如确定 A→BA \rightarrow B），就把对应行和列从矩阵中划掉，并对剩余子矩阵重新归约，更新下界增量。这样每个搜索节点都有一个反映“已确定路径 + 剩余最乐观估计”的下界。

完整的优先队列式分支限界会把这些搜索节点放进堆里，每次优先扩展下界最小、最有希望的节点。它效果更好，但实现也更复杂。本文的回溯代码已经展示了“界 + 剪枝”的核心思想：把简单的 currentCost 剪枝换成“当前成本 + 剩余下界”剪枝，就进入了分支限界法的思路。

9. 其他常见方法概览#

TSP 是个研究了几十年的问题，精确法和近似/启发式方法都很多。

方法类型时间复杂度特点
回溯法精确O((n−1)!)O((n-1)!)实现简单，适合小规模
分支限界法精确最坏仍指数级下界紧，剪枝强，常用于中等规模
动态规划（Held-Karp）精确O(n2⋅2n)O(n^2 \cdot 2^n)用状态压缩，n≤20n \le 20 左右可行
最近邻等贪心法近似O(n2)O(n^2)快但不保证最优，可作为初始解
模拟退火 / 遗传算法 / 蚁群启发式依赖迭代次数大规模近似求解，结果不稳定
Held-Karp 动态规划

用 dp[S][j]dp[S][j] 表示已访问城市集合为 SS、当前位于城市 jj 的最短距离。状态数为 O(n⋅2n)O(n \cdot 2^n)，转移 O(n)O(n)，总复杂度 O(n2⋅2n)O(n^2 \cdot 2^n)。它把阶乘级降到了指数级，是精确解法里最快的之一，但 nn 一旦超过 2020 也很难承受。

选择哪种方法，取决于问题规模和精度要求：

  • n≤10n \le 10：回溯法足矣。
  • n≤20n \le 20：动态规划 Held-Karp。
  • n≤50n \le 50 左右：分支限界（下界要设计得好）。
  • nn 更大：近似算法或元启发式算法。

10. 总结#

旅行售货员问题的核心可以概括为：

在排列树上搜索所有环游，用下界剪掉无望分支，找到总路程最短的回路。

核心内容如下：

  • TSP 的解空间是排列树，固定起点后方案数上界为 (n−1)!(n-1)!。
  • 回溯法通过”做出选择 → 递归 → 撤销选择”遍历排列树。
  • 最朴素的剪枝：当前已走距离 ≥\ge 已知最优，即剪掉。
  • 分支限界法用更紧的下界（如矩阵归约）替代朴素界，剪枝更强。
  • TSP 是 NP-Hard 问题，精确算法都是指数级以上，大规模只能靠近似。

口诀：

固定起点排顺序，回溯遍历排列树；代价超界即剪枝，归约下界更强力。

分享

如果这篇文章对你有帮助，欢迎分享给更多人！

旅行售货员问题（回溯法与分支限界法）
https://dawn114514.site/posts/algorithm/travelingsalesman/
作者
黎明
发布于
2026-06-15 10:10:02
许可协议
MIT

部分信息可能已经过时

最短等待时间（加工顺序问题）
N 皇后
相关文章 智能推荐
1
0-1 背包问题（动态规划、回溯法、分支限界法）
Algorithm 从决策树到分支限界，三种视角求解 0-1 背包：动态规划求最优值，回溯法与分支限界用上界剪枝。
2
素数环问题（回溯法）
Algorithm 通过回溯法解决素数环问题，理解排列树、剪枝、奇偶性约束与素数判定。
3
最大流问题与 Edmonds-Karp 算法
Algorithm 从贪心找路失败出发，引出反向边的纠错机制，形式化残量网络与增广路，用 BFS 实现标号法并反复推流，直到残量网络中源汇不再连通。
4
第二大元素问题
Algorithm 从两种题型出发，介绍一次遍历和分治两种解法，重点讲清分治合并时的候选淘汰思想。
5
N 皇后
Algorithm 经典回溯问题：N 皇后的图解与详细解析，深入理解深度优先搜索中状态重置的本质。
随机文章 随机推荐
1
快速幂
Algorithm 2026-06-10
2
链表：合并两个有序链表
Algorithm 2026-05-11
3
最短等待时间（加工顺序问题）
Algorithm 2026-06-15
4
堆排序
Algorithm 2026-06-09
5
算法学习
Algorithm 2026-04-28
豫ICP备2026007336号 萌ICP备20266900号
© 2026 黎明. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录