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

算法笔记:A*算法

A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度

1 中心思路

  • A*算法通过下面这个函数来计算每个节点n的优先级
    • f(n)=g(n)+h(n)
      • f(n)是节点n的综合优先级。当选择下一个要遍历的节点时,总会选取综合优先级最高(f(n)值最小)的节点。
      • g(n) 是节点n距离起点的代价
      • h(n)是节点n距离终点的预计代价,这也就是A*算法的启发函数
  • A*算法在运算过程中,每次从优先队列中选取f(n)值最小(优先级最高)的节点作为下一个待遍历的节点。

1.1  伪代码

  • A*算法使用两个集合来表示待遍历的节点(open_set),与已经遍历过的节点(close_set)

  • 初始化open_set和close_set
  • 将起点n0加入open_set中,并设置f(n0)=0(优先级最高)
  • 如果open_set不为空,则从open_set中选取优先级最高的节点n:
    • 如果节点n为终点:
      • 从终点开始逐步追踪parent节点,一直达到起点
      • 返回找到的结果路径,算法结束
    • 如果节点n不是终点:
      • 将节点n从open_set中删除,并加入close_set中
      • 遍历节点n所有的邻近节点
        • 如果邻近节点m在close_set中(已经访问过来),则:
          • 跳过,选取下一个邻近节点
        • 如果邻近节点m也不在open_set中,则=
          • 设置节点m的parent为节点n
          • 计算节点m的优先级f(n)
          • 将节点m加入open_set中

2 启发函数

  • 在极端情况下,当启发函数h(n)始终为0,则将由g(n)决定节点的优先级,此时算法就退化成了Dijkstra算法
    • ntu 课程笔记 :MAS714(7) 最短路径和优先队列_UQI-LIUWJ的博客-CSDN博客
  • 如果h(n)始终小于等于节点n到终点的代价,则A*算法保证一定能够找到最短路径。
    • 但是当h(n)的值越小,算法将遍历越多的节点,也就导致算法越慢。
  • 如果h(n)完全等于节点n到终点的代价,则A*算法将找到最佳路径,并且速度很快。
    • 可惜的是,并非所有场景下都能做到这一点。因为在没有达到终点之前,我们很难确切算出距离终点还有多远。
  • 如果h(n)的值比节点n到终点的代价要大,则A*算法不能保证找到最短路径,不过此时会很快
    • 比如这种情况最短路路径应该是下路
    • 但如果我们估计的h(n)为实际路径的两倍
      • 那么选择中间节点的时候,A*算法会选择上路 (5+3*2=11,4+3.6*2=11.2)

     

2.1 一些经验启发函数

  • 如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离
  • 如果图形中允许朝八个方向移动,则可以使用对角距离
  • 如果图形中允许朝任何方向移动,则可以使用欧几里得距离

     

相关文章:

算法笔记:A*算法

