Python递归实现A*算法路径及状态成本计算错误修复求助

原代码核心问题 #

• 本质为贪心局部最优搜索，不符合A*算法标准逻辑：仅计算单步边价+下节点启发值，未累加从起点到当前节点的实际累计路径代价g(n)，无全局代价判断能力。
• 代价统计逻辑错误：路径字典存储的是启发值与单步边价的混合值，求和后得到的并非实际路径总开销。
• 无回溯、无开放/封闭列表维护：仅能沿当前局部最优分支走，不会回退选择其他更优路径，也不会处理重复节点的更优代价更新，仅在局部最优刚好匹配全局最优时碰巧得到正确路径。
• 全局路径变量设计不合理，无递归对应的回退机制。

修复后可运行代码 #

规则说明：你提供的state字典为A算法的启发式估计函数h(n)（节点到终点的预估代价），A总估计代价公式为f(n) = g(n) + h(n)，其中g(n)为起点到当前节点的实际累计路径代价，最终输出的总代价为终点的g值，不计入启发值。

graph= {'A':{'B':6, 'F':3},
    'B':{'C':3, 'D':2},
    'C':{'E':5, 'D':1},
    'D':{'E':8},
    'E':{'J':5},
    'F':{'G':1, 'H':7},
    'G':{'I':3},
    'H':{'I':2},
    'I':{'E':5, 'J':3},
    'J':{}}

state = {'A':10,
     'B':8,
     'C':5,
     'D':7,
     'E':3,
     'F':6,
     'G':5,
     'H':3,
     'I':1,
     'J':0}

def recursive_a_star(graph, current, end, h, g_scores, open_list, closed_list, path):
    # 到达终点直接返回结果
    if current == end:
        return path, g_scores[current]
    
    # 当前节点移入封闭列表，避免重复遍历
    closed_list.add(current)
    # 遍历所有相邻节点
    for neighbor, step_cost in graph[current].items():
        if neighbor in closed_list:
            continue
        # 计算从起点走到相邻节点的实际累计代价
        tentative_g = g_scores[current] + step_cost
        # 相邻节点未访问，或新路径代价更优则更新
        if neighbor not in g_scores or tentative_g < g_scores[neighbor]:
            g_scores[neighbor] = tentative_g
            open_list[neighbor] = tentative_g + h[neighbor]
            path[neighbor] = current
    
    # 开放列表为空说明无可达路径
    if not open_list:
        return None, float('inf')
    
    # 选择f值最小的节点作为下一个遍历节点
    next_node = min(open_list, key=open_list.get)
    del open_list[next_node]
    
    # 递归搜索
    return recursive_a_star(graph, next_node, end, h, g_scores, open_list, closed_list, path)

# 初始化参数
start_node = 'A'
end_node = 'J'
g_scores = {start_node: 0}
open_list = {start_node: 0 + state[start_node]}
closed_list = set()
path_record = {start_node: None}

# 执行算法
result_path, total_cost = recursive_a_star(graph, start_node, end_node, state, g_scores, open_list, closed_list, path_record)

# 还原完整路径顺序
reverse_path = []
current = end_node
while current is not None:
    reverse_path.append(current)
    current = result_path[current]
final_path = reverse_path[::-1]

# 输出结果
print("最优路径：", final_path)
print("实际总路径代价：", total_cost)

运行输出 #

最优路径： ['A', 'F', 'G', 'I', 'J']
实际总路径代价： 10

原代码错误输出参考：
['A', 'F', 'G', 'I', 'J'] Total cost: 26 {'A': 0, 'F': 9, 'G': 10, 'I': 4, 'J': 3}

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