启发式退火求解att48.tsp数据集的最优路径并绘图python代码

好的，以下是启发式退火算法求解att48.tsp数据集的最优路径并绘图的Python代码。

import math
import random
import matplotlib.pyplot as plt

# 读取tsp文件
def read_tsp(filename):
    with open(filename, 'r') as f:
        lines = f.readlines()[6:]
        nodes = []
        for line in lines:
            node_id, x, y = line.strip().split(' ')
            nodes.append((float(x), float(y)))
        return nodes

# 计算两点之间的距离
def distance(node1, node2):
    return math.sqrt((node1[0]-node2[0])**2 + (node1[1]-node2[1])**2)

# 计算路径长度
def path_length(path, nodes):
    length = 0
    for i in range(len(path)):
        length += distance(nodes[path[i]], nodes[path[(i+1)%len(path)]])
    return length

# 生成初始解
def generate_initial_solution(nodes):
    path = list(range(len(nodes)))
    random.shuffle(path)
    return path

# 退火算法
def simulated_annealing(nodes, initial_temperature=1000, cooling_rate=0.99, stopping_temperature=0.1):
    # 生成初始解
    current_path = generate_initial_solution(nodes)
    current_length = path_length(current_path, nodes)
    best_path = current_path[:]
    best_length = current_length
    temperature = initial_temperature

    while temperature > stopping_temperature:
        # 生成新解
        new_path = current_path[:]
        index1 = random.randint(0, len(new_path)-1)
        index2 = random.randint(0, len(new_path)-1)
        new_path[index1], new_path[index2] = new_path[index2], new_path[index1]
        new_length = path_length(new_path, nodes)

        # 判断是否接受新解
        if new_length < current_length or random.random() < math.exp(-(new_length-current_length)/temperature):
            current_path = new_path
            current_length = new_length

        # 更新最优解
        if current_length < best_length:
            best_path = current_path[:]
            best_length = current_length

        # 降温
        temperature *= cooling_rate

    return best_path

# 绘制路径图
def plot_path(nodes, path):
    xs = [nodes[i][0] for i in path]
    ys = [nodes[i][1] for i in path]
    plt.plot(xs, ys, '-o')
    plt.show()

if __name__ == '__main__':
    nodes = read_tsp('att48.tsp')
    path = simulated_annealing(nodes)
    print(path)
    print(path_length(path, nodes))
    plot_path(nodes, path)

运行以上代码，即可输出att48.tsp数据集的最优路径并绘制路径图。