算法一：A*寻路初探
译者序：很久以前就知道了 算法，但是从未认真读过相关的文章，也没有看过代码，只是脑子里
有个模糊的概念。这次决定从头开始，研究一下这个被人推崇备至的简单方法，作为学习人工智能的开
始。
这篇文章非常知名，国内应该有不少人翻译过它，我没有查找，觉得翻译本身也是对自身英文水平的锻
炼。经过努力，终于完成了文档，也明白的 算法的原理。毫无疑问，作者用形象的描述，简洁诙谐的
语言由浅入深的讲述了这一神奇的算法，相信每个读过的人都会对此有所认识。
原文链接：
以下是翻译的正文。由于本人使用 编辑，所以没有对原文中的各种链接加以处理除了图表，
也是为了避免未经许可链接的嫌疑，有兴趣的读者可以参考原文。
会者不难，A*(念作 A 星)算法对初学者来说的确有些难度。
这篇文章并不试图对这个话题作权威的陈述。取而代之的是，它只是描述算法的原理，使你可以在
进一步的阅读中理解其他相关的资料。
最后，这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿，我在文章的
末尾包含了一个指向例子程序的链接。 压缩包包括 和 ! 两个语言的版本，如果你只是想
看看它的运行效果，里面还包含了可执行文件。我们正在提高自己。让我们从头开始。。。
序：搜索区域
假设有人想从 点移动到一墙之隔的 点，如图，绿色的是起点 ，红色是终点 ，蓝色方块是中间的
墙。
!"图 #$
!!!!你首先注意到，搜索区域被我们划分成了方形网格。像这样，简化搜索区域，是寻路的第一步。这一
方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块，方块被标记为可通过的
和不可通过的。路径被描述为从 到 我们经过的方块的集合。一旦路径被找到，我们的人就从一个方
格的中心走向另一个，直到到达目的地。
这些中点被称为“节点”。当你阅读其他的寻路资料时，你将经常会看到人们讨论节点。为什么不把他
们描述为方格呢？因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形，六角形，
或者其他任意形状。节点能够被放置在形状的任意位置－可以在中心，或者沿着边界，或 其他什么地方 。
我们使用这种系统，无论如何，因为它是最简单的。
开始搜索
正如我们处理上图网格的方法，一旦搜索区域被转化为容易处理的节点，下一步就是去引导一次找
到最短路径的搜索。在 寻路算法中，我们通过从点 开始，检查相邻方格的方式，向外扩展直到找到
剩余24页未读，继续阅读
评论1