用Python轻松解决旅行商问题（TSP）——小白也能掌握的最短路径优化算法教程

准备工作：安装必要库

我们只需要使用 Python 内置模块，无需额外安装第三方库。但为了可视化效果更好，你可以选择性安装 matplotlib（本教程不强制要求）。

方法一：暴力穷举法（适用于小规模问题）

当城市数量较少（比如 ≤ 8）时，我们可以尝试所有可能的路径，找出最短的一条。这种方法虽然效率低，但结果绝对最优。

import itertoolsimport mathdef calculate_distance(city1, city2):    """计算两个城市之间的欧几里得距离"""    return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)def total_distance(path, cities):    """计算完整路径的总距离"""    distance = 0    for i in range(len(path)):        from_city = cities[path[i]]        to_city = cities[path[(i + 1) % len(path)]]        distance += calculate_distance(from_city, to_city)    return distancedef brute_force_tsp(cities):    """暴力求解TSP"""    n = len(cities)    all_paths = itertools.permutations(range(n))    best_path = None    min_dist = float('inf')        for path in all_paths:        dist = total_distance(path, cities)        if dist < min_dist:            min_dist = dist            best_path = path        return best_path, min_dist# 示例：定义4个城市坐标cities = [(0, 0), (1, 3), (4, 3), (6, 0)]best_path, min_dist = brute_force_tsp(cities)print("最优路径:", best_path)print("最短距离:", round(min_dist, 2))

方法二：贪心最近邻算法（快速近似解）

当城市数量变多时，暴力法就不可行了。我们可以使用贪心算法：从起点出发，每次都前往最近的未访问城市。虽然不能保证最优，但速度极快，适合大规模问题的初步求解。

def nearest_neighbor_tsp(cities):    n = len(cities)    visited = [False] * n    path = [0]  # 从第0个城市开始    visited[0] = True    current = 0        for _ in range(n - 1):        nearest = -1        min_dist = float('inf')        for j in range(n):            if not visited[j]:                dist = calculate_distance(cities[current], cities[j])                if dist < min_dist:                    min_dist = dist                    nearest = j        path.append(nearest)        visited[nearest] = True        current = nearest        total_dist = total_distance(path, cities)    return path, total_dist# 测试贪心算法greedy_path, greedy_dist = nearest_neighbor_tsp(cities)print("贪心路径:", greedy_path)print("贪心距离:", round(greedy_dist, 2))

如何选择合适的方法？

• 城市数 ≤ 8：使用暴力穷举法，获得精确最优解。
• 城市数 > 8：优先使用贪心、遗传算法或模拟退火等启发式方法。
• 实际应用中，常结合多种策略进行最短路径优化。

总结

通过本教程，你已经掌握了用Python语言实现旅行商问题（TSP）的两种基础方法。无论是学习Python算法逻辑，还是解决实际的最短路径优化需求，这些知识都非常实用。后续你还可以探索更高级的算法，如遗传算法、蚁群优化等。

记住，旅行商问题不仅是学术研究热点，也在物流配送、电路板钻孔、DNA测序等领域有广泛应用。动手试试吧，用代码解决现实世界的难题！