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

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

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

在这里插入图片描述

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

A*算法的基本原理

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

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

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

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

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

启发式函数的选择

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

  1. 可接受性(Admissibility):启发式函数永远不应高估从当前节点到目标节点的真实代价。

  2. 一致性(Consistency):对于每个节点 ( n ) 和它的每个相邻节点 ( m ),启发式函数应满足:
    在这里插入图片描述

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

常见的启发式函数包括:

  • 曼哈顿距离:在网格地图中,适用于只能上下左右移动的场景:
    在这里插入图片描述

  • 欧几里得距离:适用于可以在任意方向移动的场景:
    在这里插入图片描述

A*算法的步骤

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

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}")

代码解读

  1. 节点类Node 类表示搜索中的每个节点,包含位置、父节点、实际代价、启发式代价和总估计代价。

  2. 启发式函数heuristic 函数计算曼哈顿距离,作为启发式代价。

  3. A*搜索函数a_star_search 实现了A*算法的核心逻辑,包括初始化、循环处理、生成邻居节点、计算代价等。

  4. 示例网格:示例网格中,0表示可通行的路径,1表示障碍物。

  5. 路径输出:程序输出从起点到终点的路径。

A*算法的复杂度

A算法的时间复杂度和空间复杂度在最坏情况下都是在这里插入图片描述
,其中 b 是分支因子(每个节点的子节点数), d 是解的深度。由于A
算法在搜索中保持了开启列表和关闭列表,因此其空间复杂度较高,特别是在大规模问题上。

A*算法的优缺点

优点
  1. 高效性:A*算法通过使用启发式函数引导搜索,可以快速找到最优解。
  2. 灵活性:启发式函数可以根据具体问题的特点进行调整,灵活应对不同的场景。
  3. 保证最优性:只要启发式函数是可接受的,A*算法保证找到最优路径。
缺点
  1. 内存消耗:由于需要维护开启列表和关闭列表,A*算法在处理大规模问题时可能会

消耗大量内存。

  1. 启发式函数的选择:选择合适的启发式函数至关重要,错误的选择可能导致效率降低。

A*算法的应用场景

  1. 路径规划:在地图上为机器人或游戏角色寻找最短路径。
  2. 游戏开发:用于非玩家角色(NPC)的智能移动。
  3. 网络路由:寻找网络中最优数据传输路径。
  4. 物流与运输:优化配送路径和调度问题。

总结

A* 搜索算法是一种高效的图形搜索算法,广泛应用于路径寻找和优化问题。通过结合实际代价和启发式代价,A*算法能够快速找到最优路径。虽然在大规模问题上存在内存消耗等问题,但其灵活性和保证最优性的特性使其在众多领域中仍然具有广泛的应用前景。

在这里插入图片描述


http://www.mrgr.cn/news/62396.html

相关文章:

  • Spring Boot 与 EasyExcel 携手:复杂 Excel 表格高效导入导出实战
  • Python | Leetcode Python题解之第521题最长特殊序列I
  • 小白从零开始配置pytorch环境
  • 重磅新品丨Fortinet 发布 Lacework FortiCNAPP,强化云原生应用安全
  • Linux中gcc的使用
  • 函数式接口与回调函数实践
  • 【Docker知识】Docker进阶-容器镜像深度解读
  • AIGC学习笔记(4)——AI大模型开发工程师
  • 高效集成:SQLServer对接MySQL的实战案例
  • NR 5G 系统信息深度解析
  • 使用python提取日志里面的role_id、vip字段的值,(vip字段可能为空或者缺失,此时需要给默认值0):
  • 个人在ssm框架整合时犯的错误
  • 只尊重不教育,只筛选不改变
  • Threejs渲染3D字体介绍
  • gradio RuntimeError: async generator raised StopAsyncIteration
  • 阿里巴巴API返回值全解析:轻松掌握1688店铺商品信息
  • 【系统设计】高效的分布式系统:使用 Spring Boot 和 Kafka 实现 Saga 模式
  • SAP ABAP开发学习——第一代增强(包含增强演示)
  • BOE(京东方)2024年前三季度净利润三位数增长 “屏之物联”引领企业高质发展
  • java-数据结构
  • C++学习:类和对象(二)
  • AI时代,哪种人更被需要?
  • 【传知代码】自动化细胞核分割与特征分析
  • flowable7.1.0功能
  • 单例 C++ 懒汉+恶汉
  • 前端面试题21 | 了解过媒体查询吗?它有哪些应用场景?