蚁群算法应用.docx

《蚁群算法应用.docx》由会员分享，可在线阅读，更多相关《蚁群算法应用.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、很久以前就知道了 A*算法，但是从未仔细读过相关的文章，也没有看过代码，只是脑 子里有个模糊的概念。这次打算从头开头，争论一下这个被人推崇备至的简洁方法，作为学习 人工智能的开头。这篇文章特别知名，国内应当有不少人翻译过它，我没有查找，觉得翻译本 身也是对自身英文水平的熬炼。经过努力，最终完成了文档，也明白的A*算法的原理。毫无 疑问，作者用形象的描述，简洁诙谐的语言由浅入深的叙述了这一奇妙的算法，信任每个读过 的人都会对此有所熟悉（假如没有，那就是偶的翻译太差了一b）。以下是翻译的正文。（由于本人使用ultraedit编辑，所以没有对原文中的各种链接加以处理（除了图表），也是 为了避开未经许

2、可链接的嫌疑，有爱好的读者可以参考原文。会者不难，A* （念作A星）算法对初学者来说的确有些难度。这篇文章并不试图对这个话题作权威的陈述。取而代之的是，它只是描述算法的原理，使你可以在进一步的阅读中 理解其他相关的资料。最终，这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿，我在文章的末尾包含了一个指向例子程序的链接。压缩包包括C+和 Blitz Basic两个语言的版本，假如你只是想看看它的运行效果，里面还包含了可执行文 件。我们正在提高自己。让我们从头开头序：搜寻区域假设有人想从A点移动到一墙之隔的B点，如下图，绿色的是起点A,红色是终点B,蓝色方块是中间的墙。图1 你

3、首先留意到，搜寻区域被我们划分成了方形网格。像这样，简化搜寻区域，是寻路的第一 步。这一方法把搜寻区域简化成了一个二维数组。数组的每一个元素是网格的一个方块，方块 被标记为可通过的和不行通过的。路径被描述为从A到B我们经过的方块的集合。一旦路径 被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。这些中点被称为节点。当你阅读其他的寻路资料时，你将常常会看到人们争论节点。为什么不把他们描述 为方格呢？由于有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形，六角 形，或者其他任意外形。节点能够被放置在外形的任意位置一可以在中心，或者沿着边界，或 其他什么地方。我们使用这种系统，

4、无论如何，由于它是最简洁的。开头搜寻正如我们处理上图网格的方法，一旦搜寻区域被转化为简洁处理的节点，下一步就是去引导一次找到最短 路径的搜寻。在A*寻路算法中，我们通过从点A开头，检查相邻方格的方式，向外扩展直到 找到目标。我们做如下操作开头搜寻：从点A开头，并且把它作为待处理点存入一个开启列表。开启列表就像一张购物清 单。尽管现在列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的方格， 也可能不会。基本上，这是一个待检查方格的列表。查找起点四周全部可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方 格。也把他们加入开后列表。为全部这些方格保存点A作为父方格。当我们想描

5、述路径的 时候，父方格的资料是特别重要的。后面会解释它的具体用途。从开后列表中删除点A,把它加入到一个、关闭列表，列表中保存全部不需要再次检查 的方格。在这一点，你应当形成如图的结构。在图中，暗绿色方格是你起始方格的中心。它 被用浅蓝色描边，以表示它被加入到关闭列表中了。全部的相邻格现在都在开启列表中，它们 被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格，也就是开头的方格。图2 接着，我们选择开启列表中的接近方格，大致重复前面的过程，如下。但是，哪个方格是我们 要选择的呢？是那个F值最低的。路径评分选择路径中经过哪个方格的关键是下面这个等 式：F = G + H 这里：G =从起点A

