旅行商问题回溯法代码

旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，目标是最小化一个旅行商访问所有城市恰好一次并返回起点的总路程。回溯法是一种搜索算法，常用于解决这类问题。以下是使用Python实现旅行商问题回溯法的一个简单示例：

def tsp_city_list(cities):
    n = len(cities)
    tour =  * n

    def tsp_helper(path, current_city):
        if current_city == n - 1:  # 已经完成路径，计算并更新最优解
            nonlocal best_tour, best_distance
            distance = calculate_distance(path)
            if distance < best_distance:
                best_tour = path.copy()
                best_distance = distance
        else:
            for next_city in range(current_city + 1, n):
                tour[current_city] = next_city
                tsp_helper(path + [next_city], current_city + 1)

    tsp_helper([], 0)
    return best_tour, best_distance

def calculate_distance(path):
    total_distance = 0
    for i in range(len(path) - 1):
        total_distance += cities[path[i]][path[i + 1]]
    # 计算起始点到结束点的距离
    total_distance += cities[path[-1]][0]
    return total_distance

# 假设cities是一个二维列表，表示城市之间的距离
cities = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

best_tour, best_distance = tsp_city_list(cities)
print(f"最优路径: {best_tour}")
print(f"最小总距离: {best_distance} 单位：城市间的距离")