模拟退火解决旅行商问题 可视化

下面是一个简单的模拟退火解决旅行商问题的可视化实现，使用了Python的pygame库：

import pygame
import random
import math

# 初始化pygame
pygame.init()

# 设置屏幕大小
SCREEN_WIDTH = 800
SCREEN_HEIGHT = 600
screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))

# 设置窗口标题
pygame.display.set_caption("Traveling Salesman Problem")

# 设置字体
font = pygame.font.SysFont(None, 32)

# 设置颜色
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)

# 设置旅行商数量和初始温度
NUM_POINTS = 10
TEMPERATURE = 100

# 生成随机的旅行商坐标
points = [(random.randint(50, SCREEN_WIDTH - 50), random.randint(50, SCREEN_HEIGHT - 50)) for i in range(NUM_POINTS)]

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

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

# 随机生成初始路径
path = list(range(NUM_POINTS))
random.shuffle(path)

# 初始化温度和降温速率
temperature = TEMPERATURE
cooling_rate = 0.01

# 记录最佳路径和长度
best_path = path
best_length = path_length(path)

# 渲染函数
def render():
    # 绘制旅行商之间的连线
    for i in range(len(path)-1):
        pygame.draw.line(screen, BLUE, points[path[i]], points[path[i+1]], 2)
    pygame.draw.line(screen, BLUE, points[path[-1]], points[path[0]], 2)

    # 绘制旅行商的位置
    for point in points:
        pygame.draw.circle(screen, RED, point, 10)

    # 显示当前温度和路径长度
    text = font.render("Temperature: {:.2f}, Path length: {:.2f}".format(temperature, path_length(path)), True, BLACK)
    screen.blit(text, (10, 10))

    # 更新屏幕
    pygame.display.flip()

# 主循环
running = True
while running:
    # 处理事件
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    # 复制当前路径
    new_path = path[:]

    # 随机交换两个旅行商的位置
    i, j = random.sample(range(NUM_POINTS), 2)
    new_path[i], new_path[j] = new_path[j], new_path[i]

    # 计算新路径的长度和长度差
    new_length = path_length(new_path)
    delta_length = new_length - best_length

    # 如果新路径更优，则接受新路径
    if delta_length < 0:
        path = new_path
        best_length = new_length

        # 如果新路径是最优的，则记录下来
        if best_length < path_length(best_path):
            best_path = path[:]

    # 否则按概率接受新路径
    else:
        probability = math.exp(-delta_length / temperature)
        if random.random() < probability:
            path = new_path

    # 降温
    temperature *= (1 - cooling_rate)

    # 渲染
    screen.fill(WHITE)
    render()

# 退出pygame
pygame.quit()

运行代码后，会生成一个窗口，其中包含了随机生成的旅行商的位置和它们之间的路径。程序会不断地执行模拟退火算法来寻找最优路径，并在窗口中实时渲染路径和路径长度。当用户关闭窗口时，程序会退出。