6、,沿着产生的路径，移动到网格上指定方格的移动耗费。H =从网格上那个方格移动到终点B的预估移动耗费。这常常被称为后发式的，可能 会让你有点迷惑。这样叫的缘由是由于它只是个猜想。我们没方法事先知道路径的长度，由于 路上可能存在各种障碍（墙，水，等等）。虽然本文只供应了一种计算H的方法，但是你可以 在网上找到许多其他的方法。我们的路径是通过反复遍历开后列表并且选择具有最低F值的方格来生成的。文 章将对这个过程做更具体的描述。首先，我们更深化的看看如何计算这个方程。正如上面所说，G表示沿路径从起点到当前点的移动耗费。在这个例子里，我们令水平或者垂直移动的 耗费为10,对角线方向耗费为14。我们取这些

7、值是由于沿对角线的距离是沿水平或垂直移动 耗费的的根号2 （别怕），或者约1.414倍。为了简化，我们用10和14近似。比例基本正 确，同时我们避开了求根运算和小数。这不是只由于我们怕麻烦或者不喜爰数学。使用这样的 整数对计算机来说也更快捷。你不就就会发觉，假如你不使用这些简化方法，寻路会变得很 慢。既然我们在计算沿特定路径通往某个方格的G值，求值的方法就是取它父节点的G值，然后依照它相对父节点是对角线方向或者直角方向（非对角线），分别增加14和10。例 子中这个方法的需求会变得更多，由于我们从起点方格以外猎取了不止一个方格。H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算

8、从当前格到目的格之间 水平和垂直的方格的数量总和，忽视对角线方向。然后把结果乘以10。这被成为曼哈顿方法 是由于它看起来像计算城市中从一个地方到此外一个地方的街区数，在那里你不能沿对角线方 向穿过街区。很重要的一点，我们忽视了一切障碍物。这是对剩余距离的一个估算，而非实际 值，这也是这一方法被称为后发式的缘由。想知道更多？你可以在这里找到方程和额外的注 解。 F的值是G和H的和。第一步搜寻的结果可以在下面的图表中看到。F, G和H的评 分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的，F被打印在左上角，G在左下 角，H则在右下角。图3现在我们来看看这些方格。写字母的方格里，G = 10o

9、这是由于它只在水平方向偏离起始格一个格距。紧邻起始格的上方，下方和左边的方格的G值都 等于10。对角线方向的G值是14。H值通过求解到红色目标格的曼哈顿距离得到，其中只在水平和垂直方向移动，并且忽视中间的墙。用这种方法，起点右侧紧邻的方格离红色方格 有3格距离，H值就是30o这块方格上方的方格有4格距离（记住，只能在水平和垂直方向 移动），H值是40。你大致应当知道如何计算其他方格的H值了。每个格子的F值，还是简洁的由G和H相加得到连续搜寻为了连续搜寻，我们简洁的从开后列表中选择F值最低的方格。然后，对选中的方格做如下处理：4.把它从开后列表中删除，然后添加到关闭 列表中。5.检查全部相邻格子

10、。跳过那些已经在关闭列表中的或者不行通过的（有墙，水 的地形，或者其他无法通过的地形），把他们添加进开后列表，假如他们还不在里面的话。把选中的方格作为新的方格的父节点。6.假如某个相邻格已经在开后列表里了，检 查现在的这条路径是否更好。换句话说，检查假如我们用新的路径到达它的话，G值是否会更 低一些。假如不是，那就什么都不做。另一方面，假如新的G值更低，那就把相邻方格的父 节点改为目前选中的方格（在上面的图表中，把箭头的方向改为指向这个方格）。最终，重新 计算F和G的值。假如这看起来不够清楚，你可以看下面的图示。好了，让我们看看它是怎么运作的。我们最初的9格方格中，在起点被切换到关闭列表中后，

