旅行商问题（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→R+d: V \times V \to \mathbb{R}^+d:V×V→R+，我们的目标是最小化路径总长度LLL，即：
L=min∑i=1nd(πi,πi+1) L = \min \sum_{i=1}^{n} d(\pi_i, \pi_{i+1})L=mini=1∑nd(πi,πi+1)
其中π\piπ是城市的一个排列，且πn+1=π1\pi_{n+1} = \pi_1πn+1=π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}D=0101520100352515350302025300
该矩阵是对称的，即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):"""计算路径总长度"""total=0foriinrange(len(path)-1):total+=dist[(path[i],path[i+1])]total+=dist[(path[-1],path[0])]# 回到起点returntotal# 固定起点为 A，对其他城市进行全排列start_node='A'other_nodes=[cityforcityincitiesifcity!=start_node]optimal_path=Nonemin_distance=math.inf# 遍历所有排列组合forperminitertools.permutations(other_nodes):current_path=(start_node,)+perm current_dist=calculate_path_length(current_path)ifcurrent_dist<min_distance:min_distance=current_dist optimal_path=current_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):"""计算路径总距离"""total=0foriinrange(len(route)-1):total+=dist[(route[i],route[i+1])]# 可选：回到起点total+=dist[(route[-1],route[0])]returntotaldefnearest_neighbor_tsp(start,distance_map):"""最近邻启发式求解 TSP"""unvisited=set(cities)route=[start]unvisited.remove(start)current_city=startwhileunvisited:next_city=min(unvisited,key=lambdacity:distance_map[(current_city,city)])route.append(next_city)unvisited.remove(next_city)current_city=next_cityreturnroute# 执行最近邻算法nn_route=nearest_neighbor_tsp('A',dist)nn_distance=calculate_path_length(nn_route)print(f"最近邻路径:{nn_route}")print(f"最近邻距离:{nn_distance}")在本例中，最近邻算法同样输出了808080的最优解，但在更复杂的数据集中，结果通常会略逊于最优解。这种权衡体现了算法设计中“时间”与“精度”的经典博弈。对于更大规模的现实问题，我们往往需要引入更复杂的元启发式算法（如遗传算法、模拟退火）或使用 Google OR-Tools 等专业优化库。TSP 不仅是理论的试金石，更是物流配送、电路板钻孔、基因测序等众多实际应用的核心模型。
