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的情况。
分享到:
相关推荐
在这个“a star算法matlab”项目中,开发者可能已经创建了一个能够根据用户自定义的起点(Start)、终点(Target)和障碍物(Obstacle)来寻找最短路径的程序。 A*算法的核心在于使用启发式函数(heuristic ...
在这个迷宫问题中,我们用A_Star算法进行路径规划,通过优化策略提升了算法的效率。 首先,理解A_Star算法的核心思想至关重要。它基于两个主要概念:F(n)、G(n) 和 H(n)。F(n) 是节点n的总成本,由到达该节点的实际...
**D*(D-star)算法**是一种用于机器人路径规划的高效搜索算法,它在动态环境中尤其有用,因为其能够实时地更新路径以适应环境变化。D*算法是Dijkstra算法的扩展,它优化了从起点到目标点的路径,不仅考虑了初始状态...
基于matlab的A-star算法实现,有地图模拟,动态展现寻路过程。
A*(A-Star)算法是一种在图形搜索中用于找到从起点到终点的最短路径的启发式搜索算法。它结合了Dijkstra算法的全局最优性和Greedy最佳优先搜索算法的效率,通过引入一个评估函数来预测从当前节点到目标节点的估计...
C++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS中的A-star算法去ROS处理项目源码.zipC++实现将ROS...
**DStar算法详解** 在计算机科学和人工智能领域,路径搜索是一个关键问题,特别是在导航系统、游戏AI和机器人路径规划中。DStar算法(Dynamic A*)是为了解决这一问题而设计的一种高效、灵活的寻路算法。它是由...
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-...
在“A_star算法路径规划”项目中,可能包含了一个二维平面的地图,其中不同区域表示障碍物,A*算法用于找到从起点到终点的最优路径。MATLAB程序可能包括读取地图数据、设置启发式函数、实现A*算法逻辑以及可视化路径...
A*(发音"A-star")算法是一种广泛应用的路径搜索算法,源自Dijkstra的最短路径算法,但通过引入启发式信息来提高效率。在VC环境下实现A*算法,主要是为了在图形界面或游戏开发中寻找从起点到终点的最短或最优路径。...
D*(发音为 "D-star")算法是路径规划领域的一个重要突破,由Koenig和Likhachev在2002年提出,是一种动态A*(Dynamic A*)搜索算法,旨在解决环境变化时的实时路径更新问题。本文将深入探讨D*算法的基本原理、优势...
【基于A-star算法控制的井下搬运系统研究】 在井下采矿作业中,搬运系统扮演着至关重要的角色,它与采掘等综合采煤设备协同工作,其效率直接影响着整个煤矿的生产能力。随着计算机技术、传感器技术的进步,井下搬运...
A*算法是一种广泛应用的路径搜索算法,尤其在游戏开发、地图导航等领域中起到关键作用。它结合了Dijkstra算法的最优性和Best First Search的效率,通过评估每个节点的F值(即G值和H值之和)来找到从起点到终点的最短...
【基于D-star算法移动机器人避障路径规划MATLAB代码】是一种用于实现机器人自主导航的关键技术。D-star(D*)算法是一种高效的动态路径规划方法,适用于环境变化的情况,如机器人在未知或动态环境中避障。它是在A*...
人工智能里的A-star算法是一种常用的算法,适用于机器人的路径规划和寻优。在这个算法中,机器人将尝试沿着最短的路径到达目的地。该算法的优势在于通过估计每个节点到目的地的距离,可以避免探索不必要的节点,从而...
《基于RRT_Star算法实现无人机三维路径规划含Matlab源码》 在现代无人机技术中,路径规划是一项至关重要的任务,它确保无人机能够在复杂的环境中安全、高效地移动。RRT_Star( Rapidly-exploring Random Tree Star...
### A*算法(A-Star算法) #### 原理与应用概述 A*(A-Star)算法是一种在静态路网中寻找最短路径的有效方法。它结合了Dijkstra算法(一种经典的图遍历算法,用于查找图中两点之间的最短路径)与启发式搜索的优点...
**A-Star算法求解旅行商问题** 旅行商问题(Traveling Salesman Problem,TSP)是一个经典的组合优化问题,它要求找到访问给定城市集合中的每个城市一次,并最终返回起点的最短路径。A-Star(A*)算法是一种启发式...
在给定的"svm-matlab.rar"压缩包中,包含了一个SVM的Matlab实现,重点在于d-star和d-star算法的训练过程以及训练特征的处理。 函数`[D, a_star] = SVM(train_features, train_targets, params, region)`是这个SVM...