A*算法

A*算法，A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算培侵外过法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

• 中文名称 A*算法
• 外文名称 A-star algorithm
• 别名 启发式搜索
• 表达式 f(n)=g(n)+h(n)
• 运行条件 静态网路

原理

　　A* (A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意--是最有效的直接搜索算法，之后涌现了很多预处理算法(如CH)，在线查询北环诗效率是A*算法的数千甚至上万倍。

　　公式表示为: f*(n)=g*(n)+h*(n),

　　其中， f*(n) 是从初始状态经由状态n到目标状态的最小代价估来自计，

　　g*(n) 是在状态空间中从初始状态到状态n的最小代价，

　　h*360百科(n) 是从状态n到目标状态的路径的最小估计代价。

　　(对于路径搜索问题，状态就是图中的节点，代价就是距离)

　　真实h界雷足(n)的选取:

　　保宽明证找到最短路径(最优解的)条件，关键在于估价函数f(n)够搞兵为的选取(或者说h(n)的选取)。

　　以h(n)表达状态n到目标状态估计的距离，那么h(n)的选取大致有如下三种情况:

1. 如果h(n)< h*(n)，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
2. 如果h(n)=h*(n)，此管讲血尼式时的搜索效率是最高的。
3. 如果 h(n)>h*(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

简单案例

　　参见参考资料中的"A*算法入门" 。

　　另外，A*同样可以用于其他搜索问题，只需要对应状态和状态的距离即可。

算法分类

　　该算法在最短路径搜索算法中分类为:

　　直接搜索算法:直接在实际地来自图上进行搜索，不经过任何预处理;

　　启发式算法:通过启发函数引导算法的搜索方向;

　　静态图搜索算法:被搜索的图的权值不随时间变化(后被证明同样可以适用于动态图的搜索 )。

实际运用

　　距离估计与实际值越接近，估价函数取得就越好

　　例如对于几何路网来360百科说，可以取两节点间曼哈顿距离做为距离估计，即f流济只集掌龙磁=g(n) + (abs(dx - nx) + abs(dy - ny))家分派帮厚首附;这样估价函数f(n)在g(n)一定的情况下，会或多或少的受距离估计值h(n)的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显笑属情载盟格跳收识优于Dijkstra算法的毫无方向的向四周搜索。

　　算法实现(路径搜索)

　　创建两个表，OPEN表保存所有已生成而未考讨评低察的节点，CLOSED表中记房继录已访问过的节点对百言发。

　　算起点的h(s);

　　将起点放入OPEN表;

　　保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径;

　　用C语言实现A*最短路径搜索算法，作者 Tittup frog(跳跳蛙)。

其它算法

　　启发式搜索着永植温答其实有很多的算法

　　比如:局部择优搜索法、最好优先搜索法等等，当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。像局部择优搜索法，就是在搜索的过程中选取"最佳节点"后舍弃其他的兄弟节点、父亲节点，而一直得搜索下去。这种搜索的结果很明显低非施务均无宣争眼，由于舍弃了其他的节点，沙可能也把最好的节点都舍弃了，因为求解的最佳节点否体化伟创来只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，它在搜索时，并没有舍弃节点(除非该节点是死节点)，在每一步的估价中都把当前的节点和以前的节点的f(n)比较得到一个"最佳的节点"，这样可以有效的防止"最佳节点"的丢失。那么A*算法又是一种什么样的算法呢?

好处

　　其实A*算法也是一种层系位准最好优先的算法

　　只不过要反屋约敌之所吗细章百加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索易略告降烟你我的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的!

　　我们先下个定义，如果一个估价函数可以张律作家费且找出最短的路径，温终称养待船我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示二问肉微建意谓验次率置为:

　　f'(n) = g'(n) + h'(n)

　　这里，f'(n)是估价函数，g'(n)是起点到节点n的最短路径值，h'(n)是停毫n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的稳称轴估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可(大多数情况下都是满足的，可以不用考虑)，h(n)代替h'(n)，但h(n)<=h'(n)才可(这一点特别的重要)。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。

　　举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。

　　再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的不甚为好的原因了，因为它的h(n)=0，没有一点启发信息。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。