# 分支限界法实战：用Python解决旅行商问题（TSP）的完整代码与优化技巧 如果你对算法竞赛或者组合优化问题有过接触，那么“旅行商问题”这个名字一定不会陌生。它就像一个经典的试金石，检验着我们对算法效率与优雅的理解深度。很多朋友在学习了回溯法、动态规划后，初次面对TSP时，往往会被其阶乘级的解空间所震撼——5个城市有120条路径，10个城市就飙升到360万条以上。当回溯法在20个城市面前显得力不从心时，我们迫切需要一种更“聪明”的搜索策略。这就是**分支限界法**大显身手的舞台。它不是简单地枚举所有可能，而是像一个经验丰富的向导，在探索解空间的巨大迷宫时，手里始终握着一张“潜力地图”，能果断放弃那些注定没有前途的岔路。本文将带你从零开始，用Python亲手实现一个高效的分支限界法求解TSP，并深入探讨那些能让代码性能提升数倍的优化技巧。无论你是准备算法面试，还是希望在项目中处理实际的路径规划问题，这里都有你需要的实战干货。 ## 1. 理解核心：为什么是分支限界法？ 在深入代码之前，我们必须厘清一个根本问题：面对NP-hard的旅行商问题，为什么分支限界法是一个值得投入的选项？回溯法同样能求出精确解，但其盲目的深度优先搜索，在遇到糟糕的路径分支时，会浪费大量时间在明显劣于当前最优解的路径上。动态规划（如Held-Karp算法）虽然将复杂度降到了O(n²2ⁿ)，但对于稍大规模的问题（例如n>20），其所需的内存空间（2ⁿ量级）可能成为瓶颈。 分支限界法的核心思想是 **“智能剪枝”** 。它采用广度优先或最佳优先的策略来搜索解空间树（对于TSP，这是一棵排列树）。每个树节点代表一个部分解（例如，已经确定了前k个访问城市的路径）。算法的关键在于为每个节点计算一个**代价下界**。这个下界是对“从该部分解出发，完成整个回路所需的最小可能代价”的一个乐观估计。 > **提示**：下界的估计越紧（即越接近真实的最小可能值），剪枝的效果就越好，算法效率就越高。设计一个高质量的下界函数，是分支限界法性能优劣的决定性因素。 算法维护一个优先队列（通常是最小堆），总是优先扩展当前**下界最小**的节点。为什么？因为下界最小的节点，最有可能最终扩展出全局最优解。同时，算法还维护一个**当前找到的最优解的成本上界**。在扩展节点时，如果发现某个节点的下界已经**大于或等于**当前最优解的成本，那么以该节点为根的整个子树都可以被安全地剪掉——因为这片子树里不可能产生比现有解更好的解了。 这个过程就像搜索宝藏： 1. 你有一张藏宝图（解空间），但不知道宝藏（最优解）具体在哪。 2. 你派出一队探险家（优先队列中的节点），每位探险家对自己所在区域宝藏的价值有一个最低预估（下界）。 3. 你手上已经有一个找到的宝藏（当前最优解），知道它的价值。 4. 你总是派那个预估价值最低的探险家去深入探索（扩展节点）。 5. 如果某个探险家出发前，他的最低预估就已经比你手上的宝藏价值还高，那你肯定不会派他去（剪枝）。 6. 当有探险家真的找到了一个新宝藏，并且比手上的更好，你就更新你手上的宝藏。 7. 最终，当所有潜在的、预估价值低于手上宝藏的区域都被探索完毕，你手上的就是最好的宝藏。 与回溯法的对比，我们可以用一个简单的表格来清晰展示： | 特性维度 | 回溯法 (Backtracking) | 分支限界法 (Branch and Bound) | | :--- | :--- | :--- | | **搜索策略** | 深度优先搜索 (DFS) | 广度优先或最佳优先搜索 (常使用优先队列) | | **节点扩展顺序** | 固定顺序（如字典序），与节点质量无关 | 根据节点的“潜力”（下界）动态决定，优先扩展最有希望的节点 | | **剪枝依据** | 约束条件（可行性） | 约束条件 + 限界函数（最优性） | | **内存占用** | 相对较小（栈深度为O(n)） | 较大（需要存储整个活节点队列） | | **找到第一个解的速度** | 可能较快（如果运气好） | 通常较慢（需要系统性地评估潜力） | | **证明找到最优解** | 必须遍历所有未被剪枝的路径 | 当优先队列中所有节点的下界 >= 当前最优解时，即可终止 | | **适用场景** | 解空间相对较小，或侧重于找到任意可行解 | 解空间巨大，且明确要求找到**代价最小/最大**的精确最优解 | 从表中可以看出，分支限界法通过引入“代价下界”和“优先队列”，将搜索的“蛮力”成分降到了最低，特别适合求解像TSP这类最优化问题。 ## 2. 构建基石：TSP的数据结构与下界函数 理论清晰后，我们开始动手。首先，需要定义问题的输入。旅行商问题通常用一个代价矩阵（距离矩阵）来表示。 ```python import heapq import math import sys from typing import List, Tuple, Optional class TSPSolver: def __init__(self, distance_matrix: List[List[float]]): """ 初始化求解器。 :param distance_matrix: 一个 n x n 的方阵，dist[i][j] 表示从城市 i 到城市 j 的代价。 对角线元素 dist[i][i] 应为 0。 """ self.n = len(distance_matrix) self.dist = distance_matrix # 预处理：计算每个城市的最小出边和次小出边，用于优化下界计算 self.min_out = [0] * self.n self.second_min_out = [0] * self.n self._precompute_min_edges() ``` 这里我们选择将算法封装在一个类中。预处理函数 `_precompute_min_edges()` 非常关键，它能为后续高效计算下界打下基础。 ```python def _precompute_min_edges(self): """预处理，计算每个城市出发的最小和次小出边代价。""" for i in range(self.n): edges = [self.dist[i][j] for j in range(self.n) if i != j] edges.sort() self.min_out[i] = edges[0] if len(edges) > 1: self.second_min_out[i] = edges[1] else: self.second_min_out[i] = 0 # 实际上对于n>=2的城市不会发生 ``` 接下来是算法的灵魂——**下界函数**。一个简单而有效的下界计算方法是：对于一条部分路径，其已完成部分的代价是确定的。对于剩余未访问的城市（包括起点），要形成一条哈密顿回路，每个城市都**至少**需要一条进入边和一条离开边。因此，一个乐观的估计是：已确定代价 + 所有未访问城市（及起点）的**最小出边代价之和**的一半（因为每条边会被两个城市各计算一次，更严谨的做法是下面介绍的1-tree松弛法）。 我们采用一种更紧的下界估计，它基于最小生成树的思想，被称为 **“归约矩阵”法** 或 **“Held-Karp下界”的简化版本**。其步骤如下： 1. **归约行**：对代价矩阵的每一行，减去该行的最小值。这个最小值代表“访问该城市至少需要付出的代价”。 2. **归约列**：对归约后的矩阵的每一列，减去该列的最小值。这个最小值代表“从其他城市到达该城市至少需要付出的代价”。 3. **归约常数**：所有行归约值和列归约值之和，就是当前矩阵的一个有效下界。 4. **结合部分路径**：对于已经固定的边（如从起点出发，或路径中已确定的顺序），将其代价加上，并将对应行/列从后续归约中排除。 为了在分支限界中高效计算，我们使用一种增量式计算下界的方法。下面是一个计算节点下界的核心函数： ```python def _calculate_lower_bound(self, path: List[int], path_cost: float) -> float: """ 计算给定部分路径的下界。 :param path: 已经访问过的城市顺序列表，path[0]是起点。 :param path_cost: 当前路径的实际代价。 :return: 从当前状态出发完成回路的最小可能代价下界。 """ if len(path) == self.n: # 路径已满，只需加上返回起点的代价 return path_cost + self.dist[path[-1]][path[0]] # 方法：使用最小出边/入边之和的1/2作为剩余代价的乐观估计 # 这是一种快速但相对宽松的下界，后续我们会实现更紧的下界。 bound = path_cost visited = set(path) # 对于已路径中的最后一个城市，它的出边已经固定（去下一个城市）， # 但入边可能还未固定。对于起点，它的入边（返回）也未固定。 # 我们简单地为每个未访问城市（包括起点，如果它不在路径末尾）加上其最小出边。 for city in range(self.n): if city not in visited: bound += self.min_out[city] elif city == path[0] and path[-1] != path[0]: # 起点已被访问，但回路还未闭合，需要考虑返回起点的边 # 这里我们保守地加上起点最小出边（实际上可能不是返回边） bound += self.min_out[city] # 每条边被计算了两次（一次作为起点的出边，一次作为终点的入边），除以2 bound /= 2.0 return bound ``` 这个下界函数计算速度快，但不够紧致。在实际的高性能实现中，往往会采用基于**最小1-tree**的下界，它是Held-Karp下界的核心组成部分，效果要好得多。由于实现稍复杂，我们将在优化章节详细讨论其实现。 ## 3. 核心实现：优先队列与节点状态管理 有了下界函数，我们就可以定义搜索过程中的节点状态。每个节点需要记录：当前路径、路径实际代价、下界值。我们使用Python的`heapq`模块来实现最小优先队列。 ```python class Node: """表示搜索树中的一个节点。""" __slots__ = ('path', 'cost', 'bound', 'visited_mask') # 使用__slots__节省内存 def __init__(self, path: List[int], cost: float, bound: float): self.path = path[:] # 复制路径，避免后续修改影响父节点 self.cost = cost self.bound = bound # 使用位掩码快速判断城市是否被访问，对于n<=30左右很高效 self.visited_mask = 0 for city in path: self.visited_mask |= (1 << city) def __lt__(self, other): # 为了放入最小堆，定义比较规则：下界小的节点优先级更高 return self.bound < other.bound ``` > **注意**：在TSP中，城市数量n常常是性能的关键。当n较大时，存储完整的`path`列表会占用较多内存。使用位掩码`visited_mask`是一个常见的优化，它可以快速进行集合成员判断和复制，但这里我们为了代码清晰，同时保留了路径列表。在实际处理大规模问题时，可能需要更精细的内存管理。 现在，我们可以构建分支限界法的主循环了。 ```python def solve(self) -> Tuple[Optional[List[int]], float]: """ 使用分支限界法求解TSP。 :return: (最优路径, 最优代价)。如果无解，返回(None, inf)。 """ if self.n < 2: return ([0], 0) if self.n == 1 else (None, float('inf')) best_cost = float('inf') best_path = None # 初始化根节点：从城市0出发 root_bound = self._calculate_lower_bound([0], 0) # 优先队列，元素为 (bound, node)。heapq按元组第一个元素排序 pq = [] heapq.heappush(pq, (root_bound, Node(path=[0], cost=0, bound=root_bound))) while pq: _, current_node = heapq.heappop(pq) # 剪枝：如果当前节点的下界已经差于已知最优解，跳过 if current_node.bound >= best_cost: continue current_path = current_node.path current_cost = current_node.cost last_city = current_path[-1] # 如果路径包含了所有城市，形成一个候选解 if len(current_path) == self.n: total_cost = current_cost + self.dist[last_city][current_path[0]] if total_cost < best_cost: best_cost = total_cost best_path = current_path[:] continue # 扩展当前节点：尝试所有未访问的城市作为下一个目的地 for next_city in range(self.n): if current_node.visited_mask & (1 << next_city): continue # 城市已访问 new_path = current_path + [next_city] new_cost = current_cost + self.dist[last_city][next_city] new_bound = self._calculate_lower_bound(new_path, new_cost) # 只有当下界有可能优于当前最优解时，才创建子节点 if new_bound < best_cost: child_node = Node(path=new_path, cost=new_cost, bound=new_bound) heapq.heappush(pq, (new_bound, child_node)) return best_path, best_cost ``` 主循环的逻辑清晰体现了分支限界法的框架： 1. 从优先队列中取出下界最小的节点。 2. 进行最优性剪枝：如果该节点的下界已不低于当前最优解，则丢弃该节点及其所有子节点（因为队列是最小堆，后续节点的下界只会更大）。 3. 如果该节点代表一个完整路径（访问了所有城市），则计算回路总成本，并尝试更新最优解。 4. 否则，生成该节点的所有可行子节点（即访问下一个未访问的城市），计算子节点的实际代价和下界。 5. 对于每个子节点，如果其下界小于当前最优解，说明它所在的子树可能包含更优解，将其加入优先队列。 这个基础版本已经可以正确求解小规模的TSP实例。但是，它的效率还有巨大的提升空间。接下来，我们将进入**优化技巧**的深水区。 ## 4. 性能飞跃：关键优化技巧详解 要让分支限界法真正能处理数十个城市的TSP实例，我们必须引入一系列优化。这些优化从不同角度削减搜索空间，提升下界质量，降低内存开销。 ### 4.1 采用更紧的下界：最小1-Tree松弛 前面使用的“最小出边和的一半”下界过于宽松，导致剪枝能力弱。**最小1-tree**是 Held-Karp 算法中计算下界的核心工具，它能提供紧致得多的下界。 1-tree的定义是：对于一个图，先取出一个特定的节点（通常记为节点0），然后构造一个包含所有节点的生成树，**再加上两条与节点0相连的边**。对于TSP，一个哈密顿回路必然是一个1-tree（因为回路去掉一条与节点0相连的边，就是一棵生成树）。因此，**所有1-tree的最小代价，一定是TSP最优解代价的一个下界**。 计算最小1-tree的代价非常高效（接近O(n²)）： 1. 忽略节点0，在剩余的n-1个节点上计算最小生成树（MST）的代价。 2. 找到连接节点0的最短两条边，将其代价加入MST代价。 这个值就是当前代价矩阵的一个下界。更妙的是，我们可以通过**归约**技术来进一步提升这个下界，并引导分支决策。归约过程会产生一个“惩罚值”向量（π），作用于每个城市，调整边的代价，使得下界不断提高。这构成了Held-Karp算法的核心。在我们的分支限界法中，可以周期性地或在关键节点使用这种技术来获得极强的下界。 下面是一个简化版的、在节点扩展时使用的增强下界计算函数： ```python def _calculate_lower_bound_advanced(self, path: List[int], path_cost: float) -> float: """ 使用最小生成树思想计算更紧的下界（简化版）。 思路：已确定的路径可以看作是一个子图。剩余部分至少需要一棵连接所有未访问城市（及起点）的最小生成树。 同时，每个节点的度数在最终回路中必须为2，我们可以利用这个条件进行额外的惩罚估计。 """ if len(path) == self.n: return path_cost + self.dist[path[-1]][path[0]] visited = set(path) # 对于已固定的边（路径中的连续城市），其代价已计入path_cost。 # 我们需要估计连接所有节点（形成一个回路）所需的最小额外代价。 # 简化版：计算未访问城市（包括起点，如果它不在路径末尾）构成的最小生成树代价。 # 然后，考虑起点和路径末端城市与这个MST的连接。 unvisited_cities = [c for c in range(self.n) if c not in visited] if not unvisited_cities: # 只剩下返回起点的边 return path_cost + self.dist[path[-1]][path[0]] # 这里为了示例清晰，我们使用一个简单的估计： # 额外代价 >= 连接所有未访问城市所需MST的代价 + 连接MST到路径两端所需的最小边代价。 # 实际上，精确计算这个下界需要更复杂的逻辑（如寻找最小1-tree）。 # 作为一个强化的例子，我们使用每个未访问城市的两条最小边之和的一半。 # 这是一个比简单最小出边和更紧的下界，因为它考虑了每个城市需要两条边。 extra_bound = 0 for city in unvisited_cities: # 获取该城市最小的两条边（排除自环） edges = [self.dist[city][j] for j in range(self.n) if j != city] edges.sort() extra_bound += (edges[0] + edges[1]) extra_bound /= 2.0 # 还需要考虑如何将未访问部分与已访问路径连接。 # 路径的末端城市`last`需要一条边进入未访问部分，起点`first`需要一条边从未访问部分返回。 last_city = path[-1] first_city = path[0] # 找到从last_city到未访问集合的最小边 min_edge_from_last = min((self.dist[last_city][c] for c in unvisited_cities), default=0) # 找到从未访问集合到first_city的最小边 min_edge_to_first = min((self.dist[c][first_city] for c in unvisited_cities), default=0) # 注意：上面的extra_bound已经包含了未访问城市之间的连接，以及它们各自的两条边。 # 但last_city和first_city的边可能已经被重复计算或未计算。这里是一个近似处理。 # 一个更严谨的实现需要避免重复计算，这涉及到复杂的度约束最小生成树问题。 # 此处我们采用一个近似值：extra_bound + 连接路径两端的最小边代价。 bound = path_cost + extra_bound + min_edge_from_last + min_edge_to_first # 由于近似可能重复计算，这个bound可能比真实下界大，但作为示例展示思路。 return bound ``` 在实际的最高效实现中（如Concorde TSP求解器），会使用基于**归约代价矩阵的最小1-tree**下界，并配合**子树消除**和**分支决策**，这需要实现完整的Held-Karp算法作为子过程，代码量会大很多。但即使使用上述的增强版下界，也能显著提升基础版本的性能。 ### 4.2 启发式初始解：快速获得一个优质上界 在分支限界法中，**当前最优解的值（上界）** 至关重要。一个越小的上界，意味着可以越早、越频繁地进行剪枝。如果我们一开始就有一个很好的解（例如用贪心算法或最近邻法得到的），那么搜索过程会大大加速。 ```python def _get_initial_upper_bound(self) -> Tuple[List[int], float]: """使用最近邻贪心算法获取一个初始解，作为最优代价的上界。""" start_city = 0 visited = [False] * self.n path = [start_city] visited[start_city] = True total_cost = 0 current = start_city for _ in range(self.n - 1): # 找到离当前城市最近的未访问城市 next_city = -1 min_dist = float('inf') for city in range(self.n): if not visited[city] and self.dist[current][city] < min_dist: min_dist = self.dist[current][city] next_city = city path.append(next_city) visited[next_city] = True total_cost += min_dist current = next_city # 返回起点，形成回路 total_cost += self.dist[path[-1]][path[0]] return path, total_cost ``` 在主函数开始时，调用此方法获取`best_cost`和`best_path`的初始值，可以立即排除大量劣质分支。 ### 4.3 状态压缩与对称性破缺 **状态压缩**：对于城市数量n不超过64（在64位系统上）的情况，使用位掩码（bitmask）来表示访问集合是最高效的方式，比使用Python的`set`或`list`快得多。我们在`Node`类中已经使用了`visited_mask`。 **对称性破缺**：在TSP中，由于回路是循环的，路径`[0,1,2,3]`和`[1,2,3,0]`代表的是同一条回路。为了避免重复搜索，我们可以固定起点为城市0。这并不会丢失任何最优解，因为总可以通过旋转将任意起点为0的回路对应起来。这能将解空间直接减少n倍。 ### 4.4 使用更高效的数据结构 Python的`heapq`对于存储大量节点可能成为瓶颈，因为每个节点都是一个包含列表等对象的复杂结构。对于超大规模问题，可以考虑： - 使用`array`或`numpy`数组来扁平化存储节点数据。 - 实现自定义的、基于数组的优先队列。 - 在C/C++扩展中实现核心算法，用Python做胶水层。许多顶尖的TSP求解器（如Concorde）的核心都是C语言库。 ### 4.5 迭代加深与局部搜索结合 纯精确算法对于大规模TSP（如1000个城市）仍然是不现实的。在实际应用中，常常采用**混合策略**： 1. 使用**Lin-Kernighan**等启发式算法快速得到一个非常接近最优的解。 2. 将这个解的成本作为分支限界法的初始上界。 3. 分支限界法专注于证明最优性，或者在有限时间内寻找比当前解更好的解。 这种“启发式+精确”的混合方法，在学术和工业界的求解器中非常常见。 ## 5. 可视化与调试：让算法过程一目了然 理解算法如何工作，可视化是最有力的工具。我们可以用`matplotlib`来绘制搜索过程和最终路径。 ```python import matplotlib.pyplot as plt def plot_cities(coords, path=None, title="TSP Cities"): """绘制城市坐标和路径（如果提供）。""" x = [c[0] for c in coords] y = [c[1] for c in coords] plt.figure(figsize=(10, 6)) plt.scatter(x, y, c='red', s=100, zorder=5) for i, (xi, yi) in enumerate(coords): plt.text(xi, yi, f'{i}', fontsize=12, ha='center', va='center', zorder=6) if path: # 闭合路径 path_x = [coords[i][0] for i in path] + [coords[path[0]][0]] path_y = [coords[i][1] for i in path] + [coords[path[0]][1]] plt.plot(path_x, path_y, 'b-', linewidth=1.5, alpha=0.6, zorder=4) plt.title(f"{title} - Path length: {calculate_path_length(coords, path):.2f}") else: plt.title(title) plt.xlabel("X") plt.ylabel("Y") plt.grid(True, alpha=0.3) plt.axis('equal') plt.show() def calculate_path_length(coords, path): """计算给定路径（城市索引列表）的总长度。""" total = 0 for i in range(len(path)): x1, y1 = coords[path[i]] x2, y2 = coords[path[(i+1)%len(path)]] total += math.hypot(x2-x1, y2-y1) return total # 示例：生成随机城市并求解 def random_tsp_instance(n_cities=10, seed=42): import random random.seed(seed) coords = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(n_cities)] # 计算欧氏距离矩阵 dist = [[0]*n_cities for _ in range(n_cities)] for i in range(n_cities): for j in range(i+1, n_cities): d = math.hypot(coords[i][0]-coords[j][0], coords[i][1]-coords[j][1]) dist[i][j] = d dist[j][i] = d return coords, dist # 主程序示例 if __name__ == "__main__": n = 12 # 城市数量，12个城市对于基础分支限界法在可接受时间内 city_coords, dist_matrix = random_tsp_instance(n) plot_cities(city_coords, title=f"Random TSP Instance (n={n})") solver = TSPSolver(dist_matrix) # 获取初始上界 init_path, init_cost = solver._get_initial_upper_bound() print(f"Initial greedy solution cost: {init_cost:.2f}") plot_cities(city_coords, init_path, "Initial Greedy Solution") # 使用改进的下界函数（需要替换到solver类中） # solver._calculate_lower_bound = solver._calculate_lower_bound_advanced best_path, best_cost = solver.solve() if best_path: print(f"Optimal path found: {best_path}") print(f"Optimal cost: {best_cost:.2f}") plot_cities(city_coords, best_path, "Optimal Solution (Branch and Bound)") else: print("No solution found.") ``` 可视化不仅帮助我们验证结果，在调试算法时，观察优先队列的大小变化、下界的收敛情况，也能直观地判断剪枝策略是否有效。 ## 6. 从理论到实践：处理真实世界数据的挑战 当你将上面的代码应用于教科书上的对称TSP时，它可能工作良好。但现实世界的数据会带来新的挑战： 1. **非对称TSP**：城市i到j和j到i的距离可能不同。我们的代码假设距离矩阵是对称的。处理非对称TSP需要调整下界函数，例如分别计算行的最小出边和列的最小入边。 2. **大规模数据**：对于成千上万个城市，精确算法不再可行。此时需要转向启发式算法（如模拟退火、遗传算法、蚁群算法）或使用专业的TSP求解器（如Concorde，它内部使用了复杂的割平面法和分支定界法）。 3. **动态约束**：真实的物流路径规划可能包含时间窗口、载重限制、多车辆等约束。这变成了车辆路径问题，需要在分支限界框架内加入复杂的可行性判断。 4. **浮点精度**：使用浮点数表示距离时，比较`new_bound < best_cost`可能会因精度问题导致错误剪枝。一个常见的做法是引入一个很小的容差epsilon。 一个处理非对称TSP下界的简单修改示例如下： ```python def _calculate_lower_bound_asymmetric(self, path, path_cost): """针对非对称TSP的下界计算（简化版）。""" visited = set(path) bound = path_cost # 对于每个未访问城市，至少需要一条进入边和一条离开边 for city in range(self.n): if city not in visited: # 最小出边 min_out = min((self.dist[city][j] for j in range(self.n) if j != city), default=0) # 最小入边 min_in = min((self.dist[j][city] for j in range(self.n) if j != city), default=0) bound += (min_out + min_in) / 2.0 # 对于路径中的首尾城市，其部分边已固定，需要更精细的调整，此处省略 return bound ``` 最后，我想分享一点在实现和调试分支限界法时的个人体会。最耗时的部分往往不是算法逻辑本身，而是**下界函数的质量**和**数据结构的选择**。我曾在一个项目中，仅仅将下界函数从简单的出边和改为基于MST的估计，就将一个20城市TSP的求解时间从几分钟缩短到了几秒钟。同时，对于超过15个城市的问题，一定要重视初始上界的作用，一个好的贪心解或局部搜索解能极大地压缩搜索树。如果你发现队列膨胀得太快，内存吃紧，那可能是下界太松，或者分支策略（选择下一个城市扩展的顺序）不够好，可以考虑按照“最小 regret”（即，不选择某个城市作为下一步所导致的代价增加）来排序子节点，优先扩展 regret 大的分支，这有时能更快地找到优质解从而加强剪枝。