11、还剩8格留在开后 列表中。这里面，F值最低的那个是起始格右侧紧邻的格子，它的F值是40。因此我们选择 这一格作为下一个要处理的方格。在紧随的图中，它被用蓝色突出显示。图4 首先，我 们把它从开启列表中取出，放入关闭列表（这就是他被蓝色突出显示的缘由）。然后我们检查 相邻的格子。哦，右侧的格子是墙，所以我们略过。左侧的格子是起始格。它在关闭列表里， 所以我们也跳过它。其他4格已经在开后列表里了，于是我们检查G值来判定，假如通过这一格到达那里，路径是否更好。我们来看选中格子下面的方格。它的G值是14。假如我 们从当前格移动到那里，G值就会等于20（到达当前格的G值是10,移动到上面的格子将使 得G

12、值增加10）。由于G值20大于14,所以这不是更好的路径。假如你看图，就能理解。 与其通过先水平移动一格，再垂直移动一格，还不如直接沿对角线方向移动一格来得简洁。当我们对已经存在于开启列表中的4个接近格重复这一过程的时候，我们发觉没有一条路径 可以通过使用当前格子得到改善，所以我们不做任何转变。既然我们已经检查过了全部邻近 格，那么就可以移动到下一格了。于是我们检索开后列表，现在里面只有7格了，我们仍旧选择其中F值最低的。好玩的是，这次，有两个格子的数值都是54。我们如何选择？这 并不麻烦。从速度上考虑，选择最终添加进列表的格子会更快捷。这种导致了寻路过程中，在 靠近目标的时候，优先使用新找到

13、的格子的偏好。但这无关紧要。（对相同数值的不同对待， 导致不同版本的A*算法找到等长的不同路径。）那我们就选择起始格右下方的格子，如图。 图5 这次，当我们检查相邻格的时候，发觉右侧是墙，于是略过。上面一格也被略过。 我们也略过了墙下面的格子。为什么呢？由于你不能在不穿越墙角的状况下直接到达那个格 子。你的确需要先往下走然后到达那一格，按部就班的走过那个拐角。（注解：穿越拐角的规 章是可选的。它取决于你的节点是如何放置的。）这样一来，就剩下了其他5格。当前格下面的此外两个格子目前不在开后列表中，于是我们添加他们，并且把当前格指定为他们的父 节点。其余3格，两个已经在关闭列表中（起始格，和当前格

14、上方的格子，在表格中蓝色高 亮显示），于是我们略过它们。最终一格，在当前格的左侧，将被检查通过这条路径，G值是否 更低。不必担忧，我们已经预备好检查开后列表中的下一格了。我们重复这个过程，知道目标 格被添加进开后列表，就如在下面的图中所看到的。图6 留意，起始格下方格子的父节点已经和前面不同的。之前它的G值是28,并且指向右上方的格子。现在它的G值是20, 指向它上方的格子。这在寻路过程中的某处发生，当应用新路径时，G值经过检查变得低了一 于是父节点被重新指定，G和F值被重新计算。尽管这一变化在这个例子中并不重要，在许多 场合，这种变化会导致寻路结果的巨大变化。那么，我们怎么确定这条路径呢？很

15、简洁，从红色的目标格开头，按箭头的方向朝父节点移动。这最终会引导你回到起始格，这就是你的 路径！看起来应当像图中那样。从起始格A移动到目标格B只是简洁的从每个格子（节点） 的中点沿路径移动到下一个，直到你到达目标点。就这么简洁。图7A*方法总结好，现在 你已经看完了整个说明，让我们把每一步的操作写在一起：把起始格添加到开后列表。重复如下的工作：a）查找开后列表中F值最低的格子。我们称它为当前格。b）把它 切换到关闭列表。c）对相邻的8格中的每一个？假如它不行通过或者已经在笑闭列表中，略过它。反之如下。假如它不在开后列表中，把它添加进去。把当前格作为这一格的父节点。纪录这一格的 F,G,和H值。

