旅行商问题可视化python

旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题，它是指一个旅行商从出发地出发，要到若干个客户地点去旅行，最后回到出发地，求最短的路线。在这个问题中，每个客户地点只能被访问一次，而且出发地和终点都是同一个地点。

以下是一个使用 Python 和 Matplotlib 库实现的旅行商问题可视化的示例代码：

import numpy as np
import matplotlib.pyplot as plt

# 城市坐标
cities = np.array([[60, 200], [180, 200], [80, 180], [140, 180], [20, 160],
                   [100, 160], [200, 160], [140, 140], [40, 120], [100, 120],
                   [180, 100], [60, 80], [120, 80], [180, 60], [20, 40],
                   [100, 40], [200, 40], [20, 20], [60, 20], [160, 20]])

# 计算距离矩阵
def calc_distance_matrix(cities):
    n = len(cities)
    distance_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            distance_matrix[i][j] = np.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2)
    return distance_matrix

# 计算路径长度
def calc_path_length(path, distance_matrix):
    n = len(path)
    length = 0
    for i in range(n-1):
        length += distance_matrix[path[i]][path[i+1]]
    length += distance_matrix[path[n-1]][path[0]]
    return length

# 随机生成初始路径
def generate_random_path(n):
    path = np.arange(n)
    np.random.shuffle(path)
    return path

# 交换两个城市的位置
def swap_cities(path):
    n = len(path)
    i, j = np.random.randint(0, n, size=2)
    path[i], path[j] = path[j], path[i]
    return path

# 模拟退火算法
def simulated_annealing(distance_matrix, init_temperature=100, alpha=0.99, iter_per_temp=100):
    # 初始化路径和路径长度
    n = len(distance_matrix)
    path = generate_random_path(n)
    path_length = calc_path_length(path, distance_matrix)
    # 模拟退火过程
    temperature = init_temperature
    while temperature > 1:
        for i in range(iter_per_temp):
            new_path = swap_cities(np.copy(path))
            new_path_length = calc_path_length(new_path, distance_matrix)
            delta = new_path_length - path_length
            if delta < 0 or np.exp(-delta/temperature) > np.random.rand():
                path, path_length = new_path, new_path_length
        temperature *= alpha
    return path, path_length

# 可视化
def visualize(cities, path):
    plt.figure(figsize=(6, 6))
    plt.scatter(cities[:, 0], cities[:, 1], color='blue')
    plt.plot(cities[path, 0], cities[path, 1], color='red')
    plt.show()

if __name__ == '__main__':
    distance_matrix = calc_distance_matrix(cities)
    path, path_length = simulated_annealing(distance_matrix)
    print('最短路径长度：', path_length)
    visualize(cities, path)

代码中使用模拟退火算法来求解 TSP。在模拟退火过程中，每个温度下进行一定次数的迭代，每次迭代随机交换两个城市的位置，如果新路径更优或者按照一定概率接受新路径，则更新路径和路径长度。最后得到的路径即为最优路径。可视化部分使用 Matplotlib 库绘制城市位置和最优路径。