Python中如何实现A*启发式搜索算法进行查找
A*算法是一种基于启发式搜索的路径规划算法，它可以用于解决迷宫问题、游戏AI、机器人路径规划等问题。它的基本思想是利用估价函数来评估每个节点的代价，然后选择代价最小的节点进行拓展，直到找到目标节点或者无法继续拓展为止。
以下是Python中实现A*启发式搜索算法进行查找的详细步骤：
- 定义节点类
在A*算法中，需要定义一个节点类来表示每个节点，其中节点需要包含以下信息：
- 父节点：用于回溯路径
- 坐标：表示节点在地图中的位置
- G值：从起点到当前节点的实际代价
- H值：从当前节点到终点的估计代价
- F值：G值和H值的和，表示从起点到终点经过该节点的总代价
节点类代码如下：
class Node: def __init__(self, parent=None, position=None): self.parent = parent self.position = position self.g = 0 self.h = 0 self.f = 0 def __eq__(self, other): return self.position == other.position
- 定义估价函数
在A*算法中，需要定义一个估价函数来评估每个节点的代价。估价函数应该返回该节点到终点的估计距离。常用的估价函数有曼哈顿距离、欧几里得距离和切比雪夫距离等。在本例中，我们使用曼哈顿距离作为估价函数。
曼哈顿距离的计算方式为：两点之间的曼哈顿距离 = 两点横坐标之差的绝对值 + 两点纵坐标之差的绝对值。
估价函数代码如下：
def manhattan_distance(start, end): return abs(start[0] - end[0]) + abs(start[1] - end[1])
- 定义A*算法函数
在A*算法中，需要定义一个函数来进行搜索。该函数需要接受起点和终点作为参数，返回一条从起点到终点的路径。
A*算法的基本思路如下：
- 将起点加入开启列表。
- 当开启列表不为空时，取出开启列表中F值最小的节点，将其加入关闭列表，同时将其所有可以到达的但未在开启列表中的节点加入开启列表，计算这些节点的G值和H值，更新节点的F值，并记录每个节点的父节点。
- 如果当前节点为终点，则返回路径（从当前节点回溯到起点的路径）。
- 如果开启列表为空，则无法到达终点，返回None。
A*算法函数代码如下：
def astar(maze, start, end): # 创建起点和终点节点 start_node = Node(None, start) start_node.g = start_node.h = start_node.f = 0 end_node = Node(None, end) end_node.g = end_node.h = end_node.f = 0 # 初始化开启列表和关闭列表 open_list = [] closed_list = [] # 将起点加入开启列表 open_list.append(start_node) # 开始搜索 while len(open_list) > 0: # 取出F值最小的节点 current_node = min(open_list, key=lambda node: node.f) # 将当前节点从开启列表中移除，并加入关闭列表 open_list.remove(current_node) closed_list.append(current_node) # 如果当前节点为终点，则返回路径 if current_node == end_node: path = [] while current_node is not None: path.append(current_node.position) current_node = current_node.parent return path[::-1] # 反转路径 # 计算当前节点所有可以到达的邻居节点的G值、H值和F值 for neighbor_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # 获取邻居节点的坐标 neighbor_x = current_node.position[0] + neighbor_position[0] neighbor_y = current_node.position[1] + neighbor_position[1] neighbor_position = (neighbor_x, neighbor_y) # 如果邻居节点不在地图范围内，则忽略该节点 if neighbor_x < 0 or neighbor_x >= len(maze) or neighbor_y < 0 or neighbor_y >= len(maze[0]): continue # 如果邻居节点是障碍物，则忽略该节点 if maze[neighbor_x][neighbor_y] == 1: continue # 如果邻居节点已经在关闭列表中，则忽略该节点 if any(neighbor_position == node.position for node in closed_list): continue # 计算邻居节点的G值、H值和F值 neighbor_node = Node(current_node, neighbor_position) neighbor_node.g = current_node.g + 1 neighbor_node.h = manhattan_distance(neighbor_position, end) neighbor_node.f = neighbor_node.g + neighbor_node.h # 如果邻居节点已经在开启列表中，则更新其G值和F值 if any(neighbor_position == node.position for node in open_list): open_node = next(node for node in open_list if neighbor_position == node.position) if neighbor_node.g < open_node.g: open_node.g = neighbor_node.g open_node.f = neighbor_node.f open_node.parent = current_node else: open_list.append(neighbor_node) # 开启列表为空，无法到达终点，返回None return None
- 实现代码演示
现在我们可以使用一个简单的迷宫地图来测试我们的A算法。我们可以将地图定义为一个二维数组，其中0表示可通行，1表示障碍物。请注意，我们的A算法函数接受的坐标不是以x,y的形式表示的，而是以行列的形式表示的。
代码演示如下：
def main(): maze = [[0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0]] start = (0, 0) end = (4, 6) path = astar(maze, start, end) print(path) # 输出结果为：[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6)]
当给定起点和终点之后，上述代码将计算最短路径，并返回从起点到终点的路径。在本例中，从(0,0)到(4,6)的最短路径为[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6)]。
相关文章