A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度 1 中心思路 A*算法通过下面这个函数来计算每个节点n的优先级 f(n)g(n)h(n) f(n)是节点n的综合优先级。当选择下一个要遍历的节点时,总会选取综合优先级最高(f(n)值最小&#xff0…...

postgresql 分类排名

postgresql 分类排名 排名窗口函数示例CUME_DIST 和 NTILE 排名窗口函数 排名窗口函数用于对数据进行分组排名。常见的排名窗口函数包括: • ROW_NUMBER,为分区中的每行数据分配一个序列号,序列号从 1 开始分配。 • RANK,计算每…...

TCP服务器实现—多进程版,多线程版,线程池版

目录 前言 1.存在的问题 2.多进程版 3.多线程版 4.线程池版 总结 前言 在上一篇文章中使用TCP协议实现了一个简单的服务器,可以用来服务端和客户端通信,但是之前的服务器存在一个问题,就是当有多个客户端连接服务器的时候,服…...

Nginx 配置文件的完整指南 (二)

文章目录 四、反向代理配置4.1 proxy_pass效果1—路径重写效果2—转发到其他服务器 4.2 proxy_pass使用规则4.3 proxy_set_header4.3.1 修改请求协议 五、负载均衡配置5.1 upstream5.2 server5.3 负载均衡策略5.3.1 轮询5.3.2 加权轮询5.3.3 最少连接5.3.3 ip_hash:…...

AI夏令营第三期 - 基于论文摘要的文本分类与关键词抽取挑战赛笔记

赛题:基于论文摘要的文本分类与关键词抽取 背景:高效的从海量医学文献中提取疾病诊断和治疗关键信息 任务:通过论文摘要判断论文是否为医学文献 样例 数据集:csv文件,字段:标题、作者、摘要、关键词 评价指…...

使用qsqlmysql操作mysql提示Driver not loaded

环境: win10 IDE: qt creator 编译器: mingw32 这里简单的记录下。我遇到的情况是在IDE使用debug和release程序都是运行正常,但是当我编译成发布版本之后。老是提示Driver not load。 这就很奇诡了。 回顾了下编译的时候是需要在使用qt先编译下libqsqlmysql.dll的…...

Java云原生框架Quarkus初探

Java云原生框架Quarkus初探 Quarkus 介绍 Quarkus 是一个云原生,容器优先的Java应用框架,它号称是超音速和亚原子的框架,主要特点是构建速度、启动速度快和占用资源少等特点。它为OpenJDK HotSpot和GraalVM量身定制, 根据Java库和…...

ElasticSearch相关概念

文章目录 前提倒排索引MySQL、ES的区别和关联IK分词器索引库mapping属性索引库的crud 文档的crudRestClientDSL查询DSL 查询种类DSL query 基本语法 搜索结构处理排序分页高亮RestClient 前提 开源的搜索引擎,从海量数据中快速找到需要的内容。(分词检索…...

微服务实战项目-学成在线-项目部署

微服务实战项目-学成在线-项目部署 1 什么是DevOps 一个软件的生命周期包括:需求分析阶、设计、开发、测试、上线、维护、升级、废弃。 通过示例说明如下: 1、产品人员进行需求分析 2、设计人员进行软件架构设计和模块设计。 3、每个模块的开发人员…...

封装form表单

目录 1. 源码 2. 其他页面引用 ps&#xff1a;请看完看明白再复用 1. 源码 <template><div style"width: 100%; height: 100%" class"form-condition"><!-- 普通表单 --><el-card shadow"hover" class"cardheigh…...

程序员如何利用公网远程访问查询本地硬盘【内网穿透】

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《高效编程技巧》《cpolar》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 公网远程访问本地硬盘文件【内网穿透】 文章目录 公网远程访问本地硬盘文件【内网穿透】前言1. 下载cpolar和Everything软件1.…...

算法|Day42 动态规划10

LeetCode 121.买卖股票的最佳时机 题目链接&#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/ 题目描述&#xff1a;给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天…...

vmalert集成钉钉告警

vmalert通过在alert.rules中配置告警规则实现告警&#xff0c;告警规则语法与Prometheus兼容&#xff0c;依赖Alertmanager与prometheus-webhook-dingtalk实现钉钉告警&#xff0c;以下步骤&#xff1a; 1、构建vmalert 从源代码构建vmalert&#xff1a; git clone https://…...

深入解析 MyBatis 中的 <foreach> 标签:优雅处理批量操作与动态 SQL

在当今的Java应用程序开发中&#xff0c;数据库操作是一个不可或缺的部分。MyBatis作为一款颇受欢迎的持久层框架&#xff0c;为我们提供了一种优雅而高效的方式来管理数据库操作。在MyBatis的众多特性中&#xff0c;<foreach>标签无疑是一个强大的工具&#xff0c;它使得…...

LeGO-Loam代码解析(二)--- Lego-LOAM的地面点分离、聚类、两步优化方法

1 地面点分离剔除方法 1.1 数学推导 LeGO-LOAM 中前端改进中很重要的一点就是充分利用了地面点,那首先自然是提取 对地面点的提取。 如上图,相邻的两个扫描线束的同一列打在地面上如 点所示,他们的垂直高度差 &#xff0c;水平距离差 &#xff0c;计算垂直高度差和水平高度差…...

程序员如何利用公网打造低成本轻量化的搜索和下载平台【内网穿透】

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《高效编程技巧》《cpolar》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 公网远程访问本地硬盘文件【内网穿透】 文章目录 公网远程访问本地硬盘文件【内网穿透】前言1. 下载cpolar和Everything软件1.…...

构建可远程访问的企业内部论坛

文章目录 前言1.cpolar、PHPStudy2.Discuz3.打开PHPStudy&#xff0c;安装网页论坛所需软件4.进行网页运行环境的构建5.运行Discuz网页程序6.使用cpolar建立穿透内网的数据隧道&#xff0c;发布到公网7.对云端保留的空白数据隧道进行配置8.Discuz论坛搭建完毕 前言 企业在发展…...

2023河南萌新联赛第(六)场:河南理工大学-C 旅游

2023河南萌新联赛第&#xff08;六&#xff09;场&#xff1a;河南理工大学 https://ac.nowcoder.com/acm/contest/63602/C 文章目录 2023河南萌新联赛第&#xff08;六&#xff09;场&#xff1a;河南理工大学题意解题思路代码 题意 小C喜欢旅游&#xff0c;现在他要去DSH旅…...

C语言 常用工具型API ----------strchr()

函数原型 char *strchr(const char *str, int c) 参数 str-- 要被检索的 C 字符串。 c-- 在 str 中要搜索的字符。 功能 在参数str所指向的字符串中搜索第一次出现字符c&#xff08;一个无符号字符&#xff09;的位置 头文件 #include <string.h> 返回值 返回一…...

建造者模式的理论与实现

本文实践代码仓库&#xff1a;https://github.com/goSilver/my_practice 文章目录 一、定义二、作用三、实现四、总结 一、定义 建造者模式是一种创建复杂对象的设计模式。它将一个复杂对象的构建过程分解为多个简单的步骤&#xff0c;并且允许按照特定的顺序来构建对象。通过…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...