无锡定制网站制作公司,网站开发 python 工具,德语网站域名,合肥网站优化公司From: http://www.cppblog.com/mythit/archive/2009/04/19/80492.aspx 在看下面这篇文章之前#xff0c;先介绍几个理论知识#xff0c;有助于理解A*算法。 启发式搜索#xff1a;启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估#xff0c;得到最好的位置先介绍几个理论知识有助于理解A*算法。 启发式搜索启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估得到最好的位置再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径提到了效率。在启发式搜索中对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
估价函数从当前节点移动到目标节点的预估费用这个估计就是启发式的。在寻路问题和迷宫问题中我们通常用曼哈顿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我们经过的方块的集合。一旦路径被找到我们的人就从一个方格的中心走向另一个直到到达目的地。
这些中点被称为“节点”。当你阅读其他的寻路资料时你将经常会看到人们讨论节点。为什么不把他们描述为方格呢因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形六角形或者其他任意形状。节点能够被放置在形状的任意位置可以在中心或者沿着边界或其他什么地方。我们使用这种系统无论如何因为它是最简单的。
开始搜索
正如我们处理上图网格的方法一旦搜索区域被转化为容易处理的节点下一步就是去引导一次找到最短路径的搜索。在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值被重新计算。尽管这一变化在这个例子中并不重要在很多场合这种变化会导致寻路结果的巨大变化。
那么我们怎么确定这条路径呢很简单从红色的目标格开始按箭头的方向朝父节点移动。这最终会引导你回到起始格这就是你的路径看起来应该像图中那样。从起始格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. 不同的地形损耗在这个教程和我附带的程序中地形只能是二者之可通过的和不可通过的。但是你可能会需要一些可通过的地形但是移动耗费更高沼泽小山地牢的楼梯等等。这些都是可通过但是比平坦的开阔地移动耗费更高的地形。类似的道路应该比自然地形移动耗费更低。
这个问题很容易解决只要在计算任何地形的G值的时候增加地形损耗就可以了。简单的给它增加一些额外的损耗就可以了。由于A*算法已经按照寻找最低耗费的路径来设计所以很容易处理这种情况。在我提供的这个简单的例子里地形只有可通过和不可通过两种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值最低的元素的时候遍历开启列表。这很简单但是太慢了尤其是对长路径来说。这可以通过维护一格排好序的列表来改善每次寻找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*算法来求解正所谓光说不练是没有用的
http://acm.pku.edu.cn/JudgeOnline/problem?id2243 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: 1 #include iostream 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; 10 } 11 }k; 12 bool visited[8][8]; //已访问标记(关闭列表) 13 int x1,y1,x2,y2,ans; //起点(x1,y1),终点(x2,y2),最少移动次数ans 14 int dirs[8][2]{{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8个移动方向 15 priority_queueknight que; //最小优先级队列(开启列表) 16 17 bool in(const knight a){ //判断knight是否在棋盘内 18 if(a.x0 || a.y0 || a.x8 || a.y8) 19 return false; 20 return true; 21 } 22 int Heuristic(const knight a){ //manhattan估价函数 23 return (abs(a.x-x2)abs(a.y-y2))*10; 24 } 25 void Astar(){ //A*算法 26 knight t,s; 27 while(!que.empty()){ 28 tque.top(),que.pop(),visited[t.x][t.y]true; 29 if(t.xx2 t.yy2){ 30 anst.step; 31 break; 32 } 33 for(int i0;i8;i){ 34 s.xt.xdirs[i][0],s.yt.ydirs[i][1]; 35 if(in(s) !visited[s.x][s.y]){ 36 s.g t.g 23; //23表示根号5乘以10再取其ceil 37 s.h Heuristic(s); 38 s.f s.g s.h; 39 s.step t.step 1; 40 que.push(s); 41 } 42 } 43 } 44 } 45 int main(){ 46 char line[5]; 47 while(gets(line)){ 48 x1line[0]-a,y1line[1]-1,x2line[3]-a,y2line[4]-1; 49 memset(visited,false,sizeof(visited)); 50 k.xx1,k.yy1,k.gk.step0,k.hHeuristic(k),k.fk.gk.h; 51 while(!que.empty()) que.pop(); 52 que.push(k); 53 Astar(); 54 printf(To get from %c%c to %c%c takes %d knight moves.\n,line[0],line[1],line[3],line[4],ans); 55 } 56 return 0; 57 } 58
