旅行商问题Traveling Salesman Problem, TSP是组合优化领域中一颗璀璨的明珠也是计算机科学中 NP-hard 问题的典型代表。其问题描述简洁而优雅给定nnn个城市以及两两之间的距离d(i,j)d(i, j)d(i,j)求解一条从某一城市出发恰好访问每个城市一次并最终返回起点的最短哈密顿回路。尽管表述简单但随着城市数量的增加其解空间呈阶乘级增长使得寻找最优解成为一项极具挑战性的任务。从数学角度看TSP 可以被形式化为在一个带权完全图中寻找最小权重的哈密顿回路。设城市集合为V{1,2,…,n}V \{1, 2, \dots, n\}V{1,2,…,n}距离函数为d:V×V→Rd: V \times V \to \mathbb{R}^d:V×V→R我们的目标是最小化路径总长度LLL即Lmin∑i1nd(πi,πi1) L \min \sum_{i1}^{n} d(\pi_i, \pi_{i1})Lmini1∑nd(πi,πi1)其中π\piπ是城市的一个排列且πn1π1\pi_{n1} \pi_1πn1π1。由于 TSP 的复杂度极高时间复杂度约为O(n!)O(n!)O(n!)对于大规模实例精确算法往往无能为力因此工程实践中常采用启发式算法寻求近似最优解。为了将理论落地我们考虑一个具体的对称 TSP 实例。假设有 4 个城市A,B,C,DA, B, C, DA,B,C,D它们之间的距离矩阵DDD定义如下D[0101520100352515350302025300] D \begin{bmatrix} 0 10 15 20 \\ 10 0 35 25 \\ 15 35 0 30 \\ 20 25 30 0 \end{bmatrix}D0101520100352515350302025300该矩阵是对称的即d(i,j)d(j,i)d(i, j) d(j, i)d(i,j)d(j,i)且对角线为 0符合欧几里得空间的基本直觉。针对此问题我们首先实现暴力枚举法Brute Force。该方法通过遍历所有可能的城市排列Permutation来寻找全局最优解。虽然这种方法的时间复杂度为O(n!)O(n!)O(n!)仅适用于小规模问题但它保证了结果的绝对精确。以下是 Python 实现importitertoolsimportmath# 城市节点cities[A,B,C,D]# 距离字典邻接表形式dist{(A,A):0,(A,B):10,(A,C):15,(A,D):20,(B,A):10,(B,B):0,(B,C):35,(B,D):25,(C,A):15,(C,B):35,(C,C):0,(C,D):30,(D,A):20,(D,B):25,(D,C):30,(D,D):0}defcalculate_path_length(path):计算路径总长度total0foriinrange(len(path)-1):totaldist[(path[i],path[i1])]totaldist[(path[-1],path[0])]# 回到起点returntotal# 固定起点为 A对其他城市进行全排列start_nodeAother_nodes[cityforcityincitiesifcity!start_node]optimal_pathNonemin_distancemath.inf# 遍历所有排列组合forperminitertools.permutations(other_nodes):current_path(start_node,)perm current_distcalculate_path_length(current_path)ifcurrent_distmin_distance:min_distancecurrent_dist optimal_pathcurrent_pathprint(f最优路径精确解:{optimal_path})print(f最短距离:{min_distance})运行上述代码我们可以得到最优路径为A→B→D→CA \to B \to D \to CA→B→D→C总距离为808080。然而当城市数量增加到 20 个以上时暴力枚举将消耗天文数字的时间。此时我们需要转向启发式算法。这里我们实现最近邻算法Nearest Neighbor这是一种贪婪策略每一步都选择距离当前城市最近的未访问城市。虽然它不能保证最优但其时间复杂度仅为O(n2)O(n^2)O(n2)速度极快。# 城市列表cities{A,B,C,D}# 距离映射必须包含所有城市对dist{(A,B):10,(B,A):10,(A,C):15,(C,A):15,(A,D):20,(D,A):20,(B,C):35,(C,B):35,(B,D):25,(D,B):25,(C,D):30,(D,C):30,}defcalculate_path_length(route):计算路径总距离total0foriinrange(len(route)-1):totaldist[(route[i],route[i1])]# 可选回到起点totaldist[(route[-1],route[0])]returntotaldefnearest_neighbor_tsp(start,distance_map):最近邻启发式求解 TSPunvisitedset(cities)route[start]unvisited.remove(start)current_citystartwhileunvisited:next_citymin(unvisited,keylambdacity:distance_map[(current_city,city)])route.append(next_city)unvisited.remove(next_city)current_citynext_cityreturnroute# 执行最近邻算法nn_routenearest_neighbor_tsp(A,dist)nn_distancecalculate_path_length(nn_route)print(f最近邻路径:{nn_route})print(f最近邻距离:{nn_distance})在本例中最近邻算法同样输出了808080的最优解但在更复杂的数据集中结果通常会略逊于最优解。这种权衡体现了算法设计中“时间”与“精度”的经典博弈。对于更大规模的现实问题我们往往需要引入更复杂的元启发式算法如遗传算法、模拟退火或使用 Google OR-Tools 等专业优化库。TSP 不仅是理论的试金石更是物流配送、电路板钻孔、基因测序等众多实际应用的核心模型。 旅行商问题：从数学模型到 Python 实战
旅行商问题Traveling Salesman Problem, TSP是组合优化领域中一颗璀璨的明珠也是计算机科学中 NP-hard 问题的典型代表。其问题描述简洁而优雅给定nnn个城市以及两两之间的距离d(i,j)d(i, j)d(i,j)求解一条从某一城市出发恰好访问每个城市一次并最终返回起点的最短哈密顿回路。尽管表述简单但随着城市数量的增加其解空间呈阶乘级增长使得寻找最优解成为一项极具挑战性的任务。从数学角度看TSP 可以被形式化为在一个带权完全图中寻找最小权重的哈密顿回路。设城市集合为V{1,2,…,n}V \{1, 2, \dots, n\}V{1,2,…,n}距离函数为d:V×V→Rd: V \times V \to \mathbb{R}^d:V×V→R我们的目标是最小化路径总长度LLL即Lmin∑i1nd(πi,πi1) L \min \sum_{i1}^{n} d(\pi_i, \pi_{i1})Lmini1∑nd(πi,πi1)其中π\piπ是城市的一个排列且πn1π1\pi_{n1} \pi_1πn1π1。由于 TSP 的复杂度极高时间复杂度约为O(n!)O(n!)O(n!)对于大规模实例精确算法往往无能为力因此工程实践中常采用启发式算法寻求近似最优解。为了将理论落地我们考虑一个具体的对称 TSP 实例。假设有 4 个城市A,B,C,DA, B, C, DA,B,C,D它们之间的距离矩阵DDD定义如下D[0101520100352515350302025300] D \begin{bmatrix} 0 10 15 20 \\ 10 0 35 25 \\ 15 35 0 30 \\ 20 25 30 0 \end{bmatrix}D0101520100352515350302025300该矩阵是对称的即d(i,j)d(j,i)d(i, j) d(j, i)d(i,j)d(j,i)且对角线为 0符合欧几里得空间的基本直觉。针对此问题我们首先实现暴力枚举法Brute Force。该方法通过遍历所有可能的城市排列Permutation来寻找全局最优解。虽然这种方法的时间复杂度为O(n!)O(n!)O(n!)仅适用于小规模问题但它保证了结果的绝对精确。以下是 Python 实现importitertoolsimportmath# 城市节点cities[A,B,C,D]# 距离字典邻接表形式dist{(A,A):0,(A,B):10,(A,C):15,(A,D):20,(B,A):10,(B,B):0,(B,C):35,(B,D):25,(C,A):15,(C,B):35,(C,C):0,(C,D):30,(D,A):20,(D,B):25,(D,C):30,(D,D):0}defcalculate_path_length(path):计算路径总长度total0foriinrange(len(path)-1):totaldist[(path[i],path[i1])]totaldist[(path[-1],path[0])]# 回到起点returntotal# 固定起点为 A对其他城市进行全排列start_nodeAother_nodes[cityforcityincitiesifcity!start_node]optimal_pathNonemin_distancemath.inf# 遍历所有排列组合forperminitertools.permutations(other_nodes):current_path(start_node,)perm current_distcalculate_path_length(current_path)ifcurrent_distmin_distance:min_distancecurrent_dist optimal_pathcurrent_pathprint(f最优路径精确解:{optimal_path})print(f最短距离:{min_distance})运行上述代码我们可以得到最优路径为A→B→D→CA \to B \to D \to CA→B→D→C总距离为808080。然而当城市数量增加到 20 个以上时暴力枚举将消耗天文数字的时间。此时我们需要转向启发式算法。这里我们实现最近邻算法Nearest Neighbor这是一种贪婪策略每一步都选择距离当前城市最近的未访问城市。虽然它不能保证最优但其时间复杂度仅为O(n2)O(n^2)O(n2)速度极快。# 城市列表cities{A,B,C,D}# 距离映射必须包含所有城市对dist{(A,B):10,(B,A):10,(A,C):15,(C,A):15,(A,D):20,(D,A):20,(B,C):35,(C,B):35,(B,D):25,(D,B):25,(C,D):30,(D,C):30,}defcalculate_path_length(route):计算路径总距离total0foriinrange(len(route)-1):totaldist[(route[i],route[i1])]# 可选回到起点totaldist[(route[-1],route[0])]returntotaldefnearest_neighbor_tsp(start,distance_map):最近邻启发式求解 TSPunvisitedset(cities)route[start]unvisited.remove(start)current_citystartwhileunvisited:next_citymin(unvisited,keylambdacity:distance_map[(current_city,city)])route.append(next_city)unvisited.remove(next_city)current_citynext_cityreturnroute# 执行最近邻算法nn_routenearest_neighbor_tsp(A,dist)nn_distancecalculate_path_length(nn_route)print(f最近邻路径:{nn_route})print(f最近邻距离:{nn_distance})在本例中最近邻算法同样输出了808080的最优解但在更复杂的数据集中结果通常会略逊于最优解。这种权衡体现了算法设计中“时间”与“精度”的经典博弈。对于更大规模的现实问题我们往往需要引入更复杂的元启发式算法如遗传算法、模拟退火或使用 Google OR-Tools 等专业优化库。TSP 不仅是理论的试金石更是物流配送、电路板钻孔、基因测序等众多实际应用的核心模型。