A*算法详解【附算法代码与运行结果】-海口c网

A*算法详解【附算法代码与运行结果】

article/2025/8/15 3:32:00

算法背景

A*算法是一种在图形平面上，有多个路径中寻找一条从起始点到目标点的最短遍历路径的算法。它属于启发式搜索算法（Heuristic Search Algorithm），因为它使用启发式方法来计算图中的节点，从而减少实际计算的节点数量，提高搜索效率。

基本原理

A*算法的核心思想是结合了Dijkstra算法和Best-First-Search算法的特点。它使用一个估价函数f(n) = g(n) + h(n)来估算从起始点到目标点的总代价，其中g(n)表示从起始点到当前节点的代价，h(n)是从当前节点到目标点的启发式估计代价。

A*算法通过扩展路径代价最小的节点来寻找目标点，它保证了如果h(n)的估计值是准确的，那么找到的路径也是最短的。相比于Dijkstra算法中会一直遍历选择距离较近的点收录，在A*算法中增加启发式函数h(n)会减少收录的栅格数目，加快算法的导向终点的速度。

算法流程

相比于Dijkstra算法，就多了一个启发式函数h(n)。

在实际应用中需权衡速度和最优性。启发式函数取的大的话可以快速找到终点。但可能会损失最优性，所以保证A*算法最优性需要加上下面这个条件，即启发项小于等于最优的那条路径：

h(n) <=*h(n)

open list表示存放从当前节点到节点已经更新过的路径；

closed list表示截至目前到起点最短路径的节点进行收录。

那么针对下面这个图的存储流程应如下：

open list：2(1+6) 3(5+0) # 2(1+6)表示节点2到起点的距离为1，加上启发项为6

closed list：1(0)

open list：2(1+6)

closed list：1(0) 3(5+0) #实际上上面的路径理论上会更短，丧失了最优性

案例实操

对起点[-5，-5],终点 [50, 50]在边长范围为[-10，60]的正方形进行路径规划，其中设置了两个墙体作为障碍物，对比A*算法与Dijkstra算法。

【实验代码】