16、假如它已经在开后列表中，用G值为参考检查新的路径是否更好。更低的G值意味着 更好的路径。假如是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F 值。假如你保持你的开后列表按F值排序，转变之后你可能需要重新对开后列表排序。d）停止，当你把目标格添加进了开后列表，这时候路径被找到，或者 没有找到目标格，开后列表已经空了。这时候，路径不存在。保存路径。从目标格开头，沿着每一格的父节点移动直到回到起始格。这就是你的路 径。题外话离题一下，见谅，值得一提的是，当你在网上或者相关论坛看到父于A夫的不同的研讨，你有时会看到一些被当作A*算法的代码而实际上他们不是。要使用A*,你必需 包含上面争

17、论的全部元素一一特定的开启和关闭列表，用F,G和H作路径评价。有许多其他 的寻路算法，但他们并不是A夫，A*被认为是他们当中最好的。Bryan Stout在这篇文章后 面的参考文档中论述了一部分，包括他们的一些优点和缺点。有时候特定的场合其他算法会更 好，但你必需很明确你在作什么。好了，够多的了。回到文章。实现的注解现在你已经明白了基本原理，写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用了我 用C+和Blitz Basic写的程序，但对其他语言写的代码同样有效。维护开启列表：这是A大寻路算法最重要的组成部分。每次你访问开后列表，你都需要 查找F值最低的方格。有几种不同的方法实

18、现这一点。你可以把路径元素随便保存，当需要 查找F值最低的元素的时候，遍历开后列表。这很简洁，但是太慢了，尤其是对长路径来 说。这可以通过维护一格排好序的列表来改善，每次查找F值最低的方格只需要选取列表的 首元素。当我自己实现的时候，这种方法是我的首选。在小地图。这种方法工作的很好，但它并不是最快的解决方案。更苛求速度的A夫程序员使用叫做binary heap的方法，这 也是我在代码中使用的方法。凭我的阅历，这种方法在大多数场合会快23倍，并且在长路 经上速度呈几何级数提升（10倍以上速度）。假如你想了解更多关于binary heap的内容， 查阅我的文章：Using Binary Heaps

19、 in A* Pathfindingo其他单位：假如你恰好看了我的例子代码，你会发觉它完全忽视了其他单位。我的寻路 者事实上可以相互穿越。取决于具体的嬉戏，这或许可以，或许不行。假如你准备考虑其他单 位，盼望他们能相互绕过，我建议在寻路算法中忽视其他单位，写一些新的代码作碰撞检测。 当碰撞发生，你可以生成一条新路径或者使用一些标准的移动规章（比如总是向右，等等）直 到路上没有了障碍，然后再生成新路径。为什么在最初的路径计算中不考虑其他单位呢？那是 由于其他单位会移动，当你到达他们原来的位置的时候，他们可能已经离开了。这有可能会导 致惊奇的结果，一个单位突然转向，躲避一个已经不在那里的单位，并且

20、会撞到计算完路径 后，冲进它的路径中的单位。然而，在寻路算法中忽视其他对象，意味着你必需编写单独的碰撞检测代码。这因嬉戏而异，所以我把这个打算权留给你。参考文献列表中，Bryan Stout的文章值得争论，里面有一些可能的解决方案（像鲁棒追踪，等等）。一些速度方面的提示：当你开发你自己的A*程序，或者改写我的，你会发觉寻路占据 了大量的CPU时间，尤其是在大地图上有大量对象在寻路的时候。假如你阅读过网上的其他 材料，你会明白，即使是开发了星际争霸或帝国时代的专家，这也无可奈何。假如你觉得寻路 太过缓慢，这里有一些建议或许有效：使用更小的地图或者更少的寻路者。不要同时给多个对象寻路。取而代之的是

21、把他们加入一个队列，把寻路过程分散在几个 嬉戏周期中。假如你的嬉戏以40周期每秒的速度运行，没人能察觉。但是他们会发觉嬉戏速 度突然变慢，当大量寻路者计算自己路径的时候。尽量使用更大的地图网格。这降低了寻路中搜寻的总网格数。假如你有志气，你可以设 计两个或者更多寻路系统以便使用在不同场合，取决于路径的长度。这也正是专业人士的做 法，用大的区域计算长的路径，然后在接近目标的时候切换到使用小格子/区域的精细寻路。 假如你对这个观点感爰好，查阅我的文章：Two-Tiered A* Pathfinding。使用路径点系统计算长路径，或者预先计算好路径并加入到嬉戏中。预处理你的地图，表明地图中哪些区域是

