作者文章链接：http://www.policyalmanac.org/games/aStarTutorial.htm
启示式搜索：启示式搜索就是在状态空间中的搜索对每个搜索的位置进行评估，得到最好的位置。再从这个位置进行搜索直到目标。
这样能够省略大量无畏的搜索路径。提到了效率。
在启示式搜索中，对位置的估价是十分重要的。採用了不同的估价能够有不同的效果。
估价函数：从当前节点移动到目标节点的预估费用；这个预计就是启示式的。
在寻路问题和迷宫问题中，我们通经常使用曼哈顿（manhattan）估价函数（下文有介绍）预估费用。
A*算法与BFS：能够这样说。BFS是A*算法的一个特例。对于一个BFS算法，从当前节点扩展出来的每个节点（假设没有被訪问过的话）都要放进队列进行进一步扩展。也就是说BFS的预计函数h永远等于0。没有一点启示式的信息。能够觉得BFS是“最烂的”A*算法。
选取最小估价：假设学过数据结构的话，应该能够知道，对于每次都要选取最小估价的节点。应该用到最小优先级队列（也叫最小二叉堆）。在C++的STL里有现成的数据结构priority_queue，能够直接使用。当然不要忘了重载自己定义节点的比較操作符。
A*算法的特点：A*算法在理论上是时间最优的，可是也有缺点：它的空间增长是指数级别的。
IDA*算法：这样的算法被称为迭代加深A*算法。能够有效的解决A*空间增长带来的问题，甚至能够不用到优先级队列。假设要知道具体：google一下。
A*寻路初探（转载）
作者：Patrick Lester
译者：Panic2005年
译者序：非常久曾经就知道了A*算法，可是从未认真读过相关的文章，也没有看过代码，仅仅是脑子里有个模糊的概念。这次决定从头開始，研究一下这个被人推崇备至的简单方法，作为学习人工智能的開始。
这篇文章很知名，国内应该有不少人翻译过它。我没有查找。认为翻译本身也是对自身英文水平的锻炼。经过努力，最终完毕了文档，也明确的A*算法的原理。毫无疑问，作者用形象的描写叙述，简洁诙谐的语言由浅入深的讲述了这一奇妙的算法，相信每一个读过的人都会对此有所认识（假设没有，那就是偶的翻译太差了--b）。
如今是年月日的版本号。应原作者要求，对文中的某些算法细节做了改动。
原文链接：http://www.gamedev.net/reference/articles/article2003.asp
原作者文章链接：http://www.policyalmanac.org/games/aStarTutorial.htm
下面是翻译的正文
会者不难，A*(念作A星)算法对刚開始学习的人来说的确有些难度。这篇文章并不试图对这个话题作权威的陈述。
取而代之的是。它仅仅是描写叙述算法的原理，使你能够在进一步的阅读中理解其它相关的资料。最后，这篇文章没有程序细节。你尽能够用随意的计算机程序语言实现它。如你所愿，我在文章的末尾包括了一个指向样例程序的链接。
压缩包包括C++和Blitz Basic两个语言的版本号，假设你仅仅是想看看它的执行效果，里面还包括了可执行文件。我们正在提高自己。让我们从头開始。
。。
序：搜索区域
如果有人想从A点移动到一墙之隔的B点，例如以下图。绿色的是起点A。红色是终点B，蓝色方块是中间的墙。
[图-1]
你首先注意到。搜索区域被我们划分成了方形网格。像这样。简化搜索区域，是寻路的第一步。这一方法把搜索区域简化成了一个二维数组。
数组的每个元素是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描写叙述为从A到B我们经过的方块的集合。一旦路径被找到，我们的人就从一个方格的中心走向还有一个，直到到达目的地。
这些中点被称为“节点”。
当你阅读其它的寻路资料时。你将常常会看到人们讨论节点。为什么不把他们描写叙述为方格呢？由于有可能你的路径被切割成其它不是方格的结构。
他们全然能够是矩形。六角形，或者其它随意形状。节点能够被放置在形状的任何位置－能够在中心。或者沿着边界，或其它什么地方。我们使用这样的系统，不管怎样，由于它是最简单的。
開始搜索
正如我们处理上图网格的方法，一旦搜索区域被转化为easy处理的节点。下一步就是去引导一次找到最短路径的搜索。在A*寻路算法中，我们通过从点A開始，检查相邻方格的方式，向外扩展直到找到目标。
我们做例如以下操作開始搜索：
1，从点A開始。而且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。虽然如今列表里仅仅有一个元素，但以后就会多起来。你的路径可能会通过它包括的方格，也可能不会。
基本上，这是一个待检查方格的列表。
2，寻找起点周围全部可到达或者可通过的方格，跳过有墙，水，或其它无法通过地形的方格。也把他们增加开启列表。为全部这些方格保存点A作为“父方格”。
当我们想描写叙述路径的时候，父方格的资料是十分重要的。
后面会解释它的详细用途。
3。从开启列表中删除点A，把它增加到一个“关闭列表”。列表中保存全部不须要再次检查的方格。
在这一点，你应该形成如图的结构。
在图中，暗绿色方格是你起始方格的中心。
它被用浅蓝色描边，以表示它被增加到关闭列表中了。全部的相邻格如今都在开启列表中，它们被用浅绿色描边。每一个方格都有一个灰色指针反指他们的父方格，也就是開始的方格。
[图-2]
接着，我们选择开启列表中的临近方格，大致反复前面的过程，例如以下。可是。哪个方格是我们要选择的呢？是那个F值最低的。
路径评分
选择路径中经过哪个方格的关键是以下这个等式：F = G + H
这里：
* G = 从起点A。沿着产生的路径。移动到网格上指定方格的移动耗费。
* H = 从网格上那个方格移动到终点B的预估移动耗费。这常常被称为启示式的。可能会让你有点迷惑。这样叫的原因是由于它仅仅是个推測。我们没办法事先知道路径的长度，由于路上可能存在各种障碍(墙，水。等等)。尽管本文仅仅提供了一种计算H的方法，可是你能够在网上找到非常多其它的方法。
我们的路径是通过重复遍历开启列表而且选择具有最低F值的方格来生成的。文章将对这个过程做更具体的描写叙述。首先。我们更深入的看看怎样计算这个方程。
正如上面所说，G表示沿路径从起点到当前点的移动耗费。在这个样例里，我们令水平或者垂直移动的耗费为。对角线方向耗费为。我们取这些值是由于沿对角线的距离是沿水平或垂直移动耗费的的根号（别怕）。或者约.414倍。为了简化，我们用和近似。比例基本正确，同一时候我们避免了求根运算和小数。
这不是仅仅由于我们怕麻烦或者不喜欢数学。
使用这种整数对计算机来说也更快捷。
你不就就会发现，假设你不使用这些简化方法，寻路会变得非常慢。
既然我们在计算沿特定路径通往某个方格的G值。求值的方法就是取它父节点的G值，然后按照它相对父节点是对角线方向或者直角方向(非对角线)，分别添加和。样例中这种方法的需求会变得很多其它，由于我们从起点方格以外获取了不止一个方格。
H值能够用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。然后把结果乘以10。这被称为曼哈顿方法是由于它看起来像计算城市中从一个地方到另外一个地方的街区数。在那里你不能沿对角线方向穿过街区。
非常重要的一点。我们忽略了一切障碍物。这是对剩余距离的一个估算。而非实际值，这也是这一方法被称为启示式的原因。想知道很多其它？你能够在这里找到方程和额外的注解。
F的值是G和H的和。
第一步搜索的结果能够在以下的图表中看到。F,G和H的评分被写在每一个方格里。正如在紧挨起始格右側的方格所表示的，F被打印在左上角。G在左下角，H则在右下角。
[图-3]
如今我们来看看这些方格。写字母的方格里，G = 10。
这是由于它仅仅在水平方向偏离起始格一个格距。
紧邻起始格的上方，下方和左边的方格的G值都等于。
对角线方向的G值是。
H值通过求解到红色目标格的曼哈顿距离得到，当中仅仅在水平和垂直方向移动，而且忽略中间的墙。用这样的方法，起点右側紧邻的方格离红色方格有格距离，H值就是。
这块方格上方的方格有格距离(记住。仅仅能在水平和垂直方向移动)，H值是。你大致应该知道怎样计算其它方格的H值了～。
每一个格子的F值，还是简单的由G和H相加得到
继续搜索
为了继续搜索，我们简单的从开启列表中选择F值最低的方格。
然后，对选中的方格做例如以下处理：
4。把它从开启列表中删除。然后加入到关闭列表中。
5。检查全部相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙，水的地形，或者其它无法通过的地形)，把他们加入进开启列表。假设他们还不在里面的话。把选中的方格作为新的方格的父节点。
6，假设某个相邻格已经在开启列表里了，检查如今的这条路径是否更好。换句话说，检查假设我们用新的路径到达它的话。G值是否会更低一些。假设不是，那就什么都不做。
还有一方面。假设新的G值更低，那就把相邻方格的父节点改为眼下选中的方格（在上面的图表中，把箭头的方向改为指向这个方格）。
最后，又一次计算F和G的值。假设这看起来不够清晰，你能够看以下的图示。
好了，让我们看看它是怎么运作的。我们最初的格方格中，在起点被切换到关闭列表中后，还剩格留在开启列表中。
这里面，F值最低的那个是起始格右側紧邻的格子，它的F值是。
因此我们选择这一格作为下一个要处理的方格。在紧随的图中。它被用蓝色突出显示。
[图-4]
首先，我们把它从开启列表中取出，放入关闭列表(这就是他被蓝色突出显示的原因)。
然后我们检查相邻的格子。哦，右側的格子是墙。所以我们略过。左側的格子是起始格。它在关闭列表里，所以我们也跳过它。
其它格已经在开启列表里了，于是我们检查G值来判定。假设通过这一格到达那里，路径是否更好。我们来看选中格子以下的方格。它的G值是。假设我们从当前格移动到那里，G值就会等于(到达当前格的G值是，移动到上面的格子将使得G值添加)。由于G值大于，所以这不是更好的路径。
假设你看图，就能理解。与其通过先水平移动一格，再垂直移动一格，还不如直接沿对角线方向移动一格来得简单。
当我们对已经存在于开启列表中的个临近格反复这一过程的时候。我们发现没有一条路径能够通过使用当前格子得到改善，所以我们不做不论什么改变。既然我们已经检查过了全部邻近格。那么就能够移动到下一格了。
于是我们检索开启列表，如今里面仅仅有7格了，我们仍然选择当中F值最低的。有趣的是，这次，有两个格子的数值都是。
我们怎样选择？这并不麻烦。从速度上考虑，选择最后加入进列表的格子会更快捷。这样的导致了寻路过程中。在靠近目标的时候。优先使用新找到的格子的偏好。但这无关紧要。
（对同样数值的不同对待，导致不同版本号的A*算法找到等长的不同路径）那我们就选择起始格右下方的格子，如图：
[图-5]
这次，当我们检查相邻格的时候，发现右側是墙。于是略过。上面一格也被略过。我们也略过了墙以下的格子。为什么呢？由于你不能在不穿越墙角的情况下直接到达那个格子。
你的确须要先往下走然后到达那一格，按部就班的走过那个拐角。(注解：穿越拐角的规则是可选的。
它取决于你的节点是怎样放置的。)
这样一来。就剩下了其它格。当前格以下的另外两个格子眼下不在开启列表中，于是我们加入他们，而且把当前格指定为他们的父节点。
其余格，两个已经在关闭列表中（起始格，和当前格上方的格子。在表格中蓝色高亮显示),于是我们略过它们。最后一格，在当前格的左側，将被检查通过这条路径，G值是否更低。不必操心，我们已经准备好检查开启列表中的下一格了。
我们反复这个过程。直到目标格被加入进关闭列表(注解)，就如在以下的图中所示。
[图-6]
注意。起始格下方格子的父节点已经和前面不同的。
之前它的G值是。而且指向右上方的格子。如今它的G值是，指向它上方的格子。这在寻路过程中的某处发生。当应用新路径时，G值经过检查变得低了－于是父节点被又一次指定。G和F值被又一次计算。虽然这一变化在这个样例中并不重要。在非常多场合，这样的变化会导致寻路结果的巨大变化。
那么，我们怎么确定这条路径呢？非常easy，从红色的目标格開始，按箭头的方向朝父节点移动。这终于会引导你回到起始格。这就是你的路径！看起来应该像图中那样。从起始格A移动到目标格B仅仅是简单的从每一个格子（节点）的中点沿路径移动到下一个，直到你到达目标点。
就这么简单。
[图-7]
A*方法总结
好，如今你已经看完了整个说明。让我们把每一步的操作写在一起：
1，把起始格加入到开启列表。
2，反复例如以下的工作：
a) 寻找开启列表中F值最低的格子。
我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的格中的每个？
* 假设它不可通过或者已经在关闭列表中。略过它。反之例如以下。
* 假设它不在开启列表中，把它加入进去。
把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* 假设它已经在开启列表中，用G值为參考检查新的路径是否更好。更低的G值意味着更好的路径。假设是这样，就把这一格的父节点改成当前格，而且又一次计算这一格的G和F值。
假设你保持你的开启列表按F值排序，改变之后你可能须要又一次对开启列表排序。
d) 停止。当你
* 把目标格加入进了关闭列表(注解)。这时候路径被找到，或者
* 没有找到目标格。开启列表已经空了。这时候。路径不存在。
3.保存路径。从目标格開始，沿着每一格的父节点移动直到回到起始格。
这就是你的路径。
(注解:在这篇文章的较早版本号中，建议的做法是当目标格（或节点）被增加到开启列表，而不是关闭列表的时候停止寻路。
这么做会更迅速，并且差点儿总是能找到最短的路径，但不是绝对的。当从倒数第二个节点到最后一个（目标节点）之间的移动耗费悬殊非常大时－比如刚好有一条河穿越两个节点中间，这时候旧的做法和新的做法就会有显著不同。)
题外话
离题一下，见谅。值得一提的是。当你在网上或者相关论坛看到关于A*的不同的探讨，你有时会看到一些被当作A*算法的代码而实际上他们不是。要使用A*。你必须包括上面讨论的全部元素－－特定的开启和关闭列表。用F,G和H作路径评价。
有非常多其它的寻路算法，但他们并非A*，A*被觉得是他们其中最好的。Bryan Stout在这篇文章后面的參考文档中论述了一部分。包括他们的一些长处和缺点。有时候特定的场合其它算法会更好，但你必须非常明白你在作什么。好了，够多的了。回到文章。
实现的注解
如今你已经明确了基本原理，写你的程序的时候还得考虑一些额外的东西。以下这些材料中的一些引用了我用C++和Blitz Basic写的程序，但对其它语言写的代码相同有效。
1.其它单位(避免碰撞)：假设你恰好看了我的样例代码。你会发现它全然忽略了其它单位。我的寻路者其实能够相互穿越。取决于详细的游戏。这或许能够，或许不行。
假设你打算考虑其它单位，希望他们能互相绕过，我建议你仅仅考虑精巧或那些在计算路径时临近当前单位的单位，把它们当前的位置标志为可通过的。对于临近的运动着的单位，你能够通过惩处它们各自路径上的节点。来鼓舞这些寻路者找到不同的路径(很多其它的描写叙述见#2).
假设你选择了把其它正在移动而且远离当前寻路单位的那些单位考虑在内。你将须要实现一种方法及时预測在何时何地碰撞可能会发生。以便恰当的避免。否则你极有可能得到一条怪异的路径，单位突然转弯试图避免和一个已经不存在的单位发生碰撞。
当然，你也须要写一些碰撞检測的代码，由于不管计算的时候路径有多完美，它也会因时间而改变。
当碰撞发生时。一个单位必须寻找一条新路径，或者，假设还有一个单位正在移动而且不是正面碰撞，在继续沿当前路径移动之前，等待那个单位离开。
这些提示大概能够让你開始了。假设你想了解很多其它，这里有些你可能会认为实用的链接：
*自治角色的指导行为：Craig Reynold在指导能力上的工作和寻路有些不同。可是它能够和寻路整合从而形成更完整的移动和碰撞检測系统。
*电脑游戏中的长短距指导：指导和寻路方面著作的一个有趣的考察。这是一个pdf文件。
*协同单位移动：一个两部分系列文章的第一篇，内容是关于编队和基于分组的移动。作者是帝国时代(Age of Empires)的设计者Dave Pottinger.
*实现协同移动：Dave Pottinger文章系列的第二篇。
2. 不同的地形损耗：在这个教程和我附带的程序中，地形仅仅能是二者之－可通过的和不可通过的。可是你可能会须要一些可通过的地形，可是移动耗费更高－沼泽。小山。地牢的楼梯，等等。这些都是可通过可是比平坦的开阔地移动耗费更高的地形。
类似的，道路应该比自然地形移动耗费更低。
这个问题非常easy解决，仅仅要在计算不论什么地形的G值的时候添加地形损耗就能够了。
简单的给它添加一些额外的损耗就能够了。因为A*算法已经依照寻找最低耗费的路径来设计，所以非常easy处理这样的情况。在我提供的这个简单的样例里，地形仅仅有可通过和不可通过两种。A*会找到最短，最直接的路径。可是在地形耗费不同的场合，耗费最低的路径或许会包括非常长的移动距离－就像沿着路绕过沼泽而不是直接穿过它。
一种需额外考虑的情况是被专家称之为“influence mapping”的东西（暂译为影响映射图）。就像上面描写叙述的不同地形耗费一样，你能够创建一格额外的分数系统。并把它应用到寻路的AI中。如果你有一张有大批寻路者的地图，他们都要通过某个山区。每次电脑生成一条通过那个关口的路径，它就会变得更拥挤。
如果你愿意。你能够创建一个影响映射图对有大量*事件的格子施以不利影响。这会让计算机更倾向安全些的路径，而且帮助它避免总是只由于路径短(但可能更危急)而持续把队伍和寻路者送到某一特定路径。
还有一个可能得应用是惩处周围移动单位路径上得节点。
A*的一个底限是，当一群单位同一时候试图寻路到接近的地点。这一般会导致路径交叠。以为一个或者多个单位都试图走同样或者近似的路径到达目的地。对其它单位已经“认领”了的节点添加一些惩处会有助于你在一定程度上分离路径。减少碰撞的可能性。然而，假设有必要。不要把那些节点看成不可通过的。由于你仍然希望多个单位可以一字纵队通过拥挤的出口。
同一时候，你仅仅能惩处那些临近单位的路径，而不是全部路径，否则你就会得到奇怪的躲避行为比如单位躲避路径上其它已经不在那里的单位。还有，你应该仅仅惩处路径当前节点和随后的节点，而不应处理已经走过并甩在身后的节点。
3. 处理未知区域：你是否玩过这种PC游戏。电脑总是知道哪条路是正确的，即使它还没有侦察过地图？对于游戏，寻路太好会显得不真实。
幸运的是，这是一格能够轻易解决的问题。
答案就是为每一个不同的玩家和电脑（每一个玩家，而不是每一个单位－－那样的话会耗费大量的内存）创建一个独立的“knownWalkability”数组。每一个数组包括玩家已经探索过的区域，以及被当作可通过区域的其它区域。直到被证实。用这样的方法。单位会在路的死端徘徊而且导致错误的选择直到他们在周围找到路。一旦地图被探索了，寻路就像往常那样进行。
4. 平滑路径：虽然A*提供了最短，最低代价的路径。它无法自己主动提供看起来平滑的路径。看一下我们的样例终于形成的路径（在图）。
最初的一步是起始格的右下方。假设这一步是直接往下的话。路径不是会更平滑一些吗？有几种方法来解决问题。当计算路径的时候能够对改变方向的格子施加不利影响，对G值添加额外的数值。
也能够换种方法，你能够在路径计算完之后沿着它跑一遍，找那些用相邻格替换会让路径看起来更平滑的地方。想知道完整的结果。查看Toward
More Realistic Pathfinding。一篇(免费，可是须要注冊)Marco Pinter发表在Gamasutra.com的文章
5. 非方形搜索区域：在我们的样例里，我们使用简单的D方形图。你能够不使用这样的方式。
你能够使用不规则形状的区域。想想冒险棋的游戏。和游戏中那些国家。
你能够设计一个像那样的寻路关卡。为此，你可能须要建立一个国家相邻关系的表格，和从一个国家移动到还有一个的G值。
你也须要估算H值的方法。其它的事情就和样例中全然一样了。
当你须要向开启列表中加入新元素的时候，不需使用相邻的格子。取而代之的是从表格中寻找相邻的国家。
类似的，你能够为一张确定的地形图创建路径点系统，路径点通常是路上，或者地牢通道的转折点。作为游戏设计者，你能够预设这些路径点。
两个路径点被觉得是相邻的假设他们之间的直线上没有障碍的话。在冒险棋的样例里，你能够保存这些相邻信息在某个表格里，当须要在开启列表中加入元素的时候使用它。然后你就能够记录关联的G值（可能使用两点间的直线距离），H值（能够使用到目标点的直线距离）。其它都按原先的做就能够了。Amit Patel 写了其它方法的摘要。
还有一个在非方形区域搜索RPG地图的样例。查看我的文章Two-Tiered
A* Pathfinding。
(译者注：译文： A*分层寻路)
6. 一些速度方面的提示：当你开发你自己的A*程序。或者改写我的。你会发现寻路占领了大量的CPU时间，尤其是在大地图上有大量对象在寻路的时候。
假设你阅读过网上的其它材料，你会明确，即使是开发了星际争霸或帝国时代的专家，这也无可奈何。
假设你认为寻路太过缓慢，这里有一些建议或许有效：
* 使用更小的地图或者更少的寻路者。
* 不要同一时候给多个对象寻路。取而代之的是把他们增加一个队列，把寻路过程分散在几个游戏周期中。假设你的游戏以周期每秒的速度执行。没人能察觉。
可是当大量寻路者计算自己路径的时候,他们会发觉游戏速度突然变慢。
* 尽量使用更大的地图网格。这减少了寻路中搜索的总网格数。假设你有志气，你能够设计两个或者很多其它寻路系统以便使用在不同场合，取决于路径的长度。
这也正是专业人士的做法，用大的区域计算长的路径。然后在接近目标的时候切换到使用小格子/区域的精细寻路。假设你对这个观点感兴趣。查阅我的文章Two-Tiered A* Pathfinding。
(译者注：译文:A*分层寻路)
* 使用路径点系统计算长路径，或者预先计算好路径并增加到游戏中。
* 预处理你的地图，表明地图中哪些区域是不可到达的。我把这些区域称作“孤岛”。其实。他们能够是岛屿或其它被墙壁包围等无法到达的随意区域。A*的下限是，当你告诉它要寻找通往那些区域的路径时，它会搜索整个地图，直到全部可到达的方格/节点都被通过开启列表和关闭列表的计算。这会浪费大量的CPU时间。能够通过预先确定这些区域（比方通过flood-fill或类似的方法)来避免这样的情况的发生,用某些种类的数组记录这些信息，在開始寻路前检查它。
* 在一个拥挤的类似迷宫的场合，把不能连通的节点看作死端。这些区域能够在地图编辑器中预先手动指定，或者假设你有雄心壮志，开发一个自己主动识别这些区域的算法。
给定死端的全部节点能够被赋予一个唯一的标志数字。然后你就能够在寻路过程中安全的忽略全部死端，仅仅有当起点或者终点恰好在死端的某个节点的时候才须要考虑它们。
7. 维护开启列表：这是A*寻路算法最重要的组成部分。每次你訪问开启列表，你都须要寻找F值最低的方格。
有几种不同的方法实现这一点。你能够把路径元素任意保存，当须要寻找F值最低的元素的时候，遍历开启列表。这非常easy。可是太慢了。尤其是对长路径来说。这能够通过维护一格排好序的列表来改善。每次寻找F值最低的方格仅仅须要选取列表的首元素。当我自己实现的时候，这样的方法是我的首选。
在小地图。这样的方法工作的非常好。但它并非最快的解决方式。
更苛求速度的A*程序猿使用叫做二叉堆的方法，这也是我在代码中使用的方法。凭我的经验，这样的方法在大多数场合会快～倍，而且在长路经上速度呈几何级数提升(10倍以上速度)。
假设你想了解很多其它关于二叉堆的内容，查阅我的文章，Using Binary Heaps in A* Pathfinding。(译者注：译文：在A*寻路中使用二叉堆)
还有一个可能的瓶颈是你在多次寻路之间清除和保存你的数据结构的方法。
我个人更倾向把全部东西都存储在数组里面。尽管节点能够以面向对象的风格被动态的产生，记录和保存。我发现创建和删除对象所添加的大量时间，以及多余的管理层次减慢的整个过程的速度。可是，假设你使用数组，你须要在调用之间清理数据。这中情形你想做的最后一件事就是在寻路调用之后花点时间把一切归零。尤其是你的地图非常大的时候。
我通过使用一个叫做whichList(x,y)的二维数组避免这样的开销，数组的每一个元素表明了节点在开启列表还是在关闭列表中。
尝试寻路之后，我没有清零这个数组。
取而代之的是，我在新的寻路中重置onClosedList和onOpenList的数值。每次寻路两个都+5或者类似其它数值。这样的方法，算法能够安全的跳过前面寻路留下的脏数据。我还在数组中储存了诸如F,G和H的值。
这样一来。我仅仅需简单的重写不论什么已经存在的值而无需被清除数组的操作干扰。
将数据存储在多维数组中须要很多其它内存，所以这里须要权衡利弊。最后，你应该使用你最得心应手的方法。
8. Dijkstra的算法：虽然A*被觉得是通常最好的寻路算法(看前面的“题外话”),还是有一种另外的算法有它的可取之处-Dijkstra算法。Dijkstra算法和A*本质是同样的。仅仅有一点不同。就是Dijkstra算法没有启示式(H值总是)。因为没有启示式。它在各个方向上平均搜索。正如你所预料，因为Dijkstra算法在找到目标前通常会探索更大的区域，所以通常会比A*更慢一些。
那么为什么要使用这样的算法呢？由于有时候我们并不知道目标的位置。比方说你有一个资源採集单位，须要获取某种类型的资源若干。
它可能知道几个资源区域，可是它想去近期的那个。
这样的情况，Dijkstra算法就比A*更适合，由于我们不知道哪个更近。用A*，我们唯一的选择是依次对每一个目标许路并计算距离，然后选择近期的路径。我们寻找的目标可能会有不计其数的位置，我们仅仅想找当中近期的。而我们并不知道它在哪里，或者不知道哪个是近期的。
看完上面的介绍，再来看一个比較经典的题目:knight moves。
貌似也叫汉密尔顿路径。详细的我也不记得了。对这个问题我用A*算法来求解，正所谓光说不练是没实用的
id=2243" style="color:rgb(102,102,102); text-decoration:none">http://acm.pku.edu.cn/JudgeOnline/problem?id=2243
problem statement
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly
once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input Specification
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column
and a digit (1-8) representing the row on the chessboard.
Output Specification
For each test case, print one line saying "To get from xx to yy takes n knight moves.".
Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
题目的意思大概是说：在国际象棋的棋盘上，一匹马共同拥有8个可能的跳跃方向。求从起点到目标点之间的最少跳跃次数。
A* code:
2 #include <queue>
3 using namespace std;
4
5 struct knight{
6 int x,y,step;
7 int g,h,f;
8 bool operator < (const knight & k) const{ //重载比較运算符
9 return f > k.f;
}
}k;
bool visited[8][8]; //已訪问标记(关闭列表)
int x1,y1,x2,y2,ans; //起点(x1,y1),终点(x2,y2),最少移动次数ans
int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8个移动方向
priority_queue<knight> que; //最小优先级队列(开启列表)
bool in(const knight & a){ //推断knight是否在棋盘内
if(a.x<0 || a.y<0 || a.x>=8 || a.y>=8)
return false;
return true;
}
int Heuristic(const knight &a){ //manhattan估价函数
return (abs(a.x-x2)+abs(a.y-y2))*10;
}
void Astar(){ //A*算法
knight t,s;
while(!que.empty()){
t=que.top(),que.pop(),visited[t.x][t.y]=true;
if(t.x==x2 && t.y==y2){
ans=t.step;
break;
}
for(int i=0;i<8;i++){
s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1];
if(in(s) && !visited[s.x][s.y]){
s.g = t.g + 23; //23表示根号5乘以10再取其ceil
s.h = Heuristic(s);
s.f = s.g + s.h;
s.step = t.step + 1;
que.push(s);
}
}
}
}
int main(){
char line[5];
while(gets(line)){
x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1';
memset(visited,false,sizeof(visited));
k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h;
while(!que.empty()) que.pop();
que.push(k);
Astar();
printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans);
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。