A*求解TSP时nearest_to_start_distance值异常增长问题排查

我用A*实现旅行商问题（TSP），但nearest_to_start_distance变量的实现存在问题——它本该表示节点到起点的固定距离（比如B到A应为10），但程序返回值异常增长。例如路径['A','B']对应的f_n值为20，路径['A','C','B']对应的f_n值为60，与预期不符。希望在保留原有程序逻辑的前提下，排查并修复该变量的实现错误。

错误根源分析 #

1. 函数逻辑错位：原mst_heuristic函数计算了nearest_unvisited_distance却未使用，反而返回nearest_to_start_distance，但调用时却将该函数的返回值当作nearest_unvisited_distance来计算f_n，完全混淆了两个变量的用途。
2. 未访问集合未动态更新：全局的unvisited集合始终是初始状态（仅移除起点），没有随路径推进移除已访问节点，导致启发式计算的是到所有初始未访问节点的最近距离，而非当前剩余未访问节点的距离。
3. 冗余计算：通过mst_heuristic获取到起点的距离完全多余，直接从图结构中读取即可。

修复后的代码 #

import heapq

def get_nearest_unvisited_distance(graph, current_city, unvisited_cities):
    if not unvisited_cities:
        return 0
    nearest = float('inf')
    for city in unvisited_cities:
        if city in graph[current_city]:
            dist = graph[current_city][city]
            if dist < nearest:
                nearest = dist
    return nearest

def a_star_tsp(graph, start_city):
    num_nodes = len(graph)
    # 优先队列元素：(f值, 当前城市, 路径, 已访问节点集合, 当前未访问节点集合)
    priority_queue = [(0, start_city, [start_city], {start_city}, set(graph.keys()) - {start_city})]

    while priority_queue:
        print("Priority Queue:", priority_queue)
        cost, current_city, path, path_set, unvisited = heapq.heappop(priority_queue)
        print("Current City:", current_city)

        for next_city, edge_cost in graph[current_city].items():
            if next_city not in path_set:
                new_path = path + [next_city]
                new_path_set = path_set.copy()
                new_path_set.add(next_city)
                new_unvisited = unvisited - {next_city}
                g_n = cost + edge_cost
                # 获取当前节点到剩余未访问节点的最近距离作为启发值
                nearest_unvisited_dist = get_nearest_unvisited_distance(graph, next_city, new_unvisited)
                # 所有节点访问完时，启发值为回到起点的距离；否则取到剩余节点的最近距离
                h_n = nearest_unvisited_dist + (graph[next_city][start_city] if not new_unvisited else 0)
                f_n = g_n + h_n
                heapq.heappush(priority_queue, (f_n, next_city, new_path, new_path_set, new_unvisited))

        # 检查队列中所有路径是否已访问完所有节点
        if all(len(p) == num_nodes for _, _, p, _, _ in priority_queue):
            min_cost_entry = min(priority_queue, key=lambda x: x[0])
            min_cost_path = min_cost_entry[2]
            min_cost = sum(graph[min_cost_path[i]][min_cost_path[i+1]] for i in range(len(min_cost_path)-1))
            min_cost += graph[min_cost_path[-1]][start_city]
            min_cost_path.append(start_city)
            print(f"\nPriority Queue: {priority_queue}\n")
            print(f"Optimal TSP path: {min_cost_path}, Total cost: {min_cost}")
            return min_cost_path

    return path

# 示例测试
cities = {
    'A': {'B': 10, 'C': 15, 'D': 20},
    'B': {'A': 10, 'C': 20, 'D': 25},
    'C': {'A': 15, 'B': 20, 'D': 30},
    'D': {'A': 20, 'B': 25, 'C': 30}
}

start_city = 'A'
result = a_star_tsp(cities, start_city)

修复说明 #

• 拆分启发函数：将原混乱的mst_heuristic拆分为get_nearest_unvisited_distance，专门计算当前节点到剩余未访问节点的最近距离，逻辑清晰单一。
• 动态维护未访问集合：将unvisited集合放入优先队列的每个元素中，每次扩展路径时生成新的未访问集合，确保启发值计算的是当前剩余节点的距离。
• 修正f值计算逻辑：根据路径进度调整启发值——未访问节点存在时取到剩余节点的最近距离，所有节点访问完时取回到起点的距离，符合TSP的启发式需求。
• 移除冗余计算：直接从图结构中读取到起点的距离，不再通过错误的函数调用绕路。

内容的提问来源于stack exchange，提问作者artinasd