写一段python代码解决旅行商问题

旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题，目标是最小化旅行商访问所有城市并返回起点所需的距离。由于其复杂度为NP完全问题，通常采用启发式算法如遗传算法、模拟退火等求解近似最优解。下面是一段基于Python的简单遗传算法实现：

import random
from itertools import permutations

# 定义城市和它们之间的距离矩阵
cities = ['A', 'B', 'C', 'D']  # 可根据实际需要替换
distances = {
    ('A', 'B'): 5,
    ('A', 'C'): 7,
    ('A', 'D'): 9,
    ('B', 'A'): 5,
    # ... 更多城市间的距离
}

def tsp(distance_matrix):
    # 生成初始解，即随机的城市顺序排列
    population_size = 100
    routes = [permutations(cities) for _ in range(population_size)]
    
    # 计算适应度
    def fitness(route):
        return sum(distance_matrix[(route[i], route[i+1])] for i in range(len(route)-1)) + distance_matrix[(route[-1], route[0])]

    best_route = max(routes, key=fitness)
    best_fitness = fitness(best_route)

    while True:
        new_population = []
        for _ in range(int(0.5 * population_size)):
            parent1, parent2 = random.choices(routes, k=2)
            child = crossover(parent1, parent2)
            mutation(child)
            new_population.append(child)
        
        for route in new_population:
            new_fitness = fitness(route)
            if new_fitness < best_fitness:
                best_fitness = new_fitness
                best_route = route
        
        routes = new_population
        yield best_route, best_fitness
        if best_fitness == sum(distances.values()) - distances['A']['A']:  # 当找到最优解时停止迭代
            break

def crossover(parent1, parent2):
    cut_point = random.randint(1, len(parent1)-1)
    return list(parent1[:cut_point] + parent2[cut_point:])

def mutation(route):
    # 随机交换两个位置的城市
    i, j = random.sample(range(len(route)), 2)
    route[i], route[j] = route[j], route[i]

for best_route, best_fitness in tsp(distances):
    print(f"Best route: {best_route}, Total distance: {best_fitness}