当前位置：首页 > news >正文

人工智能算法之A*搜索算法

news 2024/10/31 12:00:23

人工智能算法之A*搜索算法

在这里插入图片描述

A搜索算法是一种广泛使用的图形搜索算法，适用于路径寻找和图形遍历。它结合了最佳优先搜索和Dijkstra算法的优点，通过利用启发式信息来引导搜索过程，能够高效地找到从起点到目标点的最优路径。A算法在很多应用场景中表现出色，包括游戏开发、机器人导航和地图路由等。

A*算法的基本原理

A*算法通过维护一个优先队列来管理待处理的节点。每个节点的代价由两部分组成：

实际代价 ( g(n) )：从起点到当前节点 ( n ) 的实际代价。
启发式代价 ( h(n) )：从当前节点 ( n ) 到目标节点的估算代价。

A*算法的核心思想是使用代价函数 ( f(n) ) 来评估节点 ( n )：
在这里插入图片描述

f(n) 表示从起点到目标节点的总估计代价。
g(n) 是实际成本。
h(n) 是从当前节点到目标节点的启发式估算。

A*算法通过不断扩展代价函数最小的节点，逐步找到目标节点。

启发式函数的选择

启发式函数 ( h(n) ) 是A*算法的关键，它决定了算法的效率和效果。一个有效的启发式函数应满足以下条件：

可接受性（Admissibility）：启发式函数永远不应高估从当前节点到目标节点的真实代价。
一致性（Consistency）：对于每个节点 ( n ) 和它的每个相邻节点 ( m )，启发式函数应满足：

其中 ( c(n, m) ) 是从 ( n ) 到 ( m ) 的实际代价。

常见的启发式函数包括：

曼哈顿距离：在网格地图中，适用于只能上下左右移动的场景：
欧几里得距离：适用于可以在任意方向移动的场景：

A*算法的步骤

初始化：创建一个开启列表（Open List）和关闭列表（Closed List）。将起点放入开启列表。
循环处理节点：
- 从开启列表中选择代价函数 f(n) 最小的节点 n 。
- 如果 n 是目标节点，则找到路径，算法结束。
- 将 n 移动到关闭列表。
- 对于每个相邻节点 m ：
  - 如果 m 在关闭列表中，跳过。
  - 计算 g(m) 和 f(m) 。
  - 如果 m 不在开启列表中，添加到开启列表。
路径重建：从目标节点反向重建路径。

A*算法的Python实现

下面的代码实现了A*算法在一个简单网格上的路径寻找，假设可以上下左右移动。

Python代码实现

import heapqclass Node:def __init__(self, position, parent=None):self.position = position  # 节点位置 (x, y)self.parent = parent  # 父节点self.g = 0  # 从起点到当前节点的实际代价self.h = 0  # 从当前节点到目标节点的启发式代价self.f = 0  # 总的估计代价 f(n) = g(n) + h(n)def __eq__(self, other):return self.position == other.positiondef __lt__(self, other):return self.f < other.fdef heuristic(node1, node2):""" 计算曼哈顿距离作为启发式函数 """return abs(node1.position[0] - node2.position[0]) + abs(node1.position[1] - node2.position[1])def a_star_search(start, goal, grid):open_list = []closed_list = set()start_node = Node(start)goal_node = Node(goal)# 将起点加入开启列表heapq.heappush(open_list, start_node)while open_list:# 取出f值最小的节点current_node = heapq.heappop(open_list)# 如果达到目标节点if current_node == goal_node:path = []while current_node:path.append(current_node.position)current_node = current_node.parentreturn path[::-1]  # 返回反向路径closed_list.add(current_node)# 生成邻居节点neighbors = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上、右、下、左for new_position in neighbors:node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])# 检查是否在网格范围内if (node_position[0] > (len(grid) - 1) or node_position[0] < 0 ornode_position[1] > (len(grid[len(grid) - 1]) - 1) or node_position[1] < 0):continue# 检查是否为障碍物if grid[node_position[0]][node_position[1]] != 0:continueneighbor_node = Node(node_position, current_node)if neighbor_node in closed_list:continue# 计算g, h, f值neighbor_node.g = current_node.g + 1neighbor_node.h = heuristic(neighbor_node, goal_node)neighbor_node.f = neighbor_node.g + neighbor_node.h# 检查邻居是否已经在开启列表中if any(neighbor_node == open_node and neighbor_node.g > open_node.g for open_node in open_list):continue# 将邻居添加到开启列表heapq.heappush(open_list, neighbor_node)return None  # 没有找到路径# 示例网格（0表示可通行，1表示障碍物）
grid = [[0, 0, 0, 0, 0],[0, 1, 1, 1, 0],[0, 0, 0, 0, 0],[0, 1, 1, 1, 0],[0, 0, 0, 0, 0]
]start = (0, 0)  # 起点
goal = (4, 4)   # 终点# 执行A*搜索
path = a_star_search(start, goal, grid)
print(f"Path from {start} to {goal}: {path}")