一直就很想把A*看一下,虽然所早的项目一直没用上A*,但是对它还是情有独钟,
可能是打心底的对寻路比较有好奇感把。原本网上关于A*的解释说明的文章数不胜数,
但是我还是想把自己所理解的写在自己的博客上,方便日后的回顾,
当然还是从各位大牛那一点点的积累下来的。
一、A*算法总结:
1.
将开始节点放入开放列表(开始节点的F和G值都视为0);
2.
重复一下步骤:
i.
在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点;
ii.
把当前节点从开放列表删除,
加入到封闭列表;
iii.
对当前节点相邻的每一个节点依次执行以下步骤:
(a.
如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点;
(b.
如果该相邻节点不在开放列表中,则将该节点添加到开放列表中, 并将该相邻节点的父节点设为当前节 点,同时保存该相邻节点的G和F值;
(c.
如果该相邻节点在开放列表中,
则判断若经由当前节点到达该相邻节点的G值是否小于原来保存 的G值,若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.
iv.
循环结束条件:
当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时应终止循环;
或者当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终点节点则意味着路径无法被找 到,此时也结束循环;
3.
从终点节点开始沿父节点遍历,
并保存整个遍历到的节点坐标,遍历所得的节点就是最后得到的路径;
二、路径排序
决定哪些方格会形成路径的关键是下面这个等式:
F = G + H
这里
·G=从起点A沿着已生成的路径到一个给定方格的移动开销。
·H=从给定方格到目的方格的估计移动开销。这种方式常叫做试探,有点困惑人吧。其实之所以叫做试探法是因为这只是一个猜测。在找到路径之前我们实际上并不知道实际的距离,因为任何东西都有可能出现在半路上(墙啊,水啊什么的)。本文中给出了一种计算H值的方法,网上还有很多其他文章介绍的不同方法。
我们要的路径是通过反复遍历开放列表并选择具有最小F值的方格来生成的。
三、功能拓广
1.
使用二叉堆优化开放列表,缩短检索的时间,因为它是最耗时的;
2.
A*的最小路径问题;
3.
对于不同大小的人物角色的寻路技巧;
4.
与Djikstra算法的对比;
(这部分下次有空的时候好好的补上.)
四、优缺点
网上有很多。
先去睡觉了,下次再分享一个大牛的代码,我先整理下。
分享到:
相关推荐
使用C++实现基于A*算法的N数码问题,是8数码问题的拓展。
对下图所示的迷宫问题,用A*算法为机器人搜索一条路径: 其中(1, 1) 为起始点,(4, 4) 为目标点,启发函数采用曼哈顿距离。
资源为Hybrid A * 算法Python源码,该资源是博客 动力学约束下的运动规划算法——Hybrid A*算法(附程序实现... 第三部分是结合前面第一部分的理论和第二部分的详细源码,对Hybrid A * 算法的流程进行综合的概括总结。
A star算法 + 随机迷宫 + matlab
人工智能 a*算法 八数码 java 人工智能课程设计报告 计算机软件与理论 文档大概内容:数码问题;八数码问题形式化描述;解决方案;A*算法; A*搜索算法一般介绍;...A*算法的实现等总结与程序源代码:
基于python的A星算法实现8数码问题实验源码+代码详细注释+项目说明+实验结果及总结.7z 人工智能 课程作业 Astar算法是一种求解最短路径最有效的直接搜索方法,也是许多其他问题的常用启发式算法。它的启发函数为f(n)...
这是Object Detection in 20 Years A Survey总结汇报,内含完整的24页制作的ppt内容,详细而又覆盖几乎所有的论文中的内容。
阵列信号处理作为信号处理的一个重要分支,在通信、雷达、声纳、地震勘探和射电天文等领域内获得了广泛应用和迅速发展。阵列信号处理将一组传感器按一定方式布置在空间不同位置上,形成传感器阵列。...
算法学习总结: 1.初始化开列表,关列表; 2.起点计算周围节点f值(g+h);周围节点放入开列表,起点加入关列表; 3.从开列表取f值最小值作为当前节点,加入关列表并从开列表中移除; 4.计算当前节点周围节点f值(g+h);...
2021年度A股行情总结:守得云开见月明.pdf
1. What will be the output of the following C code? #include int main(int argc, char* argv[]) ...(A)a += (a++); (B) a += (++a) ; (C) (a++) += a; (D) (++a) += (a++); 22. 下面程序的输出为: union{
通过实验提高学生编写实验报告、总结实验结果的能力;使学生对智能程序、智能算法等有比较深入的认识。 1.掌握人工智能中涉及的相关概念、算法。 2.熟悉人工智能中的知识表示方法; 3.熟悉盲目搜索和启发式搜索算法...
QW 20090427 第2章 A 公式总结QW 20090427 第2章 A 公式总结
1. 采用 C++语言实现 A*算法的求解八数码问题的程序,设计了两种不同的估价函数: 2. 设置相同初始状态和目标状态,针对两种的估价函数,求得问题的解,并比
(完整版)新概念英语青少版-starter-A-知识点总结(全).pdf
全面总结A星寻路,希望对您有所帮助,谢谢支持
特写此篇博客用来总结, 并写了寻路算法的代码, 觉得有用的同学可以看看. 另外因为图片制作起来比较麻烦, 所以我用的是原文里的图片. 当然寻路算法不止 A* 这一种, 还有递归, 非递归, 广度优先, 深度优先, 使用堆栈...
对下图所示的迷宫问题,用A*算法为机器人搜索一条路径: 其中(1, 1) 为起始点,(4, 4) 为目标点,启发函数采用曼哈顿距离。
2010全国大学生数学建模A题方法总结(经典),对于A题相当大帮助!
TSS721的应用总结和MBUS协议中的数据桢格式