### Python 实现 A* 算法并记录求解结果 以下是基于 Python 的 A* 算法实现，能够处理不同地图、初始状态和目标状态，并记录最短路径、扩展节点数、生成节点数以及运行时间。 #### A* 算法核心逻辑 A* 是一种启发式搜索算法，在寻找最短路径时结合了实际代价 \( g(n) \) 和估计代价 \( h(n) \)，其中 \( f(n) = g(n) + h(n) \)[^1]。通过优先队列管理待探索节点，每次选取具有最小 \( f(n) \) 值的节点进行扩展。 #### 代码实现 以下是一个完整的 A* 算法实现： ```python import heapq from time import perf_counter def astar_search(graph, start, goal, heuristic): """ 使用 A* 算法查找从起点到终点的最短路径。 :param graph: 图结构 {node: [(neighbor, cost), ...]} :param start: 起始节点 :param goal: 目标节点 :param heuristic: 启发函数 (node -> estimated_cost_to_goal) :return: 最短路径、扩展节点数、生成节点数、运行时间 """ open_set = [] heapq.heappush(open_set, (0, start)) # 初始化优先队列 (f_score, node) came_from = {} g_scores = {node: float('inf') for node in graph} g_scores[start] = 0 f_scores = {node: float('inf') for node in graph} f_scores[start] = heuristic(start) expanded_nodes = 0 generated_nodes = 1 t_start = perf_counter() while open_set: current_f, current_node = heapq.heappop(open_set) expanded_nodes += 1 if current_node == goal: break for neighbor, cost in graph[current_node]: tentative_g = g_scores[current_node] + cost if tentative_g < g_scores[neighbor]: came_from[neighbor] = current_node g_scores[neighbor] = tentative_g f_scores[neighbor] = tentative_g + heuristic(neighbor) if not any(node == neighbor for _, node in open_set): heapq.heappush(open_set, (f_scores[neighbor], neighbor)) generated_nodes += 1 t_end = perf_counter() runtime = t_end - t_start if goal not in came_from: return None, expanded_nodes, generated_nodes, runtime # 构建路径 path = [] current = goal while current != start: path.append(current) current = came_from.get(current) if current is None: break path.append(start) path.reverse() return path, expanded_nodes, generated_nodes, runtime # 测试用例 if __name__ == "__main__": # 定义图结构 graph = { 'A': [('B', 1), ('C', 4)], 'B': [('A', 1), ('C', 2), ('D', 5)], 'C': [('A', 4), ('B', 2), ('D', 1)], 'D': [('B', 5), ('C', 1)] } # 启发函数（欧几里得距离） def heuristic(node): goals = {'D': 0} # 只针对单一目标定义启发值 return abs(ord(node) - ord(list(goals.keys())[0])) result = astar_search(graph, 'A', 'D', heuristic) if result: path, expanded, generated, runtime = result print(f"Shortest Path: {path}") print(f"Expanded Nodes: {expanded}") print(f"Generated Nodes: {generated}") print(f"Runtime: {runtime:.6f} seconds") else: print("No path found.") ``` #### 输出解释 - **最短路径**: 记录从起始节点到目标节点的具体路径。 - **扩展节点数**: 表示在搜索过程中被取出评估的节点数量。 - **生成节点数**: 表示在整个搜索过程中创建的新节点总数。 - **运行时间**: 执行整个算法所花费的时间。 #### 关键点说明 1. A* 算法的核心在于维护一个优先队列来存储候选节点，并按照综合成本 \( f(n) \) 进行排序[^1]。 2. 启发函数的选择直接影响算法效率；通常采用曼哈顿距离或欧几里得距离作为简单场景中的启发函数[^3]。 3. 时间复杂度取决于具体问题规模和启发函数质量，空间复杂度由最大同时存在的候选项决定[^2]。 ---