22、不行到达的。我把这些区域称作孤岛。事 实上，他们可以是岛屿或其他被墙壁包围等无法到达的任意区域。A*的下限是，当你告知它 要查找通往那些区域的路径时，它会搜寻整个地图，直到全部可到达的方格/节点都被通过开 后列表和关闭列表的计算。这会铺张大量的CPU时间。可以通过预先确定这些区域（比如通 过flood-fill或类似的方法）来避开这种状况的发生，用某些种类的数组纪录这些信息，在 开头寻路前检查它。在我Blitz版本的代码中，我建立了一个地图预处理器来作这个工作。 它也标明白寻路算法可以忽视的死端，这进一步提高了寻路速度。不同的地形损耗：在这个教程和我附带的程序中，地形只有两种一可通过的和不行通

23、过 的。但是你可能会需要一些可通过的地形，但是移动耗费更高一沼泽，小山，地牢的楼梯，等 等。这些都是可通过但是比平坦的开阔地移动耗费更高的地形。类似的，道路应当比自然地形 移动耗费更低。这个问题很简洁解决，只要在计算任何地形的G值的时候增加地形损耗就可以了。简洁的给它增加一些额外的损耗就可以了。由于A*算法已经根据查找最低耗费的 路径来设计，所以很简洁处理这种状况。在我供应的这个简洁的例子里，地形只有可通过和不 行通过两种，A*会找到最短，最直接的路径。但是在地形耗费不同的场合，耗费最低的路径 或许会包含很长的移动距离一就像沿着路绕过沼泽而不是直接穿过它。一种需额外考虑的状况是被专家称之为in

24、f luencmapping的东西（暂译为影响映射图）。就像上面描述 的不同地形耗费一样，你可以创建一格额外的分数系统，并把它应用到寻路的A工中。假设你 有一张有大批寻路者的地图，他们都要通过某个山区。每次电脑生成一条通过那个关口的路 径，它就会变得更拥挤。假如你情愿，你可以创建一个影响映射图对有大量屠杀大事的格子施 以不利影响。这会让计算机更倾向平安些的路径，并且关心它避开总是仅仅由于路径短（但可 能更危急）而持续把队伍和寻路者送到某一特定路径。处理未知区域：你是否玩过这样的PC嬉戏，电脑总是知道哪条路是正确的，即使它还 没有侦察过地图？对于嬉戏，寻路太好会显得不真实。幸运的是，这是一格可以

25、轻易解决的问 题。 答案就是为每个不同的玩家和电脑（每个玩家，而不是每个单位一一那样的话会耗费 大量的内存）创建一个独立的“knownWalkability数组，每个数组包含玩家已经探究过的 区域，以及被当作可通过区域的其他区域，直到被证明。用这种方法，单位会在路的死端徘徊 并且导致错误的选择直到他们在四周找到路。一旦地图被探究了，寻路就像平常那样进行。平滑路径：尽管A*供应了最短，最低代价的路径，它无法自动供应看起来平滑的路 径。看一下我们的例子最终形成的路径（在图7）o最初的一步是起始格的右下方，假如这一 步是直接往下的话，路径不是会更平滑一些吗？有几种方法来解决这个问题。当计算路径的时候

