« eve 随想及虚拟物品交易合法化 | 返回首页 | 读了一篇文章 »

A* 算法之误区

估计是因为我在上大学时在网上留过一篇文章，里面有一个简单的使用 A* 算法寻路的源程序，导致了这近七年来，不段的收到 email 和我讨论这个算法。

对，毫不夸张。那个简陋的代码。在七年前我随手写出来扔在网上后，已经遍布中文网络世界的犄角旮旯，让我在痛恨那段代码的时候，想收回都不可能。

我最大的困惑在于，为什么课堂上最为基础的算法知识，却有如此多的人行入误区。难道写游戏的程序员都不去读读基本的课本？

A* ，读作 A-Star 。它仅仅是一个启发式搜索算法。就是说在一个可以被穷举的有限解空间集中，用比较有效的方法（主要是利用估价函数）求出最优解的算法。A* 跟寻路算法没有太多关系，我们只是借助了这个方法来解决寻路这个问题，正如四则运算对于数学题一样，它只是一个基本工具。寻路算法本身有很多种，我们找到算法后，借助 A* 这个工具实现这个算法而已。

我的那篇文章中提到的，也是传统意义上的地图寻路，其实依据的是这样一种算法：把地图分成若干个格子，把起始点的格子上标作 0 。然后根据将周围一圈可以通畅的格子上标为1。然后再把所有标上 1 的格子周围可以通达的格子标为 2 ，当然，如果那些格子上已经有过数字了（一定比 2 小）就不用标了。

如此反复迭代下去，我们地图上的终点只要可以通达，就一定会被标上数字。而这个数字就是理论最短的距离，而标记过的每个格子都有一个前导的入口（即它由附近一个比它小 1 的格子引导过来）整个标记的过程逆推，也就找到了最短路径。

这种一步步尝试的过程，就是一种搜索过程。如果加上启发函数，不让它盲目的寻找，就衍生出很多启发式搜索算法。A* 是其中的一种。之所以加一个 * 号，是因为它的启发式函数是有限制的，这个限制确保它能找到绝对最优解，去掉这个限制，就是 A 算法了。

我们可以看到，把地图分格子，给格子间的路径一个权值（前面的例子中，格子间的距离都是相等的，我们也可以根据地形划分成不等的距离，即权值，或者定义单向道路，这都是可以的），这是解决寻路问题的关键，但都不是 A* 算法的范畴。

如果你想出某种算法，比如把地图划分成不规则的区域，或者把地图矢量化。依然可以再此基础上用 A* 算法这个工具来从中求到最优解。如果想别的方法来寻路，比如拟人的判断，预设路点等等，甚至按走迷宫的方法一样，分叉右转，碰壁回头，那些可以算是对分格寻路方法的一些改进，却都不关 A* 什么事情。

A* 算法理论上 是时间最优的 可以得到最优解，不过我们可以通过选择一个更好的估价函数，或是减少解空间来提高性能。 A* 算法最大的缺点就是，空间需求太大。我们可以用一些时间换空间的方法改进。但是如果不存在解（比如在寻路问题中，根本不存在一条通达的路），采用 A* 算法求解，势必会穷举所有的可能。所以一般在游戏里，我们一般会采用额外的手法避免这个问题。

ps. 如果用 waypoint 的方法来解决寻路问题，实际上将地图化成了一个图，经典的最短路径算法是 dijkstra 算法。若是把地图的阻挡物用凸多边形描述，有一道 10 年前的 ACM 赛题可以参考：Cutting Corners。

云风 提交于 July 8, 2006 03:01 AM |

Comments

没想到项目中的寻路算法还是用了优化后的A*寻路

Posted by: kanghaov | (16) October 19, 2020 05:27 PM

請問能不能提供文中提到的課本的書名和作者 感謝

Posted by: 墨貓 | (15) April 5, 2014 04:19 AM

请问A算法（没有*）和A*算法的区别是什么，特别是在代码上的不同，googleA算法出来的竟然都是A星算法

Posted by: 您好 | (14) October 6, 2013 09:37 AM

