路径规划之启发式算法之一:A-Star(A*)算法
A*算法是一种启发式搜索算法,常用于解决路径规划问题。
一、A*算法的定义与原理
A*算法是一种用于在图形或网格中查找最短路径的算法。它在搜索过程中综合考虑了每个节点的实际距离(g值)和预估距离(h值),以找到最优路径。具体来说,算法通过评价各个节点的代价值(f值),其中f值等于g值加上h值,来获取下一需要拓展的最佳节点,直至到达最终目标点位置。
改进A算法是在传统A算法的基础上进行优化,以提高路径搜索的效率和准确性。改进的主要方向包括启发函数的选择与优化、搜索邻域的优化、双向搜索算法(双向A*)、对open list列表进行数据结构优化,以及曲线平滑化处理。
二、特点与优势
1. 启发式搜索:A*算法利用启发信息(即预估距离h值)来指导搜索过程,从而提高了搜索效率。
2. 环境适应性强:该算法对环境反应迅速,能够根据不同场景和约束条件进行路径规划。
3. 路径直接:A*算法搜索路径直接,不易陷入局部最优解。
三、核心公式
A*算法的核心在于其估价函数,该函数由两部分组成:实际代价g(n)和启发式估计代价h(n)。总的代价消耗f(n)是这两者的和,表示为:
f(n)=g(n)+h(n)
其中:
f(n) 表示节点的综合优先级,在选择节点时考虑该节点的综合优先级;
g(n) 表示起始点到当前节点的代价值;
h(n) 表示当前节点到目标点的代价估计值,也就是预估函数。
四、算法流程
1. A*算法的实现通常包括以下步骤:
(1)初始化:创建开放列表(open list)和封闭列表(close list),并将起点加入开放列表。
(2)搜索:从开放列表中选择f值最小的节点进行搜索。更新该节点的g值和h值,并检查其邻居节点。如果邻居节点在开放列表或封闭列表中,则更新其g值(如果通过当前节点到达该邻居节点的路径更短)。如果邻居节点不在任何列表中,则将其加入开放列表,并设置其父节点为当前节点。
(3)更新列表:将已搜索过的节点从开放列表中移除,并加入封闭列表。
(4)终止条件:如果目标节点在开放列表中,则找到最优路径并终止搜索。否则,继续搜索直到开放列表为空或达到其他终止条件。
2. 改进A*算法的流程如下:
(1)初始化:初始化open_set(开放列表)和close_set(关闭列表),将起点加入open_set中,并设置优先级为0(优先级最高)。
(2)循环选择:如果open_set不为空,则从open_set中选取优先级最高的节点n。
(3)目标检查:如果节点n为终点,则从终点开始逐步追踪parent节点,一直达到起点;返回找到的结果路径,算法结束。
(4)节点扩展:如果节点n不是终点,则将节点n从open_set中删除,并加入close_set中;遍历节点n所有的邻近节点。
(5)邻近节点检查:对于每个邻近节点m,如果m在close_set中,则跳过;如果m不在open_set中,则设置节点m的parent为节点n,计算节点m的优先级,并将节点m加入open_set中。
(6)循环结束:重复步骤2-5,直到找到终点或open_set为空。
五、应用领域
A*算法被广泛应用于各种路径规划问题,包括但不限于:
(1)计算机图形学:在图形图像处理中,A*算法常用于搜索最优路径。
(2)自动导航:A*算法可用于导航系统,规划机器人或车辆的移动路径。
(3)网络规划:A*算法可用于网络规划和路由规划,如规划互联网数据包的最优路径。
(4)游戏开发:A*算法常用于游戏开发,用于寻找游戏人物或NPC(非玩家角色)移动的最优路径。
六、注意事项与局限性
(1)启发函数的选择:启发函数h(n)的选择对A*算法的性能和结果有很大影响。如果h(n)的值过小,算法将遍历更多的节点,导致搜索速度变慢;如果h(n)的值过大,则可能无法找到最短路径。因此,需要根据具体应用场景选择合适的启发函数。
(2)计算复杂度:A*算法的计算复杂度较高,特别是在节点数量较多或障碍物复杂的情况下。因此,在实际应用中需要权衡搜索效率和计算复杂度之间的关系。
(3)实时性要求:对于实时性要求较高的应用场景(如自动驾驶、无人机导航等),A*算法可能需要进行优化或与其他算法结合使用以满足实时性要求。
七、优化策略
(1)启发函数的选择与优化:预估函数的选择对A*算法的性能有很大影响。如果h(n)的值过小,算法将遍历更多的节点,导致搜索速度变慢;如果h(n)的值过大,则可能无法找到最短路径。可以为启发函数增加权重系数,节点比较时启发函数的优化。
(2)搜索邻域的优化:舍弃邻域法和扩展邻域法可以减少搜索范围,提高搜索效率。
(3)*双向搜索算法(双向A)**:从起点和终点同时进行搜索,提高计算速度。
(4)数据结构优化:对open list列表进行数据结构优化,如使用二叉堆等,以提高算法的执行效。
(5)曲线平滑化:采用贝塞尔曲线等方法进行路径平滑化处理,提高路径的平滑度。
相关文章:
路径规划之启发式算法之一:A-Star(A*)算法
A*算法是一种启发式搜索算法,常用于解决路径规划问题。 一、A*算法的定义与原理 A*算法是一种用于在图形或网格中查找最短路径的算法。它在搜索过程中综合考虑了每个节点的实际距离(g值)和预估距离(h值),以…...
Android复习代码1-4章
public class RudioButton extends AppCompatActivity {Overrideprotected void onCreate(Nullable Bundle savedInstanceState) {super.onCreate(savedInstanceState);setContentView(R.layout.activity_rudio_button);// 找到RadioGroup和TextView的实例RadioGroup radioGrou…...
【问题】webdriver.Chrome()设置参数executable_path报不存在
场景1: 标红报错unresolved reference executable_path 场景2: 执行报错TypeError: __init__() got an unexpected keyword argument executable_path 原因: 上述两种场景是因为selenium4开始不再支持某些初始化参数。比如executable_path 解决: 方案…...
win10系统安装docker-desktop
1、开启Hyper-v ———————————————— Hyper-V 是微软提供的一种虚拟化技术,它允许你在同一台物理计算机上运行多个独立的操作系统实例。这种技术主要用于开发、测试、以及服务器虚拟化等领域。 —————————————————————— &#…...
小程序-基于java+SpringBoot+Vue的乡村研学旅行平台设计与实现
项目运行 1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境:IDEA,Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境:Tomcat 7.x,8.x,9.x版本均可 4.硬件环境:…...
组件A底部栏(position: fixed )事件使用$emit更新内容失败bug解决
今天遇到一个很离奇的bug,记录一下 问题:在组件内底部栏使用$emit触发按钮事件但打印出来的值是初始化的值,更新的值被重置导致更新失败 原因:组件内底部使用了 position: fixed; 固定, 导致组件内插槽 this 与 保存按…...
数据结构——排序第三幕(深究快排(非递归实现)、快排的优化、内省排序,排序总结)超详细!!!!
文章目录 前言一、非递归实现快排二、快排的优化版本三、内省排序四、排序算法复杂度以及稳定性的分析总结 前言 继上一篇博客基于递归的方式学习了快速排序和归并排序 今天我们来深究快速排序,使用栈的数据结构非递归实现快排,优化快排(三路…...
C++的类功能整合
1. 类的基本概念 类是面向对象编程的核心,它封装了数据和操作数据的函数。 #include <iostream> using namespace std;class MyClass { public:int publicData;void publicFunction() {cout << "Public function" << endl;}private:i…...
《String类》
目录 一、定义与概述 二、创建字符串对象 2.1 直接赋值 2.2 使用构造函数 三、字符串的不可变性 四、常用方法 4.1 String对象的比较 4.1.1 比较是否引用同一个对象 4.1.2 boolean equals(Object anObject)方法:按照字典序比较 4.1.3 int compareTo(Strin…...
【docker】docker的起源与容器的由来、docker容器的隔离机制
Docker 的起源与容器的由来 1. 虚拟机的局限:容器的需求萌芽 在 Docker 出现之前,开发和部署软件主要依赖虚拟机(VMs): 虚拟机通过模拟硬件运行操作系统,每个应用程序可以运行在自己的独立环境中。虽然虚…...
Window 安装 Nginx
参考链接 Windows 环境nginx安装使用及目录结构详解_windows 安装nginx-CSDN博客 Nginx 安装及配置教程(Windows)【安装】_nginx下载安装-CSDN博客 安装 1)下载 nginx: download 2)解压 3)启动 3.1)方…...
replace (regexp|substr, newSubstr|function)替换字符串中的指定部分
replace 方法用于替换字符串中的指定部分。它可以接受一个子字符串或正则表达式作为第一个参数,第二个参数是替换的内容。 用法示例 基本替换 let str "Hello, world!"; let newStr str.replace("world", "everyone"); console.lo…...
【ROS2】Ubuntu22.04安装ROS humble
一. ROS简介 1.1 什么是ROS ROS 是一个适用于机器人的开源的元操作系统。它提供了操作系统应有的服务,包括硬件抽象,底层设备控制,常用函数的实现,进程间消息传递,以及包管理。ROS的核心思想就是将机器人的软件功能做…...
cesium 3Dtiles变量
原本有一个变亮的属性luminanceAtZenith,但是新版本的cesium没有这个属性了。于是 let lightColor 3.0result._customShader new this.ffCesium.Cesium.CustomShader({fragmentShaderText:void fragmentMain(FragmentInput fsInput, inout czm_modelMaterial mate…...
配置泛微e9后端开发环境
配置泛微e9的后端开发环境 1.安装jdk1.8(请自行安装并设置环境变量) 2.将服务器上的WEARVER文件夹拷贝到开发环境下(其中要包含ecology和Resin目录) 3.通过idea创建一个基础Java项目,将jdk设置为1.8 4.添加依赖,需要将3个文件夹的所有jar包添加到项目中…...
【Stable Diffusion】安装教程
目录 一、python 安装教程 二、windows cuda安装教程 三、Stable Diffusion下载 四、Stable Diffusion部署(重点) 一、python 安装教程 (1)第一步下载 打开python下载页面,找到python3.10.9,点击右边…...
USB Type-C一线通扩展屏:多场景应用,重塑高效办公与极致娱乐体验
在追求高效与便捷的时代,启明智显USB Type-C一线通扩展屏方案正以其独特的优势,成为众多职场人士、娱乐爱好者和游戏玩家的首选。这款扩展屏不仅具备卓越的性能和广泛的兼容性,更能在多个应用场景中发挥出其独特的价值。 USB2.0显卡ÿ…...
【力扣】541.反转字符串2
问题描述 思路解析 每当字符达到2*k的时候,判断,同时若剩余字符>k,只对前k个进行判断(这是重点)因为字符串是不可变变量,所以将其转化为字符串数组,最后才将结果重新转变为字符串 字符串->字符数组 …...
什么是防抖与节流
防抖(Debouncing)与节流(Throttling) 在前端开发中,尤其是在处理用户输入、窗口调整大小、滚动事件等高频率触发的事件时,防抖和节流是两种常用的技术手段。它们可以帮助我们优化性能,减少不必…...
springboot vue 开源 会员收银系统 (12)购物车关联服务人员 订单计算提成
前言 完整版演示 http://120.26.95.195/ 开发版演示 http://120.26.95.195:8889/ 在之前的开发进程中,我们完成订单的挂单和取单功能,今天我们完成购物车关联服务人员,用户计算门店服务人员的提成。 1.商品关联服务人员 服务人员可以选择 一…...
FFmpeg 推流给 FreeSWITCH
FFmpeg 推流,貌似不难,网上有很多资料, 接到一个任务,推流给 FreeSWITCH,最开始以为很容易, 实则不然,FreeSWITCH uuid_debug_media <uuid>, 一直没人任何反应 仔细一查,Fr…...
.npmrc文件的用途
.npmrc 文件是 npm(Node.js 的包管理工具)用于配置项目或用户的设置文件。它可以存储与 npm 相关的配置信息,如注册表地址、认证信息、代理设置、安装路径等。.npmrc 文件可以出现在不同的地方,具有不同的作用范围,通常…...
C++游戏开发入门:如何从零开始实现自己的游戏项目?
成长路上不孤单😊😊😊😊😊😊 【14后😊///C爱好者😊///持续分享所学😊///如有需要欢迎收藏转发///😊】 今日分享关于C游戏开发的相关内容! 关于【…...
Redis设计与实现第16章 -- Sentinel 总结1(初始化、主从服务器获取信息、发送信息、接收信息)
Sentinel是Redis的高可用解决方案:由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器,以及这些主服务器属下的所有从服务器,被监视的主服务器进入下线状态时,自动将下线主服务器属下的某个从服务器升级为新的主…...
Windows10+VirtualBox+Ubuntu:安装虚拟机VirtualBox,虚拟机中安装Ubuntu
一、需求 在Windows10系统中,安装虚拟机VirtualBox,VirtualBox中安装Ubuntu桌面版。 二、环境准备 系统环境 Windows10 内存:8G 虚拟化 虚拟机的运行,如果需要Windows系统开启虚拟化,可以通过BIOS设置。 “虚拟…...
Torchtune在AMD GPU上的使用指南:利用多GPU能力进行LLM微调与扩展
Torchtune on AMD GPUs How-To Guide: Fine-tuning and Scaling LLMs with Multi-GPU Power — ROCm Blogs 这篇博客提供了一份详细的使用Torchtune在AMD GPU上微调和扩展大型语言模型(LLM)的指南。Torchtune 是一个PyTorch库,旨在让您轻松地…...
C底层 函数栈帧
文章目录 一,什么是寄存器 二,栈和帧 前言 我们在学习c语言程序的时候,是不是有很多的疑问,如 1,为什么形参不可以改变实参 2,为什么我们编写程序的时候会出现烫烫烫......这个乱码 3,那些局…...
【模块一】kubernetes容器编排进阶业务容器化案例
Kubernetes 实战案例 Kubernetes实战案例-规划(基于nerdctl buildkitdcontainerd构建容器镜像) 业务容器化优势: ① 提高资源利用率、节约部署IT成本。 ② 提高部署效率,基于kubernetes实现微服务的快速部署与交付、容器的批量调度与秒级启动。 ③…...
可视化建模以及UML期末复习篇----相关软件安装
作为一个过来人,我的建议是别过来。 一、可视化建模 <1>定义: 官方:一种使用图形符号来表示系统结构和行为的建模技术。 我:其实说白了就是把工作流程用图形画出来。懂不? <2>作用: 提高理解和分析复杂系统的能力。促…...
Appflyer记录卸载事件
Appflyer官方文档 1.原理 1.AppsFlyer每天向Firebase Cloud Messaging(FCM)和 Apple Push Notification Services(APNS)发送一次API请求。 2.然后FCM和APNS会发送一条静默推送消息,用于判断用户设备上是否仍装有相关应…...
网站策划案怎么做/德州seo优化
Maven 项目模板 推荐分布式微服务电商源码 Maven 使用 archetype(原型) 来创建自定义的项目结构,形成 Maven 项目模板。 在前面章节我们学到 Maven 使用下面的命令来快速创建 java 项目: mvn archetype:generate 什么是 archetype? arc…...
企业营销网站建设/餐饮最有效的营销方案
EditText实现输入限制和校验 一、方法 1)输入限制 1、通过android:digits限制只能输入小写abc android:digits"abc" 2、通过android:inputType限制只能输入数字 android:inputType"number" 在android:inputType中可以设置各种限制,比…...
网站开发的公司属于什么行业/seo优化sem推广
勾股定理是8年级课本重要内容,属于初中阶段重要知识点,也是各类考试重点考察内容。特别是利用勾股定理求最短距离的问题,很多学生都感觉到困难,下面就针对如何巧用勾股定理求最短路径长进行讲解。求最短距离的问题,第一…...
东莞 外贸网站 建站/明天上海封控16个区
1、如何在终端运行js文件node 文件名(没有后缀),如果使用该方法,每当代码改变时,都要重新运行2、安装supervisor 实现热更新(一般使用node 文件名 来运行文件,但是当文件发生变化时必须重启文件才能刷新,安装好super…...
淘宝放单网站怎么做的/四川游戏seo整站优化
CayleyCayley公式的定义是这样的,对于n个不同的节点,能够组成的无根树(原来是无向连通图或者是有标志节点的树)的种数是n^(n-2)种。(这里让大家好理解一点,就写成了无根树࿰…...
空间信息网站/佛山seo教程
1. 创建用户和组 groupadd mysql useradd –g mysql mysql 2. 解压安装包 cd /usr/local tar -zxvf /…/mysql-5.6.22-linux-glibc2.5-i686.tar.gz ln -s mysql-5.6.22-linux-glibc2.5-i686 mysql 3. 修改文件夹所属用户和组为mysql cd mysql chown -R mysql . c…...