Python中A*算法实现TSP最短路径时返回None问题排查

你的代码返回None的核心问题是全局visited集合的使用完全错误，TSP问题中不能用全局集合记录已访问节点——因为不同路径可能经过相同节点，但后续遍历分支完全不同，全局visited会直接阻断所有包含该节点的后续路径，导致无法找到遍历所有节点的完整路径。

具体问题点 #

• 你已经通过i not in path判断节点是否在当前路径中，避免重复访问，全局visited属于画蛇添足，反而破坏了路径的多样性。
• 当某个节点被加入visited后，所有后续包含该节点的分支都会被跳过，算法无法找到覆盖所有节点的完整路径，最终走到循环结束返回None。

修复后的代码 #

import heapq
# 假设euclidean_distance是你已实现的启发式函数，节点坐标为可传入的参数

def a_star(start, goal, graph):
    N = len(graph)  # 动态获取节点总数，避免硬编码错误
    # 使用heapq优化堆操作，比手动sorted+pop(0)效率更高
    heap = []
    # 初始入堆元素：(总估计代价, 当前节点, 路径, 实际累计权重)
    heapq.heappush(heap, (euclidean_distance(start, goal), start, [start], 0))

    while heap:
        cost, current, path, weight = heapq.heappop(heap)
        
        # 路径长度等于节点数，说明遍历完所有节点，返回结果
        if len(path) == N:
            return path, weight
        
        # 遍历当前节点的邻接节点
        for i, edge_weight in enumerate(graph[current]):
            # 确保存在有效边，且节点未在当前路径中
            if edge_weight > 0 and i not in path:
                # 计算新的估计代价：实际累计权重 + 新边权重 + 启发式距离
                new_estimated_cost = weight + edge_weight + euclidean_distance(i, goal)
                heapq.heappush(heap, (new_estimated_cost, i, path + [i], weight + edge_weight))

    return None, None

额外优化说明 #

• 替换手动维护堆的方式，改用heapq模块的heappush和heappop，时间复杂度从O(n²)降到O(n log n)，性能更优。
• 修正了启发式代价的计算逻辑，原代码中euclidean_distance的参数写法存在错误（(start, goal)这类元组不符合常规坐标传入逻辑），此处改为直接传入节点坐标参数。
• 把节点总数N改为动态获取len(graph)，避免硬编码导致的路径长度判断错误。

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