TSP问题-分支限界法求解

TSP问题-分支限界法求解

TSP（旅行商）问题是一个经典的组合优化问题，其目标是在给定的城市集合中找到一条最短的巡回路线。本文将详细介绍如何使用分支限界法求解TSP问题，包括问题定义、算法设计、代价函数、搜索树结构、实例运行过程和算法分析等内容。

1. 货郎问题的分支限界算法求解

1.1. 货郎问题的定义

• 给定一个城市集合(C = {c_1, c_2, \dots, c_n})，任何两个城市之间都有距离(d\left(c_i, c_j\right)=d\left(c_j, c_i\right) \in \mathbf{Z}^{+}, 1 \leq i<j \leq n)。
• 目标：找到一个城市的排列，使得从一个城市出发，访问每个城市恰好一次，并返回出发城市，总路径长度最短。

1.2. 算法设计

• 解向量：
  解:(1,2, \ldots, n)的排列(k_1, k_2, \ldots, k_n)使得:
  [\min \left{\sum_{i=1}^{n-1} d\left(c_{k_i}, c_{k_{i+1}}\right)+d\left(c_{k_n}, c_{k_1}\right)\right} ]

• 搜索空间：
  排列树结构，每个结点(\langle i_1, i_2, \dots, i_k \rangle)表示前(k)步的路线已确定。

• 约束条件：

• 已走过的城市标号放入集合(B = {i_1, i_2, \dots, i_k})。

• 下一步只能选择未访问过的城市：(i_{k+1} \in {2, \dots, n} \setminus B)。

• 即每个节点只能访问一次

1.3. 代价函数与界的定义

• 界 (Bound)：当前已找到的最短巡回路线的长度。

• 代价函数：
  假设顶点(c_i)出发的最短边为(l_i)，(d_j)为已选定的巡回路线中第(j)段的长度，则代价函数为：
  [\boldsymbol{L}=\sum_{j=1}^k \boldsymbol{d}j+\boldsymbol{l}{i_k}+\sum_{i_i \notin B} \boldsymbol{l}_{i_j} ]

• 前半部分：已走过的路径长度。

• 后半部分：剩余未访问的城市，从每个城市出发的最短边构成的下界。

1.4. 代价函数示例

我们通过一个具体路径的代价函数计算示例，来更好理解分支限界算法中如何评估路径的代价和下界。

示例路径及红色路径描述

如图所示，我们假设货郎从1号城市出发，依次访问了3号城市和2号城市，形成了部分路径(\langle 1, 3, 2 \rangle)。现在我们已经走到2号城市，接下来需要计算该路径的代价函数，来评估当前路径的花费以及剩余部分的下界。

代价函数的计算公式

代价函数(L)的通用表达式如下：
[L = \text{已走过的路径长度} + \text{剩余部分的估计长度下界} ]

• 已走过的路径长度：
  将已访问的城市之间的路径距离累加，例如在路径(\langle 1, 3, 2 \rangle)中，
  [1 \to 3：9 ,, (单位) ]
  [3 \to 2：13 ,, (单位) ]
  已走过的路径总长度为：
  [9 + 13 = 22 ,, (单位) ]

• 剩余部分的估计长度下界：

• 当前停留在2号城市，我们需要从2号城市出发选择一条最短边。
  2号城市的最短边是(2 \to 4)，边长为(2)。

• 在剩余的未访问城市中，还未访问的城市是4号城市。从4号城市出发的最短边也是(4 \to 2)，长度同样为(2)。
  因此，剩余部分的估计长度下界为：
  [2 + 2 = 4 ,, (单位) ]

完整代价函数值计算

将已走过的路径长度和剩余部分的下界相加，得到代价函数的值：
[L = 22 + 4 = 26 ,, (单位) ]

下界解释

这个代价函数的结果表明，无论之后如何规划剩余的路径，完整路径的总长度不会小于 26。这个下界帮助算法在搜索时进行剪枝，即当其他路径的代价超过该下界时，就不再继续深入搜索该分支。

1.5. 搜索树结构

• 初始结点：从城市 1 出发。

• 可选路径：

• 第一层：1 号城市之后可以去 2、3、4。

• 第二层：假设选择了 2 号城市，则下一步可选 3 或 4。

• 深度优先遍历：

• 第一条路径：(\langle 1, 2, 3, 4, 1 \rangle)，长度(29)。

• 这是第一个找到的巡回路线，界(B = 29)。

• 更新界：
  找到路径(\langle 1, 2, 4, 3, 1 \rangle)，长度(23)。更新界(B = 23)。

• 剪枝：
  当搜索路径(\langle 1, 3, 2 \rangle)的代价函数值为(26)，大于当前界(B = 23)，停止搜索该分支。

1.6. 实例运行过程

2. 初始路径：

• 路径(\langle 1, 2, 3, 4, 1 \rangle)，长度为(29)。

4. 更新路径：

• 找到更优路径(\langle 1, 2, 4, 3, 1 \rangle)，长度为(23)，更新界。

6. 剪枝：

• 代价函数值(F = 26)，停止该分支的搜索。

8. 最优解：

• 找到路径(\langle 1, 3, 4, 2, 1 \rangle)，长度(23)。
• 该路径与之前的最优解长度相同。

1.7. 算法分析

• 搜索树的规模：

• 树叶的个数为(O((n - 1)!))。

• 每个叶片对应一条路径，每条路径有(n)个结点。

• 时间复杂度：

• 单个路径计算时间：(O(n))。

• 总时间复杂度：(O(n!))。

• 在最坏情况下，与蛮力算法的时间复杂度相同。

• 实际性能：
  通过剪枝操作，大大减少了实际搜索空间，因此平均运行时间优于蛮力算法。

1.8. 小结

• 货郎问题的分支限界算法：

• 约束条件：只能选择未访问过的城市。

• 代价函数：已走过的路径长度 + 未访问部分的长度下界。

• 时间复杂度：(O(n!))，在最坏情况下与蛮力算法相同，但通过剪枝可显著提升平均性能。