A*算法读取JSON寻最短路径陷入死循环的问题求助

首先，你的代码陷入死循环的核心原因是没有实现A*算法必备的开放列表（Open List）和已访问列表（Closed List），同时节点选择和路径跟踪的逻辑也不符合A*的规范。让我们一步步拆解问题并修复：

你的代码存在的关键问题 #

1. 无已访问节点标记：没有记录哪些城市已经被处理过，导致程序反复访问同一个节点（比如Kırıkkale），陷入无限循环。
2. 错误的候选节点管理：每次只处理当前节点的子节点，并且覆盖之前的候选节点信息，这更像是贪心算法，而非A*——A*需要保留所有待评估的节点，从中选择最优的那个。
3. 路径记录逻辑错误：直接将当前节点加入路径，没有通过父节点回溯完整路径，导致重复添加同一节点。
4. 未处理更优路径：如果某个节点存在多条路径，你的代码无法更新为更短的路径，可能导致最终结果不是最短路径。

修正后的A*算法实现 #

下面是符合A*规范的代码，它能正确找到最短路径并避免死循环：

import json

def a_star_search(start_name, goal_name, tree):
    # 辅助函数：在树结构中查找指定名称的节点
    def find_node(name, data):
        if data['name'] == name:
            return data
        for child in data['children']:
            result = find_node(name, child)
            if result:
                return result
        return None

    # 定位起点和终点节点
    start_node = find_node(start_name, tree)
    if not start_node:
        raise ValueError(f"起点城市 {start_name} 未找到")
    goal_node = find_node(goal_name, tree)
    if not goal_node:
        raise ValueError(f"终点城市 {goal_name} 未找到")

    # Open列表：存储待评估的节点，每个元素包含节点数据、到起点的实际距离(g)、父节点
    open_list = []
    # Closed列表：存储已处理过的城市名称，避免重复访问
    closed_list = []

    # 初始化起点节点
    open_list.append({
        'node': start_node,
        'g': 0,
        'parent': None
    })

    while open_list:
        # 按f值(g + h)排序，选择f值最小的节点（h是节点的启发式距离）
        open_list.sort(key=lambda x: x['g'] + x['node']['heuristic'])
        current_entry = open_list.pop(0)
        current_node = current_entry['node']
        current_g = current_entry['g']

        # 到达终点，回溯路径
        if current_node['name'] == goal_name:
            path = []
            temp_entry = current_entry
            while temp_entry:
                path.append(temp_entry['node']['name'])
                temp_entry = temp_entry['parent']
            # 反转路径得到起点到终点的顺序
            return path[::-1]

        # 将当前节点标记为已访问
        closed_list.append(current_node['name'])

        # 遍历当前节点的所有相邻城市
        for neighbor in current_node['children']:
            neighbor_name = neighbor['name']
            # 跳过已访问的节点
            if neighbor_name in closed_list:
                continue

            # 计算到相邻城市的实际距离：当前节点的g值 + 相邻城市的距离
            neighbor_g = current_g + neighbor['distance']
            # 检查相邻城市是否已在Open列表中
            existing_entry = next((item for item in open_list if item['node']['name'] == neighbor_name), None)

            if not existing_entry:
                # 不在Open列表中，添加进去
                open_list.append({
                    'node': neighbor,
                    'g': neighbor_g,
                    'parent': current_entry
                })
            else:
                # 已在Open列表中，如果当前路径更短，更新g值和父节点
                if neighbor_g < existing_entry['g']:
                    existing_entry['g'] = neighbor_g
                    existing_entry['parent'] = current_entry

    # Open列表为空，说明没有可达路径
    return None

def main():
    with open('provinces.json', encoding='utf-8') as f:
        tree = json.load(f)
    shortest_path = a_star_search('Ankara', 'Gaziantep', tree)
    if shortest_path:
        print(' -> '.join(shortest_path))
    else:
        print("未找到可行路径")

if __name__ == '__main__':
    main()

代码核心逻辑说明 #

1. 节点查找：通过find_node函数在你的JSON树结构中定位起点和终点。
2. Open/Closed列表：
   • open_list保存所有需要评估的节点，每次选择f值最小的节点处理。
   • closed_list记录已处理的节点，彻底避免重复访问。
3. 路径回溯：当到达终点时，通过父节点反向遍历，再反转得到从起点到终点的正确路径。
4. 更优路径处理：如果发现到达某个节点的更短路径，会更新该节点的实际距离和父节点信息，确保最终得到的是最短路径。

运行这段代码后，应该能输出你期望的路径：Ankara -> Kırıkkale -> Kırşehir -> Nevşehir -> Kayseri -> Kahramanmaraş -> Gaziantep

内容的提问来源于stack exchange，提问作者Ali.Turkkan