无锡网站建设seo,网站开发的步骤实训内容,宝山专业网站建设,外企网站建设#x1f4e2;本篇文章是博主人工智能学习以及算法研究时#xff0c;用于个人学习、研究或者欣赏使用#xff0c;并基于博主对相关等领域的一些理解而记录的学习摘录和笔记#xff0c;若有不当和侵权之处#xff0c;指出后将会立即改正#xff0c;还望谅解。文章分类在本篇文章是博主人工智能学习以及算法研究时用于个人学习、研究或者欣赏使用并基于博主对相关等领域的一些理解而记录的学习摘录和笔记若有不当和侵权之处指出后将会立即改正还望谅解。文章分类在启发式算法专栏 【人工智能】- 【启发式算法】6---《一学就会A*算法详细介绍Python》 一学就会A*算法详细介绍Python
目录 A*算法介绍
A*算法的核心概念
A*算法的特点
A*算法示例迷宫
执行步骤
第1步初始化
第2步扩展当前节点起始节点
第3步选择下一个节点最低 f(n)
第4步处理当前节点 (0,1)
第5步继续探索
重点说明
最终结果
A*算法与其他相关算法的比较
[Python] A*算法实现
[Results] 运行结果
[Notice] 注意事项
适用场景
实现建议 A*算法介绍 A*算法是一种高效的路径搜索算法广泛应用于人工智能、机器人技术、游戏开发等领域。它由Peter Hart、Nils Nilsson和Bertram Raphael于1968年首次提出。A算法结合了Dijkstra算法的系统性搜索和启发式搜索的优点通过使用启发式函数来减少搜索空间同时保证找到最短路径。
A*算法的核心概念 A*算法是一种最佳优先搜索算法它通过以下三个关键函数来评估路径 g(n)从起点到当前节点的实际代价。 h(n)从当前节点到目标节点的启发式估算代价。 f(n) g(n) h(n)通过当前节点到达目标的总估算代价。 在每次迭代中A*算法会选择具有最低f(n)值的节点进行扩展并更新其邻居节点的代价。如果邻居节点的试探性代价低于之前记录的值则会更新该节点的代价并将其添加到开放集合中。这一过程会持续进行直到找到目标节点或确定路径不存在。
A*算法的特点 最优性当使用可接受的启发式函数时A*算法能够找到最短路径。 效率启发式函数的引导使得A*算法比Dijkstra算法探索更少的节点。 灵活性启发式函数可以根据不同场景进行定制。 完整性如果存在解决方案A*算法将找到它。 A*算法示例迷宫
以下是使用A*算法在一个示例迷宫中寻找路径的详细步骤说明
假设有以下10x10的迷宫
S 0 0 0 0 0 0 0 0 0
0 1 1 0 1 1 0 1 1 0
0 1 0 0 0 0 0 0 1 0
0 1 1 1 1 1 0 1 1 0
0 0 0 0 1 0 0 0 0 0
0 1 1 0 1 1 1 1 1 0
0 1 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 E
其中S 表示起点 (0,0)E 表示终点 (9,9)0 表示可以通行的路径1 表示障碍物.
执行步骤
第1步初始化 起始节点(0,0)初始化其 g(n)0h(n) 由直线距离计算f(n)013.41613.416。 开放列表未被选择的节点。 封闭列表已被选择的节点。 当前节点起始节点。
第2步扩展当前节点起始节点 邻节点(0,1), (1,0)。 检查范围确保邻节点在迷宫范围内。 障碍物检查(0,1) 是 0(1,0) 是 0。 计算邻节点g(n) (0,1)起始节点的 g(n)011。 (1,0)起始节点的 g(n)011。 计算邻节点h(n) (0,1) 的 h(n)sqrt((9-0)^2 (9-1)^2) sqrt(8164)11.401。 (1,0) 的 h(n)sqrt((9-1)^2 (9-0)^2)sqrt(6481)11.401。 计算邻节点f(n) (0,1) 的 f(n)111.40112.401。 (1,0) 的 f(n)111.40112.401。 在开放列表中添加邻节点 (0,1) 和 (1,0) 添加到开放列表。
第3步选择下一个节点最低 f(n) 开放列表中有 (0,1) 和 (1,0)它们的 f(n) 都是 12.401。可以选择其中任意一个 选择 (0,1) 作为当前节点。
第4步处理当前节点 (0,1) 邻节点(0,0)起点已在封闭列表(0,2)(1,1)。 障碍物检查 (0,2) 是 0。 (1,1) 是 1障碍物。 生成有效邻节点(0,2)。 计算(0,2) 的 g(n) 来自 (0,1)g(n)112。 计算(0,2) 的 h(n): sqrt((9-0)^2 (9-2)^2) sqrt(8149)10.630。 计算 (0,2) 的 f(n): 210.63012.630。 将 (0,2) 添加到开放列表: 开放列表现在包含 (1,0), (0,2)。
第5步继续探索 重复步骤选择开放列表中 f(n) 最低的节点继续扩展并更新邻节点的 g(h,f) 值直到到达目标节点 (9,9)。
重点说明 扩展当前节点每次从开放列表中取出 f(n) 最低的节点生成其邻节点。 更新邻节点信息 如果邻节点未被访问过计算其 g(h,f) 并加入开放列表。 如果邻节点已在开放列表中需要比较新的 g(n) 是否更小。如果更小更新父节点和 g(n)。 终止条件 当前节点是目标节点回溯路径。 开放列表为空没有路径。
最终结果 经过反复的节点扩展和评估A* 算法最终找到从起点 (0,0) 到终点 (9,9) 的最短路径。路径将避免迷宫中的所有障碍物确保每一步都是经过成本最低的选择。 A*算法与其他相关算法的比较
算法与A*的关系关键差异优缺点Dijkstra算法A*是Dijkstra算法的扩展A*使用f(n)g(n)h(n)Dijkstra仅使用g(n)A*在有启发式函数时性能更好Dijkstra无需启发式函数Bellman-Ford算法基于边的松弛Bellman-Ford支持负边权重A*通常更快Bellman-Ford适用于有负权重的图A*需要启发式函数Floyd-Warshall算法解决所有点对最短路径问题Floyd-Warshall使用动态规划A*是增量搜索Floyd-Warshall适合密集图A*适合实时路径搜索 [Python] A*算法实现 项目代码我已经放入下面链接里面 A*算法实现 若是下面代码复现困难或者有问题也欢迎评论区留言。 《A*算法实现》时间2025.02.27环境迷宫作者不去幼儿园import heapq
import matplotlib.pyplot as plt
import numpy as npclass Node:节点类表示搜索树中的每一个点。def __init__(self, parentNone, positionNone):self.parent parent # 该节点的父节点self.position position # 节点在迷宫中的坐标位置self.g 0 # G值从起点到当前节点的成本self.h 0 # H值当前节点到目标点的估计成本self.f 0 # F值G值与H值的和即节点的总评估成本# 比较两个节点位置是否相同def __eq__(self, other):return self.position other.position# 定义小于操作以便在优先队列中进行比较def __lt__(self, other):return self.f other.fdef astar(maze, start, end):A*算法实现用于在迷宫中找到从起点到终点的最短路径。start_node Node(None, start) # 创建起始节点end_node Node(None, end) # 创建终点节点open_list [] # 开放列表用于存储待访问的节点closed_list [] # 封闭列表用于存储已访问的节点heapq.heappush(open_list, (start_node.f, start_node)) # 将起始节点添加到开放列表while open_list:current_node heapq.heappop(open_list)[1] # 弹出并返回开放列表中 f 值最小的节点closed_list.append(current_node) # 将当前节点添加到封闭列表if current_node end_node: # 如果当前节点是目标节点则回溯路径path []while current_node:path.append(current_node.position)current_node current_node.parentreturn path[::-1] # 返回反向路径即从起点到终点的路径(x, y) current_node.positionneighbors [(x-1, y), (x1, y), (x, y-1), (x, y1)] # 获取当前节点周围的相邻节点for next in neighbors:if 0 next[0] maze.shape[0] and 0 next[1] maze.shape[1]: # 确保相邻节点在迷宫范围内if maze[next[0], next[1]] 1: # 如果相邻节点是障碍物跳过continueneighbor Node(current_node, next) # 创建相邻节点if neighbor in closed_list: # 如果相邻节点已在封闭列表中跳过不处理continueneighbor.g current_node.g 1 # 计算相邻节点的 G 值neighbor.h ((end_node.position[0] - next[0]) ** 2) ((end_node.position[1] - next[1]) ** 2) # 计算 H 值neighbor.f neighbor.g neighbor.h # 计算 F 值if add_to_open(open_list, neighbor): # 如果相邻节点的新 F 值较小则将其添加到开放列表heapq.heappush(open_list, (neighbor.f, neighbor))return None # 如果没有找到路径返回 Nonedef add_to_open(open_list, neighbor):检查并添加节点到开放列表。for node in open_list:if neighbor node[1] and neighbor.g node[1].g:return Falsereturn True # 如果不存在则返回 True 以便添加该节点到开放列表def visualize_path(maze, path, start, end):将找到的路径可视化在迷宫上。maze_copy np.array(maze)for step in path:maze_copy[step] 0.5 # 标记路径上的点plt.figure(figsize(10, 10))plt.imshow(maze_copy, cmaphot, interpolationnearest)path_x [p[1] for p in path] # 列坐标path_y [p[0] for p in path] # 行坐标plt.plot(path_x, path_y, colororange, linewidth2)start_x, start_y start[1], start[0]end_x, end_y end[1], end[0]plt.scatter([start_x], [start_y], colorgreen, s100, labelStart, zorder5) # 起点为绿色圆点plt.scatter([end_x], [end_y], colorred, s100, labelEnd, zorder5) # 终点为红色圆点plt.legend()plt.show()
# 设定迷宫的尺寸
maze_size 100
maze np.zeros((maze_size, maze_size))
obstacle_blocks [(10, 10, 20, 20), # (y起始, x起始, 高度, 宽度)(30, 40, 20, 30),(60, 20, 15, 10),(80, 50, 10, 45),
]
for y_start, x_start, height, width in obstacle_blocks:maze[y_start:y_startheight, x_start:x_startwidth] 1
start (0, 0)
end (92, 93)
maze[start] 0
maze[end] 0
path astar(maze, start, end)
if path:print(路径已找到, path)visualize_path(maze, path, start, end)
else:print(没有找到路径。) [Results] 运行结果 [Notice] 注意事项
# 环境配置
Python 3.11.5
torch 2.1.0
torchvision 0.16.0
gym 0.26.2 由于博文主要为了介绍相关算法的原理和应用的方法缺乏对于实际效果的关注算法可能在上述环境中的效果不佳或者无法运行一是算法不适配上述环境二是算法未调参和优化三是没有呈现完整的代码四是等等。上述代码用于了解和学习算法足够了但若是想直接将上面代码应用于实际项目中还需要进行修改。 适用场景
A*算法最适合以下场景 单源单目标路径搜索。 可以提供领域特定的启发式函数。 需要最优解。 有足够的内存来维护开放/关闭集合。
主要应用场景 迷宫寻路在游戏开发中A*算法可以用来为游戏角色找到从起点到终点的最短路径例如在迷宫类游戏中角色需要绕过障碍物尽快到达目标。 机器人路径规划在机器人领域A*算法可用于规划机器人在复杂环境中的移动路径帮助其避开障碍物并找到到达目标位置的最佳路线。 地图导航在 GPS 导航系统或地图应用中A*算法可以计算两点之间的最短路径考虑道路长度、交通状况等多种因素为用户提供最优的行驶路线建议。 实现建议 使用优先队列如二叉堆或斐波那契堆快速选择节点。 根据图的大小选择合适的数据结构。 设计并验证有效的启发式函数。
算法优点 寻找最短路径无论是二维平面还是三维空间A*算法都能够有效地在复杂的环境图中找到从起点到终点的最短路径尤其是在具有障碍物和多重路径选择的情况下。 优化效率相比传统的广度优先搜索和深度优先搜索A*算法通过结合启发式估计和实际路径成本能够更高效地探索可能的路径减少不必要的计算大大提升了路径寻找的效率。 适应复杂环境A*算法能够灵活地处理各种环境变化如新增障碍物、改变目标位置等只需重新计算路径即可无需对整个地图进行重新规划。
实现效果 准确性A*算法能够精确地找到最优路径确保路径的总成本如距离、时间等最小对于大多数场景来说其结果都是全局最优的。 实时性在处理复杂地图时A*算法能够在较短时间内完成路径规划满足实时性要求特别是在一些动态环境如即时战略游戏或动态交通导航中。 可视化通过可视化工具可以清晰地看到 A*算法的搜索过程路径是如何被逐步探索和确定的这对于调试和理解算法的工作原理非常有帮助。 更多启发式算法文章请前往【启发式算法】专栏 博客都是给自己看的笔记如有误导深表抱歉。文章若有不当和不正确之处还望理解与指出。由于部分文字、图片等来源于互联网无法核实真实出处如涉及相关争议请联系博主删除。如有错误、疑问和侵权欢迎评论留言联系作者或者添加VXRainbook_2联系作者。✨