import mathimport matplotlib.pyplot as pltshow_animation = Trueclass AStarPlanner:def __init__(self, ox, oy, resolution, rr):"""Initialize grid map for a star planningox: x position list of Obstacles [m]oy: y position list of Obstacles [m]resolution: grid resolution [m]rr: robot radius[m]"""self.resolution = resolutionself.rr = rrself.min_x, self.min_y = 0, 0self.max_x, self.max_y = 0, 0self.obstacle_map = Noneself.x_width, self.y_width = 0, 0self.motion = self.get_motion_model()self.calc_obstacle_map(ox, oy)class Node:def __init__(self, x, y, cost, parent_index):self.x = x  # index of gridself.y = y  # index of gridself.cost = costself.parent_index = parent_indexdef __str__(self):return str(self.x) + "," + str(self.y) + "," + str(self.cost) + "," + str(self.parent_index)def planning(self, sx, sy, gx, gy):"""A star path searchinput:s_x: start x position [m]s_y: start y position [m]gx: goal x position [m]gy: goal y position [m]output:rx: x position list of the final pathry: y position list of the final path"""start_node = self.Node(self.calc_xy_index(sx, self.min_x),self.calc_xy_index(sy, self.min_y), 0.0, -1)goal_node = self.Node(self.calc_xy_index(gx, self.min_x),self.calc_xy_index(gy, self.min_y), 0.0, -1)open_set, closed_set = dict(), dict()open_set[self.calc_grid_index(start_node)] = start_nodewhile 1:if len(open_set) == 0:print("Open set is empty..")break# 选择扩展点 f(n) = g(n) 即cost+ h(n)即启发式函数calc_heuristic，计算goal_node终点与open_set里面的点c_id = min(open_set,key=lambda o: open_set[o].cost + self.calc_heuristic(goal_node,open_set[o]))current = open_set[c_id]# show graphif show_animation:  # pragma: no coverplt.plot(self.calc_grid_position(current.x, self.min_x),self.calc_grid_position(current.y, self.min_y), "xc")# for stopping simulation with the esc key.plt.gcf().canvas.mpl_connect('key_release_event',lambda event: [exit(0) if event.key == 'escape' else None])if len(closed_set.keys()) % 10 == 0:plt.pause(0.001)if current.x == goal_node.x and current.y == goal_node.y:print("Find goal")goal_node.parent_index = current.parent_indexgoal_node.cost = current.costbreak# Remove the item from the open setdel open_set[c_id]# Add it to the closed setclosed_set[c_id] = current# expand_grid search grid based on motion modelfor i, _ in enumerate(self.motion):node = self.Node(current.x + self.motion[i][0],current.y + self.motion[i][1],current.cost + self.motion[i][2], c_id)n_id = self.calc_grid_index(node)# If the node is not safe, do nothingif not self.verify_node(node):continueif n_id in closed_set:continueif n_id not in open_set:open_set[n_id] = node  # discovered a new nodeelse:if open_set[n_id].cost > node.cost:# This path is the best until now. record itopen_set[n_id] = noderx, ry = self.calc_final_path(goal_node, closed_set)return rx, rydef calc_final_path(self, goal_node, closed_set):# generate final courserx, ry = [self.calc_grid_position(goal_node.x, self.min_x)], [self.calc_grid_position(goal_node.y, self.min_y)]parent_index = goal_node.parent_indexwhile parent_index != -1:n = closed_set[parent_index]rx.append(self.calc_grid_position(n.x, self.min_x))ry.append(self.calc_grid_position(n.y, self.min_y))parent_index = n.parent_indexreturn rx, ry@staticmethoddef calc_heuristic(n1, n2):#计算两个点之间的距离w = 1.0  # 权重weight of heuristic，假设有多个启发式函数可以设置不同权重d = w * math.hypot(n1.x - n2.x, n1.y - n2.y)return ddef calc_grid_position(self, index, min_position):"""calc grid position:param index::param min_position::return:"""pos = index * self.resolution + min_positionreturn posdef calc_xy_index(self, position, min_pos):return round((position - min_pos) / self.resolution)def calc_grid_index(self, node):return node.y * self.x_width + node.xdef verify_node(self, node):px = self.calc_grid_position(node.x, self.min_x)py = self.calc_grid_position(node.y, self.min_y)if px < self.min_x:return Falseelif py < self.min_y:return Falseelif px >= self.max_x:return Falseelif py >= self.max_y:return False# collision checkif self.obstacle_map[node.x][node.y]:return Falsereturn Truedef calc_obstacle_map(self, ox, oy):self.min_x = round(min(ox))self.min_y = round(min(oy))self.max_x = round(max(ox))self.max_y = round(max(oy))print("min_x:", self.min_x)print("min_y:", self.min_y)print("max_x:", self.max_x)print("max_y:", self.max_y)self.x_width = round((self.max_x - self.min_x) / self.resolution)self.y_width = round((self.max_y - self.min_y) / self.resolution)print("x_width:", self.x_width)print("y_width:", self.y_width)# obstacle map generationself.obstacle_map = [[False for _ in range(self.y_width)]for _ in range(self.x_width)]for ix in range(self.x_width):x = self.calc_grid_position(ix, self.min_x)for iy in range(self.y_width):y = self.calc_grid_position(iy, self.min_y)for iox, ioy in zip(ox, oy):d = math.hypot(iox - x, ioy - y)if d <= self.rr:self.obstacle_map[ix][iy] = Truebreak@staticmethoddef get_motion_model():# dx, dy, costmotion = [[1, 0, 1],[0, 1, 1],[-1, 0, 1],[0, -1, 1],[-1, -1, math.sqrt(2)],[-1, 1, math.sqrt(2)],[1, -1, math.sqrt(2)],[1, 1, math.sqrt(2)]]return motiondef main():print(__file__ + " start!!")# start and goal positionsx = -5.0  # [m]sy = -5.0  # [m]gx = 50.0  # [m]gy = 50.0  # [m]grid_size = 2.0  # [m]robot_radius = 1.0  # [m]# set obstacle positionsox, oy = [], []for i in range(-10, 60):ox.append(i)oy.append(-10.0)for i in range(-10, 60):ox.append(60.0)oy.append(i)for i in range(-10, 61):ox.append(i)oy.append(60.0)for i in range(-10, 61):ox.append(-10.0)oy.append(i)#两堵墙for i in range(-10, 40):ox.append(20.0)oy.append(i)for i in range(0, 40):ox.append(40.0)oy.append(60.0 - i)if show_animation:  # pragma: no coverplt.plot(ox, oy, ".k")plt.plot(sx, sy, "og")plt.plot(gx, gy, "xb")plt.grid(True)plt.axis("equal")a_star = AStarPlanner(ox, oy, grid_size, robot_radius)rx, ry = a_star.planning(sx, sy, gx, gy)if show_animation:  # pragma: no coverplt.plot(rx, ry, "-r")plt.pause(0.001)plt.show()if __name__ == '__main__':main()

【运行结果】