11年前我就拜读您的文章。您的文章是我的算法方面的启蒙读物了。您不介意我11年之后才知道A×算法的原理吧。这个方法您解释的太简单了，您的很多文章我都只是似懂非懂而已，但是能看出您的用心和淡定

Posted by: Anonymous | (13) March 6, 2013 08:01 PM

很好！

Posted by: Jason | (12) September 6, 2011 12:42 AM

野人过河问题的关键是设置启发函数，这里启发函数设为：h(n)=m+c-2b即可。m为左岸野人数，c为左岸传教士人数，b为左岸船数。初始状态和目标状态分别为：(331)和（000）

Posted by: fancy | (11) March 31, 2010 10:56 AM

你好！我有个问题想请教您一下，呵呵。我们老师留了一个作业，要求用A*算法实现野人过河问题，我想了想，觉得用A*算法实现这个问题，没有什么好方法，你觉得呢？深度搜索就挺好，用A*怎么用啊？

Posted by: bubu | (10) January 2, 2010 09:13 PM

“A* 算法理论上是时间最优的”这句话有歧意，或许是表达错误。这里的“时间”并不是指求出解需要的时间。 这里我原本想表达的“时间”的含义是：在地图寻路问题上，求得的路径（问题的解）最短，即沿这条路径运动的时间最短。

Posted by: Cloud [TypeKey Profile Page] | (9) December 11, 2007 03:32 PM

啊，打错字了，不好意思 前面第一行和第三行的“A算法”其实应该改成“A* 算法” 对不住啦

Posted by: 张** | (8) October 4, 2007 12:12 PM

大家好，新手报到。 我认为A*算法也未必是时间最优的，因为要选择一个符合A*算法限制条件的估价函数很难，而且其运算复杂度也可能很大，这就不能保证其时间最优。而对于一个A算法的估价函数，可能在空间上和时间上都比较有优势。当然也要看情况而定。 如有错误，恳请指正，谢谢各位关照。

Posted by: 张** | (7) October 4, 2007 12:07 PM

Delphi

Posted by: jufei | (6) July 25, 2006 01:19 PM

A*可以用于任何一种state space的搜索问题。 可以看看Sven Koenig的D* Lite，因为信息可以重用，动态环境下显著优于A*，但是比Stentz的D*容易修改。 非规则地图可以用若干分辨率不同的地图混合解决。美国的火星探路器用过D*作为粗地图找路部分。

Posted by: 路过 | (5) July 16, 2006 05:16 AM

呵呵。明白，只是想顺便讨论一下。 另外一个问题是这个最优是不是一定是最好？

Posted by: HappyChui [TypeKey Profile Page] | (4) July 12, 2006 11:13 PM

呵呵，其实我这篇文章的意思是 astar 跟游戏里的寻路算法没有什么直接的联系。 只是实现寻路算法时的一个工具而已。就跟做数学题的时候，四则运算只是一种工具，而不是解题的直接方法。 ps. astar 算法得到的是最优解是可以被理论证明的。如果得到的不是最优解，那么就是实现的时候出了什么问题，或者是没有完全按照 astar 的定义去实现。

Posted by: Cloud [TypeKey Profile Page] | (3) July 12, 2006 02:28 PM

哈哈，终于有机会发个言，水平不好请大家不要扔垃圾:P 我记得我是99年还2000年的时候第一次看云风的网页，那时特别的兴奋。说起来云风你可是我的偶像。（大家不要见笑，说真的） 题外话说到这里。寻路确实是很多新手的一大难题，我也遇到不少挫折。A*是很优的算法，不过算出来并不是最优的路径，而且在复杂的地方上路径很难看，如果不加修饰的话基本上一看就看出是A*算出的路径。特别是在一些T字形状的位置。（可能是我水平问题，不知道大家是不是跟我一样） 其实一般游戏里的寻路都是很少的一个区域，基本上不花什么CPU资源（除非你是做网游的外挂），只要加上一个寻找的深度或者距离已经足够。这时候用那种权值基本上都不会起太大的作用。

Posted by: HappyChui [TypeKey Profile Page] | (2) July 12, 2006 09:24 AM

这么早啊

Posted by: Ninstein | (1) July 10, 2006 05:29 AM

Post a comment

非这个主题相关的留言请到：留言本