点击上方“进修编程”，选择“星标”公众号
超级无敌干货，第一时间送达！！！
A*（A-star）算法是一种功能强大且用途广泛的搜索方法，用于计算机科学中查找图中节点之间的最有效路径。A* 广泛应用于从视频游戏中的寻路到网络路由和 AI 的各种应用中，仍然是算法和人工智能领域的一项基础技术。
本文深入探讨了 A* 算法的工作原理，解释了其启发式搜索策略，以及它在其他寻路算法中脱颖而出的原因。
A* 的起源和基本原理
A* 算法由 Peter Hart、Nils Nilsson 和 Bertram Raphael 于 1968 年开发，是 Dijkstra 算法的扩展和改进，该算法也因寻找图中节点之间的最短路径而闻名。与均匀探索起始节点周围所有方向的 Dijkstra 算法不同，A* 使用启发式方法来估算从节点到目标的成本，从而优化搜索过程并减少计算负荷。
A*算法的原理
初始化:
将初始节点添加到开放集,并计算其 f(n) = g(n) + h(n) 值。
主循环:
从开放集中选择 f(n) 值最小的节点 n。
如果节点 n 是目标节点,则算法结束,返回从起点到目标节点的路径。
否则,扩展节点 n,找到其所有邻居节点。
节点扩展:
对于每个邻居节点 m:
计算从起点到节点 m 的实际成本 g(m) = g(n) + cost(n, m)。
计算从节点 m 到目标节点的启发式估计成本 h(m)。
计算节点 m 的总估计成本 f(m) = g(m) + h(m)。
如果节点 m 不在开放集或关闭集中,或者找到了更短的到达节点 m 的路径,则将其加入开放集,并记录其父节点为 n。
重复:
重复步骤 2 和 3,直到找到目标节点或开放集为空(表示没有可用路径)。
A* 算法中的启发式函数
A* 算法的有效性很大程度上取决于所使用的启发式算法。启发式算法的选择会极大地影响算法的性能和效率。好的启发式算法能够帮助算法通过探索尽可能少的节点来找到最短路径。启发式算法的属性包括：
可接受性：如果启发式方法不会高估实现目标的成本，则该启发式方法可接受。可接受启发式方法的典型示例是空间图中的直线距离。
一致性（或单调性）：如果从当前节点到目标的估计成本始终小于或等于从任何相邻节点的估计成本加上从当前节点到相邻节点的步长成本，则启发式方法是一致的。
常见的启发式方法包括基于网格的地图的曼哈顿距离（在游戏和城市规划中很有用）和用于直接点对点距离测量的欧几里得距离。
A* 的应用
A* 算法能够利用给定的启发式方法找到最有效路径，这使其适用于各种实际应用：
游戏和机器人中的寻路： A* 广泛应用于游戏行业，用于控制动态环境中的角色，以及在机器人技术中用于在点之间导航。
网络路由：在电信领域，A* 有助于确定数据包到达目的地所需的最短路由路径。
人工智能和机器学习： A* 可用于规划和决策算法，其中需要评估决策和动作的多个阶段。
使用 A* 算法寻路
步骤 1：导入库
首先导入处理优先级队列、图形处理和可视化所需的 Python 库。
import heapqimport networkx as nximport matplotlib.pyplot as plt
第 2 步：定义启发式函数
定义一个启发式函数来估算从当前节点到目标的成本。在本例中，使用曼哈顿距离作为启发式函数。
def heuristic(a, b):return abs(a[0] - b[0]) + abs(a[1] - b[1])
步骤3：实现A*算法
实现 A* 算法，该算法使用开放集、封闭集和记分结构来查找图中最短路径，从起始节点到目标节点。
def a_star(graph, start, goal):open_set = []heapq.heappush(open_set, (0, start))came_from = {}g_score = {node: float('inf') for node in graph}g_score[start] = 0f_score = {node: float('inf') for node in graph}f_score[start] = heuristic(start, goal)while open_set:_, current = heapq.heappop(open_set)if current == goal:return reconstruct_path(came_from, current)for neighbor, cost in graph[current].items():tentative_g_score = g_score[current] + costif tentative_g_score < g_score[neighbor]:came_from[neighbor] = currentg_score[neighbor] = tentative_g_scoref_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)heapq.heappush(open_set, (f_score[neighbor], neighbor))return None
步骤4：定义路径重构函数
创建一个函数，在 A* 算法完成后重建从起始节点到目标节点的路径。
def reconstruct_path(came_from, current):total_path = [current]while current in came_from:current = came_from[current]total_path.append(current)total_path.reverse()return total_path
步骤 5：设置图形并进行可视化
使用 定义图networkx，执行 A* 算法查找路径，并使用 将图和路径可视化matplotlib。
# Define the graphgraph = {(0, 0): {(1, 0): 1, (0, 1): 1},(1, 0): {(0, 0): 1, (1, 1): 1, (2, 0): 1},(0, 1): {(0, 0): 1, (1, 1): 1},(1, 1): {(1, 0): 1, (0, 1): 1, (2, 1): 1},(2, 0): {(1, 0): 1, (2, 1): 1},(2, 1): {(2, 0): 1, (1, 1): 1, (2, 2): 1},(2, 2): {(2, 1): 1}}start = (0, 0)goal = (2, 2)# Use NetworkX to create the graphG = nx.DiGraph()for node, edges in graph.items():for dest, weight in edges.items():G.add_edge(node, dest, weight=weight)# Get the path from A* algorithmpath = a_star(graph, start, goal)# Plottingpos = {node: (node[1], -node[0]) for node in graph} # position nodes based on grid coordinatesnx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, edge_color='gray', width=2)nx.draw_networkx_edges(G, pos, edgelist=path_to_edges(path), edge_color='red', width=2)plt.title('Graph Visualization with A* Path Highlighted')plt.show()
完成 A* 寻路问题
import heapqimport networkx as nximport matplotlib.pyplot as pltdef heuristic(a, b):return abs(a[0] - b[0]) + abs(a[1] - b[1])def a_star(graph, start, goal):open_set = []heapq.heappush(open_set, (0, start))came_from = {}g_score = {node: float('inf') for node in graph}g_score[start] = 0f_score = {node: float('inf') for node in graph}f_score[start] = heuristic(start, goal)while open_set:_, current = heapq.heappop(open_set)if current == goal:return reconstruct_path(came_from, current)for neighbor, cost in graph[current].items():tentative_g_score = g_score[current] + costif tentative_g_score < g_score[neighbor]:came_from[neighbor] = currentg_score[neighbor] = tentative_g_scoref_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)heapq.heappush(open_set, (f_score[neighbor], neighbor))return Nonedef reconstruct_path(came_from, current):total_path = [current]while current in came_from:current = came_from[current]total_path.append(current)total_path.reverse()return total_pathdef path_to_edges(path):return [(path[i], path[i + 1]) for i in range(len(path) - 1)]# Define the graphgraph = {(0, 0): {(1, 0): 1, (0, 1): 1},(1, 0): {(0, 0): 1, (1, 1): 1, (2, 0): 1},(0, 1): {(0, 0): 1, (1, 1): 1},(1, 1): {(1, 0): 1, (0, 1): 1, (2, 1): 1},(2, 0): {(1, 0): 1, (2, 1): 1},(2, 1): {(2, 0): 1, (1, 1): 1, (2, 2): 1},(2, 2): {(2, 1): 1}}start = (0, 0)goal = (2, 2)# Use NetworkX to create the graphG = nx.DiGraph()for node, edges in graph.items():for dest, weight in edges.items():G.add_edge(node, dest, weight=weight)# Get the path from A* algorithmpath = a_star(graph, start, goal)# Plottingpos = {node: (node[1], -node[0]) for node in graph} # position nodes based on grid coordinatesnx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, edge_color='gray', width=2)nx.draw_networkx_edges(G, pos, edgelist=path_to_edges(path), edge_color='red', width=2)plt.title('Graph Visualization with A* Path Highlighted')plt.show()
输出：
使用 A* 算法得出的路径解决方案
输出代表：
节点：用圆圈表示，并标明其坐标。例如，(0, 0) 是起始节点，(2, 2) 是目标节点。
边：连接节点的线。灰线表示所有可能的转换，红线突出显示 A* 算法选择的路径。
突出显示的路径（红色）：显示从起始节点到目标的 A* 确定的最佳路线。该路径从 (0, 0) 行进到 (0, 1)，然后向下移动到 (1, 1)，继续向下移动到 (2, 1)，最后到达 (2, 2) 处的目标。
通过这种可视化，我们可以轻松地跟踪算法的决策，并了解 A* 如何根据定义的启发式和图形结构浏览图形以找到到达目标的最有效路径。
A* 的优点
最优性：当配备可接受的启发式方法时，A* 一定能找到到达目标的最短路径。
完整性：如果存在解决方案，A* 总能找到一个解决方案。
灵活性：通过调整启发式方法，A* 可以适应各种问题设置和约束。
限制和注意事项
虽然 A* 很强大，但它并非没有局限性。内存消耗可能很大，因为它需要在内存中维护所有已探索和未探索的节点。此外，启发式算法的选择严重影响算法的性能；较差的启发式算法可能导致探索效率低下和计算量增加。
python、matlab程序设计找我
— 完 —
