A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为: f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数,
g(n) 是在状态空间中从初始节点到n节点的实际代价,
h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径(最优解的)条件,关键在于估价函数h(n)的选取:
估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。
如果 估价值>实际值, 搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。
估价值与实际值越接近,估价函数取得就越好。
例如对于几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价值,即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny));这样估价函数f在g值一定的情况下,会或多或少的受估价值h的制约,节点距目标点近,h值小,f值相对就小,能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程:
创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点,将n节点放入CLOSE中,取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小,从最小路径的节点向下进行。
}
上图是和上面Dijkstra算法使用同一个路网,相同的起点终点,用A*算法的情况,计算的点数从起始点逐渐向目标点方向扩展,计算的节点数量明显比Dijkstra少得多,效率很高,且能得到最优解。
A*算法和Dijistra算法的区别在于有无估价值,Dijistra算法相当于A*算法中估价值为0的情况。
分享到:
相关推荐
用matlab写的A*算法,可自行定义Target,Start与Obstacle
a-star算法在vc环境下的实现。动态选择最优路径
D star 搜索算法,从目标节点向起始点搜索,机器人沿最短路径开始移动,机器人路径规划探路的一种算法
基于matlab的A-star算法实现,有地图模拟,动态展现寻路过程。
基于A*算法的机器人路径规划的MATLAB实现,可自由选择地图和起始终止点,并且含有简单的文档和ppt。上一次上传的因为下载量比较多下载需要积分自动增加了,所以重新传一份,供大家下载。
C++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS...
A*算法 A star 算法(matlab)版本,可以直接使用,包含路径优化。直接下载即可运行。A*算法 A star 算法(matlab)版本,可以直接使用,包含路径优化。直接下载即可运行。
基于混合A-Star算法的停车路径规划C++实现源码.zip基于混合A-Star算法的停车路径规划C++实现源码.zip基于混合A-Star算法的停车路径规划C++实现源码.zip基于混合A-Star算法的停车路径规划C++实现源码.zip基于混合A-...
D*算法 是动态 A*(D-Star
A*路径寻找算法入门 初步:搜索区域 开始搜索 路径排序 ...
用自己改进的ASTAR算法实现迷宫问题,效率还是可以的。
人工智能里的A-star算法是一种常用的算法,适用于机器人的路径规划和寻优。在这个算法中,机器人将尝试沿着最短的路径到达目的地。该算法的优势在于通过估计每个节点到目的地的距离,可以避免探索不必要的节点,从而...
A_star算法路径规划,实现二位平面路劲规划,基本算法
AS3游戏常用寻路算法 astar(a星)算法 - A*算法 原理简介 A*(A-Star)算法是一种静态路网中求解最短路最有 A star 算法在静态路网中的应用 效的方法。
A_star算法matlab程序,A_star算法matlab程序,A_star算法matlab程序
1、资源内容:基于Matlab利用A star算法实现路径规划仿真(源码+图片).rar 2、适用人群:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业或毕业设计,作为“参考资料”使用。 3、更多仿真源码和数据...
会者不难,A*(念作A星)算法对初学者来说的确有些难度。 压缩包包括C++语言的A*算法源代码和技术说明文档,如果你只是想看看它的运行效果...技术说明文档描述了算法的原理,还有大量的图片帮助你更容易理解A Star算法。
1、资源内容:基于Matlab实现A star算法路径仿真(源码+数据).rar 2、适用人群:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业或毕业设计,作为“参考资料”使用。 3、解压说明:本资源需要电脑端...
A star 算法的C++语言实现(A* 算法接口,针对迷宫问题设计)
D*算法又称为动态A*算法,在未知环境或有动态障碍物出现时,采用A*算法需要丢弃初始规划完成的open表和close表,重新进行规划。造成规划时间的增加,D*算法的核心思想是先用dijkstra或A*从目标点向初始点进行反向...