26、可以对转变方向的格子施加不利影响，对G值增加额外的数值。也可以换种方法，你 可以在路径计算完之后沿着它跑一遍，找那些用相邻格替换会让路径看起来更平滑的地方。想 知道完整的结果，查看Marco Pinter发表在Gamasutra. com的一篇文章：Toward More Realistic Pathfinding （免费，但是需要注册）。非方形搜寻区域：在我们的例子里，我们使用简洁的2D方形图。你可以不使用这种方 式。你可以使用不规章外形的区域。想想冒险棋的嬉戏，和嬉戏中那些我国。你可以设计一个 像那样的寻路关卡。为此，你可能需要建立一个我国相邻关系的表格，和从一个我国移动到另 一个的G值。

27、你也需要估算H值的方法。其他的事情就和例子中完全一样了。当你需要向开 后列表中添加新元素的时候，不需使用相邻的格子，取而代之的是从表格中查找相邻的我国。 类似的，你可以为一张确定的地形图创建路径点系统，路径点一般是路上，或者地牢通道的转 折点。作为嬉戏设计者，你可以预设这些路径点。两个路径点被认为是相邻的假如他们之间的 直线上没有障碍的话。在冒险棋的例子里，你可以保存这些相邻信息在某个表格里，当需要在开后列表中添加元素的时候使用它。然后你就可以纪录关联的G值（可能使用两点间的直线 距离），H值（可以使用到目标点的直线距离），其他都按原先的做就可以了。另一个在非方形区域搜寻RPG地图的例子，查看

28、我的文章：Two-Tiered A大 Pathfindingo进一步的阅读好，现在你对一些进一步的观点有了初步熟悉。这时，我建议你争论我的源代码。包里面包含两个版本，一个是用C+写的，另一个用Blitz BasiCo顺便说一句，两个版本都注释详尽，简洁阅读，这里是链接。例子代码：A* Pathfinder （2D） Version 1.71假如你既不用C+也不用Blitz Basic,在C+版本里有两个小的可执行文件。Blitz Basic可以在从Blitz Basic网站免费下载的litz Basic 3D （不是Blitz Plus）演不版上运行。Ben 0 - Neill供应一个联机演示

29、可以在这里找到。你也该看看以下的网页。读了这篇教程后，他 们应当变得简洁理解多了。Amit的A*页面：这是由Amit Patel制作，被广泛引用的页面，假如你没有事先 读这篇文章，可能会有点难以理解。值得一看。尤其要看Amit关于这个问题的自己的看法。Smart Moves： 智能寻路：Bryan Stout 发表在 G 的这篇文章需要 注册才能阅读。注册是免费的而且比起这篇文章和网站的其他资源，是特别物有所值的。Bryan用Delphi写的程序关心我学习A夫,也是我的A夫代码的灵感之源。它还描述了 A*的 几种变化。地形分析：这是一格高阶，但是好玩的话题，Dave Pottinge撰写，En

30、semble Studios的专家。这家伙参加了帝国时代和君王时代的开发。别希望看懂这里全部的东西， 但是这是篇好玩的文章或许会让你产生自己的想法。它包含一些对mip-mapping, influence mapping以及其他一些高级A工/寻路观点。对 flood filling”的争论使我 有了我自己的死端和孤岛的代码的灵感，这些包含在我Blitz版本的代码中。其它一些值得一看的网站：aiGuru: PathfindingGame AI Resource: PathfindingGameD: Pathfinding 其它参考文章： Artificial Intelligence:Pathf

31、inding and Searching Featured Articles:Featured Articles 好了，这就是全部。假如你刚好写一个运用这些观点的程序，我想见识见识。你可以这 样联系我：现在，好运！CB发觉了一种惊奇的数列，命名为CB数列。这种惊奇的数列具有如下的性质： 1）全部数都是正整数；2）数列中后一个数不小于前一个数的两倍；比如，n=661 6263 61 2 61 3 6共有6种方案。 CB想用CB数列考考2B铅笔。他给出一个正整数 n,让2B铅笔计算，以n结尾（即最终一个元素等于n）的这种数列有多少个？当然，CB不想让2B铅笔轻松地解决这个问题，所以他把n的范围定得很大，n可以是两千以内的 任何正整数。2B铅笔该如何解决这个问题呢？