A*算法详解及Python实现
一、什么是A*算法?
A*(读作"A-star")算法是一种广泛使用的路径查找和图形遍历算法,它结合了Dijkstra算法的完备性和贪婪最佳优先搜索的高效性。A*算法通过使用启发式函数来估算从当前节点到目标节点的成本,从而智能地选择最有希望的路径进行探索。
二、A*算法核心概念
1. 估价函数 (f(n))
A*算法的核心是估价函数:f(n) = g(n) + h(n)
-
g(n): 从起点到当前节点n的实际路径成本
-
h(n): 从当前节点n到目标节点的启发式估计成本(即启发函数)
2. 启发函数 (h(n))
启发函数的选择对A*算法的性能有重要影响:
-
可接受性(Admissible): h(n)永远不会高估到目标的实际成本
-
一致性(Consistent): 对于每个节点n和其后继节点n',h(n) ≤ d(n, n') + h(n')
常用的启发函数:
-
曼哈顿距离(适用于网格中只能四方向移动)
-
欧几里得距离(直线距离)
-
切比雪夫距离(适用于可以八方向移动的网格)
三、A*算法步骤
-
初始化开放列表(open list)和关闭列表(closed list)
-
将起点加入开放列表
-
循环直到找到目标或开放列表为空:
a. 从开放列表中找到f值最小的节点作为当前节点
b. 将当前节点移到关闭列表
c. 对当前节点的每个相邻节点:
i. 如果不可通行或在关闭列表中,跳过
ii. 如果不在开放列表中,加入开放列表,计算其f,g,h值,记录父节点
iii. 如果在开放列表中,检查通过当前节点到它的路径是否更好(g值更小),如果是则更新 -
如果找到目标,从目标回溯父节点得到路径;如果开放列表为空且未找到目标,则无解
四、Python实现
下面是一个基于网格的A*算法实现:
import heapq
import math
from typing import List, Tuple, Dict, Optionalclass Node:def __init__(self, position: Tuple[int, int], parent=None):self.position = positionself.parent = parentself.g = 0 # 从起点到当前节点的实际距离self.h = 0 # 启发式估计到终点的距离self.f = 0 # f = g + hdef __eq__(self, other):return self.position == other.positiondef __lt__(self, other):return self.f < other.fdef __repr__(self):return f"Node({self.position}, g={self.g}, h={self.h}, f={self.f})"def heuristic(a: Tuple[int, int], b: Tuple[int, int]) -> float:"""欧几里得距离启发函数"""return math.sqrt((b[0] - a[0])**2 + (b[1] - a[1])**2)def a_star(grid: List[List[int]], start: Tuple[int, int], end: Tuple[int, int]) -> Optional[List[Tuple[int, int]]]:"""A*算法实现参数:grid: 二维数组,0表示可通行,1表示障碍物start: 起点坐标 (x, y)end: 终点坐标 (x, y)返回:路径列表(从起点到终点)或None(如果无解)"""# 创建起点和终点节点start_node = Node(start)end_node = Node(end)# 初始化开放列表和关闭列表open_list = []closed_list = set()# 将起点加入开放列表heapq.heappush(open_list, start_node)# 定义可能的移动方向(8方向)directions = [(-1, -1), (-1, 0), (-1, 1),(0, -1), (0, 1),(1, -1), (1, 0), (1, 1)]# 网格的行列数rows = len(grid)cols = len(grid[0]) if rows > 0 else 0while open_list:# 获取f值最小的节点current_node = heapq.heappop(open_list)# 如果到达终点,回溯路径if current_node == end_node:path = []current = current_nodewhile current is not None:path.append(current.position)current = current.parentreturn path[::-1] # 反转路径,从起点到终点# 将当前节点加入关闭列表closed_list.add(current_node.position)# 检查所有相邻节点for direction in directions:# 计算相邻节点位置node_position = (current_node.position[0] + direction[0], current_node.position[1] + direction[1])# 确保在网格范围内if (node_position[0] < 0 or node_position[0] >= rows ornode_position[1] < 0 or node_position[1] >= cols):continue# 确保可通行if grid[node_position[0]][node_position[1]] != 0:continue# 如果节点在关闭列表中,跳过if node_position in closed_list:continue# 创建新节点new_node = Node(node_position, current_node)# 计算g, h, f值# 对角线移动成本为sqrt(2),否则为1new_node.g = current_node.g + (1.414 if direction[0] and direction[1] else 1)new_node.h = heuristic(node_position, end)new_node.f = new_node.g + new_node.h# 如果节点已在开放列表中且g值更高,跳过for open_node in open_list:if new_node == open_node and new_node.g >= open_node.g:breakelse:heapq.heappush(open_list, new_node)# 开放列表为空但未找到路径return None# 示例使用
if __name__ == "__main__":# 0表示可通行,1表示障碍物grid = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]start = (0, 0)end = (9, 9)path = a_star(grid, start, end)if path:print("找到路径:")for step in path:print(step)else:print("未找到路径")
五、算法优化
-
优先队列优化:使用堆结构来高效获取f值最小的节点
-
哈希表优化:使用字典快速查找节点是否在开放列表中
-
启发函数选择:根据具体问题选择合适的启发函数
-
双向A*:同时从起点和终点开始搜索
-
跳点搜索(JPS):针对网格地图的优化算法
六、应用场景
A*算法广泛应用于:
-
游戏中的NPC路径规划
-
机器人导航
-
地图导航系统
-
拼图游戏解决方案
-
网络路由
七、总结
A算法是一种强大而高效的路径查找算法,通过合理选择启发函数,可以在保证找到最优解的同时显著提高搜索效率。本文提供的Python实现展示了A算法的核心思想,你可以根据具体需求进行调整和优化。
希望这篇博客能帮助你理解并实现A*算法!如果你有任何问题或建议,欢迎留言讨论。
相关文章:
A*算法详解及Python实现
一、什么是A*算法? A*(读作"A-star")算法是一种广泛使用的路径查找和图形遍历算法,它结合了Dijkstra算法的完备性和贪婪最佳优先搜索的高效性。A*算法通过使用启发式函数来估算从当前节点到目标节点的成本,…...
【C++】第九节—string类(中)——详解+代码示例
hello! 云边有个稻草人-CSDN博客 C_云边有个稻草人的博客-CSDN博客 菜鸡进化中。。。 目录 【补充】 二、string类里面的常用接口 1.resize 2.insert 3.assign 4.erase 5.replacefind 6.c_str 7.rfindsubstr 8.find_first_of、find_last_of、find_first…...
vite.config.js常用配置
vite 是一个基于 Vue3 单文件组件的非打包开发服务器,它做到了本地快速开发启动: 快速的冷启动,不需要等待打包操作; 即时的热模块更新,替换性能和模块数量的解耦让更新飞起; 真正的按需编译,不…...
【C++11(下)】—— 我与C++的不解之缘(三十二)
前言 随着 C11 的引入,现代 C 语言在语法层面上变得更加灵活、简洁。其中最受欢迎的新特性之一就是 lambda 表达式(Lambda Expression),它让我们可以在函数内部直接定义匿名函数。配合 std::function 包装器 使用,可以…...
李臻20242817_安全文件传输系统项目报告_第6周
安全文件传输系统项目报告(第 1 周) 1. 代码链接 Gitee 仓库地址:https://gitee.com/li-zhen1215/homework/tree/master/Secure-file 代码结构说明: project-root/├── src/ # 源代码目录│ ├── main.c # 主程序入口│ ├…...
使用SymPy求解矩阵微分方程
引言 在数学、物理、工程等领域,微分方程常常被用来描述系统的变化和动态过程。对于多变量系统或者多方程系统,矩阵微分方程是非常常见的,它可以用来描述如电路、控制系统、振动系统等复杂的动态行为。今天,我们将通过Python 中的 SymPy 库来求解矩阵微分方程,帮助大家轻…...
Flutter之用户输入网络数据缓存
目录: 1、处理用户输入1.1、按钮1.2、文本1.3、富文本1.4、TextField1.5、Form 2、复选框、Switch 和 Radio2.1、复选框2.2、Switch2.3、Radio 3、选择日期或时间4、滑动5、网络和数据6、本地缓存6.1、在本地内存中缓存数据 7、web端和Flutter样式控制对比7.1、文本…...
华为IP(4)
VRRP(虚拟路由冗余协议) 前言: 局域网中的用户终端通常采用配置一个默认网关的形式访问外部网络,如果默认网关设备发生故障,那么所有用户终端访问外部网络的流量将会中断。可以通过部署多个网关的方式来解决单点故障…...
蓝桥杯刷题周计划(第四周)
目录 前言题目一题目代码题解分析 题目二题目代码题解分析 题目三题目代码题解分析 题目四题目代码题解分析 题目五题目代码题解分析 题目六题目代码题解分析 题目七题目代码题解分析 题目八题目代码题解分析 题目九题目代码题解分析 题目十题目代码题解分析题目代码题解分析 题…...
华为网路设备学习-17
目录 一、加密算法 二、验证算法 三、IPsec协议 1.IKE协议(密钥交换协议) ①ISAKMP(Internet Security Association and Key Management Protocol)互联网安全关联和密钥管理协议 ②安全关联(SA) ③…...
【动态规划】深入动态规划 非连续子序列问题
文章目录 前言例题一、最长递增子序列二、摆动序列三、最长递增子序列的个数四、最长数对链五、最长定差子序列六、最长的斐波那契子序列的长度七、最长等差数列八、等差数列划分II - 子序列 结语 前言 什么是动态规划中的非连续子序列问题? 动态规划中的非连续子序…...
灵魂拷问,指针为什么是C语言的灵魂?
目录 | 引 言 | 内存操作 | 构造复杂的数据结构 | 底层硬件交互 | 指针的陷阱 | 文 末 | 引 言 指针是C语言的灵魂! 这句话是不是很耳熟?但为什么这么说,你知道吗? 本篇小文就从内存、数据结构、底层硬件交互这三个维度来…...
Node.js自定义中间件
目录 Node.js 自定义中间件详细介绍 1. 目录结构 2. 什么是自定义中间件? 3. 代码实现 1. 自定义日志中间件(记录请求信息) 2. 自定义身份验证中间件(校验用户权限) 3. 自定义请求时间中间件(记录请…...
Qt 音乐播放器项目
具体代码见:https://gitee.com/Suinnnnnn/MusicPlayer 文章目录 0. 预备1. 界面1.1 各部位长度1.2 ui文件1.3 窗口前置设置1.4 设置QSS 2. 自定义控件2.1 按钮2.2 推荐页面2.3 CommonPage2.4 滑杆 3. 音乐管理4. 歌词界面4.1 ui文件4.2 LrcPage.h文件 5. 音乐播放控…...
初识数据结构——Java集合框架解析:List与ArrayList的完美结合
📚 Java集合框架解析:List与ArrayList的完美结合 🌟 前言:为什么我们需要List和ArrayList? 在日常开发中,我们经常需要处理一组数据。想象一下,如果你要管理一个班级的学生名单,或…...
LightRAG实战:轻松构建知识图谱,破解传统RAG多跳推理难题
作者:后端小肥肠 🍊 有疑问可私信或评论区联系我。 🥑 创作不易未经允许严禁转载。 姊妹篇: 2025防失业预警:不会用DeepSeek-RAG建知识库的人正在被淘汰_deepseek-embedding-CSDN博客 从PDF到精准答案:Coze…...
Hyperlane框架全面详解与应用指南 [特殊字符][特殊字符][特殊字符]
Hyperlane框架全面详解与应用指南 🚀🚀🚀 📚 前言 欢迎来到Hyperlane框架的全面详解与应用指南!🎉🎉🎉 本文档旨在为开发者提供一个全面、详尽的Hyperlane框架使用指南,…...
使用LVS的 NAT 模式实现 3 台RS的轮询访问
题目 使用LVS的 NAT 模式实现 3 台RS的轮询访问。IP地址和主机自己规划。 -i— turn,-g——DR模式,-m——NAT模式 节点规划 仅主机网段:192.168.216.0/24 NAT网段:192.168.88.0/24 主机角色系统网络ipclientclientredhat9.5仅…...
BGP路由协议之属性4
MED 多出口鉴别器 可选非过渡属性 EBGP 的邻居 Cost 开销值,控制如何进入 AS。越小越优。继承 IGP 的开销值,默认 0 MED(Multi-Exit Discriminator,多出口鉴别器)是可选非过属性,是一种度量值用于向外部对等体指出进入本 AS 的首…...
数据库的操作
1.创建数据库 CREATE DATABASE [IF NOT EXISTS] db_name [create_specification [,create_specification] ...]create_specification: [DEFAULT] CHARACTER SET charset_name [DEFAULT] COLLATE collation_name 大写的表示关键字。[]是可选项。CHARACTER SET:指定…...
【愚公系列】《高效使用DeepSeek》055-可靠性评估与提升
🌟【技术大咖愚公搬代码:全栈专家的成长之路,你关注的宝藏博主在这里!】🌟 📣开发者圈持续输出高质量干货的"愚公精神"践行者——全网百万开发者都在追更的顶级技术博主! 👉 江湖人称"愚公搬代码",用七年如一日的精神深耕技术领域,以"…...
记录clickhouse记录一次性能优化,从60s到1s
文章目录 问题表结构类似如下分析第一步调整第一步观察多磁盘读继续观察sql 问题 一个查询接口,涉及多个clickhouse 查询,查询用时一下变成要60s 表结构类似如下 CREATE TABLE demo.test_local (id UUID,date DateTime,type String ) ENGINE Replic…...
二叉树的层序遍历
102. Binary Tree Level Order Traversal 广度优先搜索 将每个结点的层号记录下。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* …...
嵌入式硬件篇---TOF陀螺仪SPI液晶屏
文章目录 前言1. TOF传感器(Time of Flight)原理STM32使用方法硬件连接SDASCLVCC\GND 软件配置初始化I2C外设库函数驱动:读取数据 2. 陀螺仪(如MPU6050)原理STM32使用方法硬件连接SDA/SCLINTVCC/GND 软件配置初始化I2C…...
OpenCV 在树莓派上进行实时人脸检测
这段 Python 代码借助 OpenCV 库实现了在树莓派上进行实时人脸检测的功能。它会开启摄像头捕获视频帧,在每一帧里检测人脸并以矩形框标记出来,同时在画面上显示帧率(FPS)。 依赖库 cv2:OpenCV 库,用于计算…...
55.跳跃游戏
题目来源: leetcode题目,网址:55. 跳跃游戏 - 力扣(LeetCode) 解题思路: 遍历数组,若当前节点可达,更新可到达的最远距离,否则返回false。若可遍历整个数组…...
awk 实现listagg ,count 功能
awk命令实现分组统计 测试数据 ABC a1 ABC a2 ABC a3 ABD c1 ABD c2 分组统计 abc a1,a2,a3 3 abd c1,c2 awk 命令 awk {arr[$1]arr[$1] ? arr[$1] "," $2 : $2; count[$1]} END{for (i in arr) print tolower(i), arr[i], count[i]} group_…...
瑞萨RA4M2使用心得-GPIO输出
目录 一、新建项目 二、图形化开发 1.初始化IO 2.界面介绍 3.代码编写 4.所有内部函数的封装位置 5.LED闪烁函数编写 三.debug运行 总结 环境: 开发板:RA-Eco-RA4M2-100PIN-V1.0 IDE:e2 studio 一、新建项目 正常操作,下…...
uniapp微信小程序引入vant组件库
1、首先要有uniapp项目,根据vant官方文档使用yarn或npm安装依赖: 1、 yarn init 或 npm init2、 # 通过 npm 安装npm i vant/weapp -S --production# 通过 yarn 安装yarn add vant/weapp --production# 安装 0.x 版本npm i vant-weapp -S --production …...
COZE通关指南:工作流与插件开发
前言 本文隶属于专栏《AI Agent 通关指南》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢! 本专栏目录结构和参考文献请见《AI Agent 通关指南》 正文 1. 平台基础介绍 🌟 1.1 COZE平台概述 COZE平台(coze.cn)是一个强大的AI应用开发平台…...
在Unity中,如果物体上的脚本丢失,可以通过编写一个自定义编辑器脚本来查找并删除这些丢失的组件
在Unity中,如果物体上的脚本丢失,可以通过编写一个自定义编辑器脚本来查找并删除这些丢失的组件。以下是一个示例脚本,它可以帮助你一键检索场景中所有丢失脚本的物体,并删除这些丢失的组件。 步骤: 创建编辑器脚本&a…...
青少年编程与数学 02-016 Python数据结构与算法 04课题、栈与队列
青少年编程与数学 02-016 Python数据结构与算法 04课题、栈与队列 一、栈1. 栈的定义2. 栈的特点3. 栈的基本操作示例 4. 栈的实现(1)数组实现(2)链表实现 5. 栈的应用(1)函数调用(2)…...
Lucene.Net全文搜索引擎:架构解析与全流程实战指南
文章目录 引言:为什么选择Lucene.Net?一、Lucene.Net核心架构剖析1.1 模块化设计 二、Lucene.Net索引原理揭秘2.1 倒排索引:搜索的基石2.2 段(Segment)机制 三、全流程实战:从0到1构建搜索引擎3.1 环境准备…...
OpenSceneGraph 中的 LOD详解
LOD (Level of Detail,细节层次) 是3D图形中一种重要的优化技术,OpenSceneGraph 通过 osg::LOD 类提供了完整的LOD支持。 一、LOD 基本概念 1. 什么是LOD 核心思想:根据物体与相机的距离显示不同细节程度的模型 目的:减少远处物…...
程序化广告行业(64/89):AdX/SSP系统广告位设置全解析
程序化广告行业(64/89):AdX/SSP系统广告位设置全解析 大家好!我一直觉得在技术和营销不断融合的当下,程序化广告领域充满了机遇与挑战。之前和大家分享了程序化广告PDB模式的相关知识,今天想接着和大家一起…...
Pytorch中的计算图(Computational Graph)是什么
🧩 一、什么是计算图? 计算图是一种“有向无环图(DAG)”,表示变量(张量)之间的运算关系。 节点:张量或操作(如加法、乘法)边:数据流(即…...
Java 大视界 -- Java 大数据在航天遥测数据分析中的技术突破与应用(177)
💖亲爱的朋友们,热烈欢迎来到 青云交的博客!能与诸位在此相逢,我倍感荣幸。在这飞速更迭的时代,我们都渴望一方心灵净土,而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识,也…...
【Linux操作系统——学习笔记三】Linux环境下多级目录构建与管理的命令行实践报告
1.在用户主目录下,使用以下方法新建目录,并显示详细执行过程: (1)使用绝对路径在当前目录下创建 new_dir目录 (2)使用相对路径、在当前目录创建dir1、dir2、dir3目录 (3)…...
java.util.Collections中常用api
在Java中,java.util.Collections 是一个工具类,提供了大量静态方法用于操作或返回集合(如List、Set、Map等)。以下是常用的API分类整理: 1. 排序与顺序操作 sort(List<T> list) 对List进行自然顺序排序ÿ…...
批量将图片统一色调
from PIL import Image, ImageEnhance # 确保导入 ImageEnhance 模块 import osdef adjust_image_tone(image_path, output_path, r_weight1.0, g_weight1.0, b_weight1.0, brightness1.0):"""调整图片的色调、明暗,并进行去图处理。参数:image_pat…...
OCC Shape 操作
#pragma once #include <iostream> #include <string> #include <filesystem> #include <TopoDS_Shape.hxx> #include <string>class GeometryIO { public:// 加载几何模型:支持 .brep, .step/.stp, .iges/.igsstatic TopoDS_Shape L…...
docker的run命令 笔记250406
docker的run命令 笔记250406 Docker 的 run 命令用于创建并启动一个新的容器。它是 Docker 中最常用的命令之一,基本语法为: docker run [OPTIONS] IMAGE [COMMAND] [ARG...]常用选项(OPTIONS) 参数说明-d 或 --detach后台运行…...
批量将 HTML 转换为 Word/Txt/PDF 等其它格式
HTML是一种超文本标记语言,在进行网页编辑的时候非常常见,我们浏览的网站内容,都可以保存为 html 格式,如果想要将 html 格式的文档转为其它格式,比如 Word、PDF 或者 Txt,我们应该怎么做呢?今天…...
TPS入门DAY02 服务器篇
1.创建空白插件 2.导入在线子系统以及在线steam子系统库 MultiplayerSessions.uplugin MultiplayerSessions.Build.cs 3.创建游戏实例以及初始化会话创建流程 创建会话需要的函数,委托,委托绑定的回调,在线子系统接口绑定某一个委托的控制其…...
C高级,终端操作
核心要点整理 刷题作业 一、基础操作 命令行提示符结构 ubuntuubuntu:~$ 当前用户 | 连接符 | 计算机名 | 当前路径 | 用户权限 用户切换 su 用户名:切换用户sudo passwd 用户名:修改用户密码 常用指令 cd -:返回上一次路径ls:显…...
Lua语言的边缘计算
Lua语言的边缘计算探索 引言 随着物联网(IoT)、人工智能(AI)和大数据技术迅速发展,边缘计算作为一种分布式计算架构日益受到重视。其核心理念是将计算和数据存储资源更靠近数据源,以降低延迟、减轻网络负…...
RabbitMQ运维
RabbitMQ运维 一.集群1.简单介绍2.集群的作用 二.搭建集群1.多机多节点搭建步骤 2.单机单节点搭建步骤 3.宕机演示 三.仲裁队列1.简单介绍2.Raft协议Raft基本概念主节点选举选举过程 3.仲裁队列的使用 四.HAProxy负载均衡1.安装HAProxy2.HAProxy的使用 一.集群 1.简单介绍 Ra…...
【ESP32】ESP32物联网应用:MQTT控制与状态监测
ESP32物联网应用:MQTT控制与状态监测 引言 在物联网时代,远程监测和控制设备已经成为现实生活中常见的需求。本文将介绍如何使用ESP32微控制器配合MQTT协议,实现一个简单而强大的物联网应用:远程状态监测和设备控制。我们将以巴…...
如何保证RabbitMQ消息的可靠传输?
在这个图中,消息可能丢失的场景是1,2,3 1.在生产者将消息发送给RabbitMQ的时候,消息到底有没有正确的到达服务器呢,RabbitMQ提供了两种解决方案: a. 通过事务机制实现(比较消耗性能࿰…...
Redis高可用
主从复制 为什么要主从复制? 由于数据都是存储在一台服务器上,如果出事就完犊子了,比如: 如果服务器发生了宕机,由于数据恢复是需要点时间,那么这个期间是无法服务新的请求的;如果这台服务器…...