【算法】图解A* 搜索算法_a*算法流程图-程序员宅基地

最新版本参考（含代码实现）：【机器人】路径规划 - 图解A* 搜索算法 - 知乎

A* 算法是启发式搜索算法，是根据Dijkstra算法改进而来。

问题引入

如下图所示，S为起始（start）节点，G为目标（goal）节点。

节点之间连线是两点的路径长度，如A到E的路径长度c(A,E) = 9。
节点旁的h值时当前节点到达目标节点（G）的预估值，如h(A)=15, 表示从当前点A到达目标点G的估计路径长度为15，此处h(x)即为启发函数，启发函数的设计有很多方法，具体可参考链接，此处不再扩展。
从起点S到达当前节点x的路径长度表示为g(x) 。
从起点S到达目标G并经过点x的估计距离长度表示为f(x) = g(x) + h(x)，该公式是A*算法的核心公式。
A*算法通过不断的选择估计距离f最小的节点，逐渐构建最短路径。

逻辑流程

创建两个集合OPEN集，CLOSED集，算法核心是从OPEN集中选择最优（f值小最优，或f相同时，h小的更优）的节点到CLOSED集中，然后将其后继节点放入OPEN集中，然后重复操作选取最优节点，直到到达目标，或者OPEN为空为止。最后再CLOSED集中根据目标G所包含的前序节点逆序查找最后到达起点S，这个链路的逆序即最优路径，具体流程如下图。

搜索过程

以下是前面网络的搜索过程展开图。

组合块中：

灰色为前序节点
蓝色当前节点x
g：起点S到当前节点x的路径距离。
h：当前节点x到终点G的估计距离
f：起点S途径x到达终点G的估计距离，即 f = g + h
绿色框为当前OPEN集合中的最优节点
红色框表示当前OPEN集合中需要被删除的节点

在OPEN、CLOSED中每一行表示一次完整迭代完成时两集合中的节点集合。

最后的最优路径是：S->B->F->k->G

注：当两个节点f相同时，h小的更优

更多阅读

【机器人】 D*算法-动态路径规划

本文链接：https://blog.csdn.net/JasonZhu_csdn/article/details/86266228

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Ubuntu16.4 学习之安装中文输入法_language-support-installer怎么下载-程序员宅基地

文章浏览阅读1.6k次。1、先安装语言包 System Settings–>Language Support–>Install/Remove Languages选中chinese，（简体中文选中后无法点击Apply,再同时选中繁体中文）点击Apply应用即可，等待下载安装完成。2、安装ibus框架 sudo apt-get install ibus ibus-clutter ibus-_language-support-installer怎么下载

人大金仓 kingbase_v8_R3 JDBC连接_kingbase v8r3驱动类-程序员宅基地

文章浏览阅读4.1k次，点赞3次，收藏5次。人大金仓JDBC连接人大金仓v8_r3_JDBC驱动下载:链接：https://pan.baidu.com/s/1Oot2onweP2RMdGi3as65JQ提取码：1miymybatis连接人大金仓:#kingbasejdbc.driver=com.kingbase8.Driverjdbc.url=jdbc:kingbase8://localhost:54321/omtxh?zeroDateTimeBehavior=convertToNull&useUnicode=true&c_kingbase v8r3驱动类

Cocos2d-x 中setFrameSize 和 setDesignResolutionSize的一个问题_setdesignresolutionsize 缺点-程序员宅基地

文章浏览阅读6k次。最近开始搞cocos了，虽然开发起来看起来还挺简单的……但是感觉坑真是好多。。。 ok，现在讲一下我遇到的一个问题。在cocos2dx-3.x的版本中，增加了DesignResolutionSize的概念，这个东西可以使得自己设计的屏幕大小适应各种机器的屏幕。听起来还是很方便的。我开始想要模拟一个960*640的屏幕，但逻辑上的分辨率是480*320，于是我这么写了： _setdesignresolutionsize 缺点

大数据毕设选题 - 大数据招聘租房数据分析可视化系统（python）_题目是:大数据视角下的招聘数据分析与可视化研究-程序员宅基地

文章浏览阅读3.6k次，点赞2次，收藏103次。 Hi，大家好，这里是丹成学长的毕设系列文章！对毕设有任何疑问都可以问学长哦!这两年开始，各个学校对毕设的要求越来越高，难度也越来越大… 毕业设计耗费时间，耗费精力，甚至有些题目即使是专业的老师或者硕士生也需要很长时间，所以一旦发现问题，一定要提前准备，避免到后面措手不及，草草了事。为了大家能够顺利以及最少的精力通过毕设，学长分享优质毕业设计项目，今天要分享的新项目是基于大数据的招聘与租房分析可视化系统学长这里给一个题目综合评分(每项满分5分) 选题指导, 项目分享：https:/_题目是:大数据视角下的招聘数据分析与可视化研究

Vice-Chairman of the European Commission: cryptocurrency assets will be greatly developed_eu commission cryptocurrency-程序员宅基地

文章浏览阅读299次。The European Commission is the executive body of EU legislation and will complete a regulatory assessment of cryptocurrency asset governance this year. The Vice-Chairman of the European Commission sai..._eu commission cryptocurrency

C# /Winform SQLite and SQLsugar_sqlite和sqsugar版本匹配-程序员宅基地

文章浏览阅读3.6k次。SQLite 创建数据库插入数据库数据DEMO注意事项：SQLsugar版本（4.9.9.11） and SQLite版本（1.0.113.0） andSystem.Data.SQLite.EF6 版本（1.0.113.0）andSystem.Data.SQLite.Linq（1.0.113.0） and .NET版本（4.0）_sqlite和sqsugar版本匹配

随便推点

<iOS>git-起步_gvs和git-程序员宅基地

文章浏览阅读402次。起步本章介绍开始使用Git前的相关知识。我们会先了解一些版本控制工具的历史背景，然后试着让Git在你的系统上跑起来，直到最后配置好，可以正常开始开发工作。读完本章，你就会明白为什么Git会如此流行，为什么你应该立即开始使用它。版本控制什么是版本控制？我为什么要关心它呢？版本控制是一种记录一个或若干文件内容变化，以便将来查阅特定版本修订情况的系统。在本书所展示的例子中，我们仅对保存着软件_gvs和git

SpringMVC---使用注解开发，404错误原因，RESTful，页面跳转，Json交互_getmapping传参数报错404-程序员宅基地

文章浏览阅读2.1k次，点赞3次，收藏9次。四.SpringMVC项目搭建（注解版）1.首先配置springmvc-servlet.xml<?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:context="http://www.spring_getmapping传参数报错404

课程设计——迷宫问题_(s).base=(selemtype )realloc((s).base,((s).sta-程序员宅基地

文章浏览阅读3k次。课程设计——迷宫问题（C++）个人设计 2010-01-16 15:06 阅读1 评论0 字号：大大中中小小迷宫问题1设计目的、要求以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求_(*s).base=(selemtype *)realloc((*s).base,((*s).stacksize+stackincrement)*siz