旅行商问题（Traveling Salesman Problem, TSP）是组合优化领域中一颗璀璨的明珠，也是计算机科学中 NP-hard 问题的典型代表。其问题描述简洁而优雅：给定 个城市以及两两之间的距离 ，求解一条从某一城市出发，恰好访问每个城市一次并最终返回起点的最短哈密顿回路。尽管表述简单，但随着城市数量的增加，其解空间呈阶乘级增长，使得寻找最优解成为一项极具挑战性的任务。
从数学角度看，TSP 可以被形式化为在一个带权完全图中寻找最小权重的哈密顿回路。设城市集合为 ，距离函数为 ，我们的目标是最小化路径总长度 ，即：
其中 是城市的一个排列，且 。由于 TSP 的复杂度极高（时间复杂度约为 ），对于大规模实例，精确算法往往无能为力，因此工程实践中常采用启发式算法寻求近似最优解。
为了将理论落地，我们考虑一个具体的对称 TSP 实例。假设有 4 个城市 ，它们之间的距离矩阵 定义如下：
该矩阵是对称的，即 ，且对角线为 0，符合欧几里得空间的基本直觉。
针对此问题，我们首先实现暴力枚举法（Brute Force）。该方法通过遍历所有可能的城市排列（Permutation）来寻找全局最优解。虽然这种方法的时间复杂度为 ，仅适用于小规模问题，但它保证了结果的绝对精确。以下是 Python 实现：
import itertools
import math
# 城市节点
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 = 0
for i in range(len(path) - 1):
total += dist[(path[i], path[i+1])]
total += dist[(path[-1], path[0])] # 回到起点
return total
# 固定起点为 A，对其他城市进行全排列
start_node = 'A'
other_nodes = [city for city in cities if city != start_node]
optimal_path = None
min_distance = math.inf
# 遍历所有排列组合
for perm in itertools.permutations(other_nodes):
current_path = (start_node,) + perm
current_dist = calculate_path_length(current_path)
if current_dist < min_distance:
min_distance = current_dist
optimal_path = current_path
print(f"最优路径（精确解）: {optimal_path}")
print(f"最短距离: {min_distance}")
运行上述代码，我们可以得到最优路径为 ，总距离为 。
然而，当城市数量增加到 20 个以上时，暴力枚举将消耗天文数字的时间。此时，我们需要转向启发式算法。这里我们实现最近邻算法（Nearest Neighbor），这是一种贪婪策略：每一步都选择距离当前城市最近的未访问城市。虽然它不能保证最优，但其时间复杂度仅为 ，速度极快。
# 城市列表
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 = 0
for i in range(len(route) - 1):
total += dist[(route[i], route[i + 1])]
# 可选：回到起点
total += dist[(route[-1], route[0])]
return total
defnearest_neighbor_tsp(start, distance_map):
"""最近邻启发式求解 TSP"""
unvisited = set(cities)
route = [start]
unvisited.remove(start)
current_city = start
while unvisited:
next_city = min(
unvisited,
key=lambda city: distance_map[(current_city, city)]
)
route.append(next_city)
unvisited.remove(next_city)
current_city = next_city
return route
# 执行最近邻算法
nn_route = nearest_neighbor_tsp('A', dist)
nn_distance = calculate_path_length(nn_route)
print(f"最近邻路径: {nn_route}")
print(f"最近邻距离: {nn_distance}")
在本例中，最近邻算法同样输出了 的最优解，但在更复杂的数据集中，结果通常会略逊于最优解。这种权衡体现了算法设计中“时间”与“精度”的经典博弈。对于更大规模的现实问题，我们往往需要引入更复杂的元启发式算法（如遗传算法、模拟退火）或使用 Google OR-Tools 等专业优化库。TSP 不仅是理论的试金石，更是物流配送、电路板钻孔、基因测序等众多实际应用的核心模型。
