路径规划算法大对决：A星、改进A星与新A星

A星 改进A星 新A星算法 路径规划 放在一张图上 对比 三天对比线在一张图 避障在路径规划领域A星算法就像一位老将一直以来都备受瞩目。而随着研究的深入改进A星和新A星算法也相继登场今天咱们就把这几位“选手”放在一张图上来一场精彩的对比看看它们在避障场景下到底谁更胜一筹。A星算法经典的智慧A星算法是一种启发式搜索算法它结合了Dijkstra算法的广度优先搜索和贪心算法的最佳优先搜索特点。其核心思想在于通过一个评估函数$f(n) g(n) h(n)$来选择下一个要扩展的节点。这里的$g(n)$表示从起点到节点$n$的实际代价$h(n)$则是从节点$n$到目标点的估计代价。下面是一段简化的Python代码示例import heapq def heuristic(a, b): return abs(a[0] - b[0]) abs(a[1] - b[1]) def astar(graph, start, goal): open_set [] heapq.heappush(open_set, (0, start)) came_from {} g_score {node: float(inf) for node in graph.keys()} g_score[start] 0 f_score {node: float(inf) for node in graph.keys()} f_score[start] heuristic(start, goal) while open_set: _, current heapq.heappop(open_set) if current goal: path [] while current in came_from: path.append(current) current came_from[current] path.append(start) path.reverse() return path for neighbor in graph[current]: tentative_g_score g_score[current] 1 if tentative_g_score g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g_score f_score[neighbor] tentative_g_score heuristic(neighbor, goal) if neighbor not in [i[1] for i in open_set]: heapq.heappush(open_set, (f_score[neighbor], neighbor)) return None这段代码中heuristic函数就是用来计算估计代价$h(n)$的采用的是曼哈顿距离。astar函数则实现了整个A星搜索的过程open_set使用优先队列来存储待扩展节点按照$f$值从小到大排序。通过不断扩展节点直到找到目标节点或者遍历完所有可到达节点。改进A星算法升级的策略改进A星算法往往针对A星算法的某些不足进行优化。比如在传统A星算法中$h(n)$的估计可能不够精准导致搜索效率不高。改进的方法可能是对启发函数进行优化让它更加贴近实际情况。A星 改进A星 新A星算法 路径规划 放在一张图上 对比 三天对比线在一张图 避障假设我们采用一种动态权重的启发函数def improved_heuristic(a, b, dynamic_weight): return dynamic_weight * (abs(a[0] - b[0]) abs(a[1] - b[1])) def improved_astar(graph, start, goal, dynamic_weight): open_set [] heapq.heappush(open_set, (0, start)) came_from {} g_score {node: float(inf) for node in graph.keys()} g_score[start] 0 f_score {node: float(inf) for node in graph.keys()} f_score[start] improved_heuristic(start, goal, dynamic_weight) while open_set: _, current heapq.heappop(open_set) if current goal: path [] while current in came_from: path.append(current) current came_from[current] path.append(start) path.reverse() return path for neighbor in graph[current]: tentative_g_score g_score[current] 1 if tentative_g_score g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g_score f_score[neighbor] tentative_g_score improved_heuristic(neighbor, goal, dynamic_weight) if neighbor not in [i[1] for i in open_set]: heapq.heappush(open_set, (f_score[neighbor], neighbor)) return None这里的improvedheuristic函数通过引入一个动态权重dynamicweight可以根据实际场景调整启发函数的影响程度使得搜索过程更加灵活高效在避障场景下可能更快地找到路径。新A星算法崭露头角的新秀新A星算法可能是基于一些全新的理念或者结合其他技术产生的。例如结合机器学习的方法来预学习地图的特征从而优化路径搜索。# 简单模拟新A星结合机器学习预学习的情况 class NewAStar: def __init__(self, learned_model): self.learned_model learned_model def new_heuristic(self, a, b): # 根据预学习模型得到启发值 learned_value self.learned_model.predict([a, b]) return learned_value def new_astar(self, graph, start, goal): open_set [] heapq.heappush(open_set, (0, start)) came_from {} g_score {node: float(inf) for node in graph.keys()} g_score[start] 0 f_score {node: float(inf) for node in graph.keys()} f_score[start] self.new_heuristic(start, goal) while open_set: _, current heapq.heappop(open_set) if current goal: path [] while current in came_from: path.append(current) current came_from[current] path.append(start) path.reverse() return path for neighbor in graph[current]: tentative_g_score g_score[current] 1 if tentative_g_score g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g_score f_score[neighbor] tentative_g_score self.new_heuristic(neighbor, goal) if neighbor not in [i[1] for i in open_set]: heapq.heappush(open_set, (f_score[neighbor], neighbor)) return None这里假设learnedmodel是一个已经预学习好的模型通过newheuristic函数来给出更符合实际情况的启发值进而引导搜索过程。对比三天的“较量”为了直观地对比这三种算法我们在一张带有障碍物的地图上进行测试并连续测试三天记录它们每天找到路径的情况。通过绘图工具比如Python的Matplotlib库我们可以将三种算法每天找到的路径绘制在同一张图上。import matplotlib.pyplot as plt # 假设已经得到三种算法每天的路径结果 astar_paths [astar(graph, start, goal) for _ in range(3)] improved_astar_paths [improved_astar(graph, start, goal, 1.5) for _ in range(3)] new_astar_paths [NewAStar(learned_model).new_astar(graph, start, goal) for _ in range(3)] colors [r, g, b] labels [A星算法, 改进A星算法, 新A星算法] for i, paths in enumerate([astar_paths, improved_astar_paths, new_astar_paths]): for j, path in enumerate(paths): x [node[0] for node in path] y [node[1] for node in path] plt.plot(x, y, colorcolors[i], labellabels[i] if j 0 else ) plt.legend() plt.show()从这张图中可以明显看出A星算法找到的路径相对比较“规矩”按照传统的评估方式进行搜索。改进A星算法由于调整了启发函数路径可能更加“直接”一些避开障碍物的同时更高效地接近目标。而新A星算法因为结合了预学习等新技术它的路径有可能在某些情况下展现出独特的优势比如能够更好地利用地图的隐藏特征来规划路径。在避障场景下三种算法各有千秋。A星算法作为经典算法稳定性强改进A星算法通过优化启发函数提升了效率新A星算法借助新技术带来了更多可能性。在实际应用中我们可以根据具体的场景和需求来选择最合适的路径规划算法。