A星算法入门.doc

HYPERLINK /mythit/极限定律 My Algorithm Space HYPERLINK /mythit/archive/2009/04/19/80492.htmlA*算法入 门 在看下面这篇文章之前，先介绍几个理论知识，有助于理解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）。 现在是年月日的版本，应原作者要求，对文中的某些算法细节做了修改。 原文链接：/reference/articles/article2003.asp 原作者文章链接：/games/aStarTutorial.htm 以下是翻译的正文 会者不难，A*(念作A星)算 法对初学者来说的确有些难度。这篇文章并不试图对这个话题作权威的陈述。取而代之的是，它只是描述算法的原理，使你可以在进一步的阅读中理解其他相关的资 料。最后，这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿，我在文章的末尾包含了一个指向例子程序的链接。压缩包包括C++和Blitz Basic两个语言的版本，如果你只是想看看它的运行效果，里面还包含了可执行文件。我们正在提高自己。让我们从头开始。。。 序：有哪些信誉好的足球投注网站区域 假设有人想从A点移动到一墙之隔的B点，如下图，绿 色的是起点A，红色是终点B，蓝色方块是中间的墙。 [图-1] 你首先注意到，有哪些信誉好的足球投注网站区域被我们划分成了方形网格。像这样，简化有哪些信誉好的足球投注网站区域，是寻路的第一步。这一方法把有哪些信誉好的足球投注网站区 域简化成了一个二维数组。数组的每一个元素是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描述为从A到B我 们经过的方块的集合。一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。 这些中点被称为“节点”。 当你阅读其他的寻路资料时，你将经常会看到人们讨论节点。为什么不把他们描述为方格呢？因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩 形，六角形，或者其他任意形状。节点能够被放置在形状的任意位置－可以在中心，或者沿着边界，或其他什么地方。我们使用这种系统，无论如何，因为它是最简 单的。 开始有哪些信誉好的足球投注网站 正如我们处理上图网格的方法，一旦有哪些信誉好的足球投注网站区域被转化为容易处理的节点，下一步就是去引导一次找到最短路径的搜 索。在A*寻路算法中，我们通过从点A开始，检查相邻方格的方式，向外扩展直到找到目标。 我们做如下操作开始有哪些信誉好的足球投注网站： 1，从点A开始， 并且把它作为待处理点存入一个“开启列表”。 开启列表就像一张购物清单。尽管现在列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的方格，也可能不会。基本上，这是一个待检查方格的 列表。 2，寻找起点周围所有可到达或者可通过的方 格，跳过有墙，水，或其他无法通过地形的方格。也把他们