A星寻路算法
此文档由网络搜集而来。会者不难，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表示沿路径从起点到当前点的移动耗费。在这个例子里，我们令水平或者垂直移动的耗费为10，对角线方向耗费为14。我们取这些值是因为沿对角线的距离是沿水平或垂直移动耗费的的根号2（别怕），或者约1.414倍。为了简化，我们用10和14近似。比例基本正确，同时我们避免了求根运算和小数。这不是只因为我们怕麻烦或者不喜欢数学。使用这样的整数对计算机来说也更快捷。你不就就会发现，如果你不使用这些简化方法，寻路会变得很慢。
既然我们在计算沿特定路径通往某个方格的G值，求值的方法就是取它父节点的G值，然后依照它相对父节点是对角线方向或者直角方向(非对角线)，分别增加14和10。例子中这个方法的需求会变得更多，因为我们从起点方格以外获取了不止一个方格。
H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。然后把结果乘以10。这被成为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的街区数，在那里你不能沿对角线方向穿过街区。很重要的一点，我们忽略了一切障碍物。这是对剩余距离的一个估算，而非实际值，这也是这一方法被称为启发式的原因。想知道更多？你可以在这里找到方程和额外的注解。
F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F,G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的，F被打印在左上角，G在左下角，H则在右下角。
[图3]
现在我们来看看这些方格。写字母的方格里，G = 10。这是因为它只在水平方向偏离起始格一个格距。紧邻起始格的上方，下方和左边的方格的G值都等于10。对角线方向的G值是14。
H值通过求解到红色目标格的曼哈顿距离得到，其中只在水平和垂直方向移动，并且忽略中间的墙。用这种方法，起点右侧紧邻的方格离红色方格有3格距离，H值就是30。这块方格上方的方格有4格距离(记住，只能在水平和垂直方向移动)，H值是40。你大致应该知道如何计算其他方格的H值了～。
每个格子的F值，还是简单的由G和H相加得到
继续搜索
为了继续搜索，我们简单的从开启列表中选择F值最低的方格。然后，对选中的方格做如下处理：
4，把它从开启列表中删除，然后添加到关闭列表中。
5，检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙，水的地形，或者其他无法通过的地形)，把他们添加进开启列表，如果他们还不在里面的话。把选中的方格作为新的方格的父节点。 6，如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。换句话说，检查如果我们用新的路径到达它的话，G值是否会更低一些。如果不是，那就什么都不做。
另一方面，如果新的G值更低，那就把相邻方格的父节点改为目前选中的方格（在上面的图表中，
把箭头的方向改为指向这个方格）。最后，重新计算F和G的值。如果这看起来不够清晰，你可以看下面的图示。
好了，让我们看看它是怎么运作的。我们最初的9格方格中，在起点被切换到关闭列表中后，还剩8格留在开启列表中。这里面，F值最低的那个是起始格右侧紧邻的格子，它的F值是40。因此我们选择这一格作为下一个要处理的方格。在紧随的图中，它被用蓝色突出显示。
[图4]
首先，我们把它从开启列表中取出，放入关闭列表(这就是他被蓝色突出显示的原因)。然后我们检查相邻的格子。哦，右侧的格子是墙，所以我们略过。左侧的格子是起始格。它在关闭列表里，所以我们也跳过它。
其他4格已经在开启列表里了，于是我们检查G值来判定，如果通过这一格到达那里，路径是否更好。我们来看选中格子下面的方格。它的G值是14。如果我们从当前格移动到那里，G值就会等于20(到达当前格的G值是10，移动到上面的格子将使得G值增加10)。因为G值20大于14，所以这不是更好的路径。如果你看图，就能理解。与其通过先水平移动一格，再垂直移动一格，还不如直接沿对角线方向移动一格来得简单。
当我们对已经存在于开启列表中的4个临近格重复这一过程的时候，我们发现没有一条路径可以通过使用当前格子得到改善，所以我们不做任何改变。既然我们已经检查过了所有邻近格，那么就可以移动到下一格了。
于是我们检索开启列表，现在里面只有7格了，我们仍然选择其中F值最低的。有趣的是，这次，有两个格子的数值都是54。我们如何选择？这并不麻烦。从速度上考虑，选择最后添加进列表的格子会更快捷。这种导致了寻路过程中，在靠近目标的时候，优先使用新找到的格子的偏好。但这无关紧要。（对相同数值的不同对待，导致不同版本的A*算法找到等长的不同路径。）
那我们就选择起始格右下方的格子，如图。
[图5]
这次，当我们检查相邻格的时候，发现右侧是墙，于是略过。上面一格也被略过。我们也略过了墙下面的格子。为什么呢？因为你不能在不穿越墙角的情况下直接到达那个格子。你的确需要先往下走然后到达那一格，按部就班的走过那个拐角。(注解：穿越拐角的规则是可选的。它取决于你的节点是如何放置的。) 这样一来，就剩下了其他5格。当前格下面的另外两个格子目前不在开启列表中，于是我们添加他们，并且把当前格指定为他们的父节点。其余3格，两个已经在关闭列表中（起始格，和当前格上方的格子，在表格中蓝色高亮显示),于是我们略过它们。最后一格，在当前格的左侧，将被检查通过这条路径，G值是否更低。不必担心，我们已经准备好检查开启列表中的下一格了。
我们重复这个过程，直到目标格被添加进关闭列表(注解)，就如在下面的图中所看到的。
[图6]
注意，起始格下方格子的父节点已经和前面不同的。之前它的G值是28，并且指向右上方的格子。现在它的G值是20，指向它上方的格子。这在寻路过程中的某处发生，当应用新路径时，G值经过检查变得低了－于是父节点被重新指定，G和F值被重新计算。尽管这一变化在这个例子中并不重要，在很多场合，这种变化会导致寻路结果的巨大变化。
那么，我们怎么确定这条路径呢？很简单，从红色的目标格开始，按箭头的方向朝父节点移动。这最终会引导你回到起始格，这就是你的路径！看起来应该像图中那样。从起始格A移动到目标格B只是简单的从每个格子（节点）的中点沿路径移动到下一个，直到你到达目标点。就这么简单。
[图7]
A*方法总结
好，现在你已经看完了整个说明，让我们把每一步的操作写在一起：
1，把起始格添加到开启列表。
2，重复如下的工作：
a) 寻找开启列表中F值最低的格子。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的8格中的每一个？
* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。
* 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
d) 停止，当你
* 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者
* 没有找到目标格，开启列表已经空了。这时候，路径不存在。
3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。
(注解:在这篇文章的较早版本中，建议的做法是当目标格（或节点）被加入到开启列表，而不是关闭列表的时候停止寻路。这么做会更迅速，而且几乎总是能找到最短的路径，但不是绝对的。当从倒数第二个节点到最后一个（目标节点）之间的移动耗费悬殊很大时－例如刚好有一条河穿越两个节点中间，这时候旧的做法和新的做法就会有显著不同。)
A 寻路算法模拟实现 C++ 可运行
////////////////////////////////////////////////////////////////////////// // // // // //写一个自己实现的A*搜索算法 ////////////////////////////////////////////////////////////////////////// #include"stdafx.h" #include
std::map
基于BP神经网络的扫地机器人寻路算法
龙源期刊网 https://www.sodocs.net/doc/a89659953.html, 基于BP神经网络的扫地机器人寻路算法 作者：杨忠刘华春 来源：《电脑知识与技术》2017年第10期 摘要：传统的寻路算法通常用在已知地形结构的基础上规划路线，而扫地机器人的工作环境通常是陌生的，传统寻路算法在此失效。该文结合BP神经网络的特性，提出一种基于BP 神经网络的扫地机器人寻路算法，目标是使扫地机器人能够在任何陌生的环境中正确地完成寻路任务，通过分析扫地机器人的清扫模式，建立观察模型和运动模型，利用MatLab实现对应的BP神经网络，并对传统BP网络激励函数进行了优化，最后经过训练和仿真验证了算法的有效性和实用性。 关键词：寻路算法；扫地机器A-；BP神经网络 中图分类号：TPl8 文献标识码：A 文章编号：1009-3044（2017）10-0156-03 随着科技的不断进步，智能家居理念逐步渗透了现代生活中，智能扫地机器人日益流行起来，很多厂家都开始生产智能扫地机器人。过去机器人通常只能完成一些简单的任务，但随着人工智能、传感器技术的发展，机器人的功能得到了很大的升级和改善，加上网络推广，智能扫地机器人已经真正地进入人们的日常生活。智能扫地机器人能在无人监督的情况下通过红外线传感器、超声波传感器、陀螺仪、电子罗盘、室内GPS等传感器设备扫描并学习房间局部户型结构，规划路径完成房间的清洁任务。通常由于所处位置的局限性和现代住房结构复杂等因素，难以获得完整准确的户型结构图，而要求用户事先将户型图输入机器人也不现实，因此清扫路径的规划是整个清扫活动的难点。目前通常采取线性算法进行路径规划，通过传统程序设计模式编程实现。这种方式导致扫地机器人智能程度不高，在遇到一些特殊情况时，导致整个清扫工作中断。 1.问题分析 扫地机器人按清扫路线形式可分为规划式和随机式两类。目前，扫地机器人大部分都采取随机式扫地机，即不规划路线，扫到哪算哪，碰到障碍物自己走开。规划式清扫模式：扫地机器人感知四周的环境，然后规划行走的路径，有效地遍历各个区域，完成各个区域的打扫。规划式清扫模式的行走路径方式有螺旋式行走模式，S形行走模式，五边形行走模式。其中，以螺旋行走模式的清扫效率最高，它最大程度的避免了重复路线。但单一的规划式清洁模式，始终不能完美解决障碍物问题，螺旋行走模式以程序的形式编写进扫地机器人控制中心计算机，它只能以固定不变的路径完成清扫任务，在途中若遇到形状复杂、面积较大的障碍物，如茶
最优路径算法
9.4.3 寻路算法 路径选择问题是游戏开发中经常遇到的问题，比如热门的Android游戏《crystallight》，游戏中的敌人需要寻找到一条路径前进，直到被杀死或者是到达终点；又如，棋类游戏中，需要为棋子选择最"理智"的行进路径，以达到最佳棋面；再如，9.3.5节中提到的复杂游戏AI，其核心就是为"飞机"寻找一条最理想的逃生路线。此外，在非规则实体的碰撞检测中，也需要选择较优的路径到达碰撞边缘。类似的路径选择问题经常出现，但是如何合理地实现寻路算法，是很多程序员需要解决的难题。 1. A*算法知多少 很多游戏开发者一提到寻路算法，就想到A*算法；一提到A*算法，就望而却步。下面将揭开A*算法的神秘面纱。 A*算法确实是最高效、最流行的寻路算法，是搜索算法最深层的延伸。A*算法由4个要素组成：A*=估价函数+并查集+堆+广搜。A*算法必须有强大的算法功底和长年累月的实战积累方能实现。另外，A*也并非总是最适合的算法，它仅仅是在不同运用领域表现出更强的通用性，仅仅是在数据统计范畴内性能期望值最高。 那么，A*是否适合移植到Android平台呢？我们需要进一步分析它的特点与专长。A*算法的精髓是以空间换取时间，它的运用前提是：解空间充分大，运算时间受到刚性限制，而存储空间(一般是内存)相对充足。如果将它移植到Android平台上，其一，手机系统的内存资源弥足珍贵，A*算法将完全失去用武之地；其二，手机游戏的寻路空间相对较小，解空间相对狭隘。因而，搜索算法的瓶颈不再是冗余的搜索尝试，而估价函数的开销以及冗长的代码将成为新的瓶颈。因此，A*算法并不是Android手机游戏的唯一选择，针对不同的路径选择需要，应该定制不同的搜索算法。 2. 量身定制寻路算法 设计寻路算法应该基于两个原则：开发者力所能及、算法力所能及。 算法功底不是很雄厚的开发者，不必追求华丽的A*算法，可根据实际需要写一个普通的宽搜或者广搜算法。毕竟手机游戏的解空间与PC游戏差了不止一个数量级，常规搜索的时间开销也不会庞大。游戏开发者需要认真做好的是优化。其实，开发寻路算法的大门一直都敞开着，只要开发者能够找准游戏的定位，选准突破的方向。例如，热门塔防游戏--《Robo Defense》，它的搜索空间很小，对常规的搜索算法做一些优化，即能实现即时寻路。 具备深厚算法功底的开发者可以根据不同的路径选择需求，选择最恰当的寻路算法。对于解空间较小、实时性较高的游戏，A*算法将是最恰当的选择，设计高效的估计函数将成为算法性能的关键；如果解空间较大，内存空间紧缺，那么采用迭代加深搜索算法效果更佳，
A星寻路算法
此文档由网络搜集而来。会者不难，A*(念作A星)算法对初学者来说的确有些难度。 这篇文章并不试图对这个话题作权威的陈述。取而代之的是，它只是描述算法的原理，使你可以在进一步的阅读中理解其他相关的资料。 最后，这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿，我在文章的末尾包含了一个指向例子程序的链接。压缩包包括C++和Blitz Basic两个语言的版本，如果你只是想看看它的运行效果，里面还包含了可执行文件。 我们正在提高自己。让我们从头开始。。。 序：搜索区域 假设有人想从A点移动到一墙之隔的B点，如下图，绿色的是起点A，红色是终点B，蓝色方块是中间的墙。 [图1] 你首先注意到，搜索区域被我们划分成了方形网格。像这样，简化搜索区域，是寻路的第一步。这一方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描述为从A到B我们经过的方块的集合。一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。
这些中点被称为“节点”。当你阅读其他的寻路资料时，你将经常会看到人们讨论节点。为什么不把他们描述为方格呢？因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形，六角形，或者其他任意形状。节点能够被放置在形状的任意位置－可以在中心，或者沿着边界，或其他什么地方。我们使用这种系统，无论如何，因为它是最简单的。 开始搜索 正如我们处理上图网格的方法，一旦搜索区域被转化为容易处理的节点，下一步就是去引导一次找到最短路径的搜索。在A*寻路算法中，我们通过从点A开始，检查相邻方格的方式，向外扩展直到找到目标。我们做如下操作开始搜索： 1，从点A开始，并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的方格，也可能不会。基本上，这是一个待检查方格的列表。 2，寻找起点周围所有可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方格。也把他们加入开启列表。为所有这些方格保存点A作为“父方格”。当我们想描述路径的时候，父方格的资料是十分重要的。后面会解释它的具体用途。 3，从开启列表中删除点A，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。 在这一点，你应该形成如图的结构。在图中，暗绿色方格是你起始方格的中心。它被用浅蓝色描边，以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中，它们被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格，也就是开始的方格。 [图2]
浅谈寻路A算法
浅谈寻路A*算法 算法 路是游戏中非常重要的一个元素，如何找到一条最短的路径是程序需要设计的算法，现在最为流行的寻路算法是A*算法。A*算法与状态空间搜索结合的相当紧密。 状态空间搜索，就是将问题求解的过程表现为从初始状态到目标状态寻找这个路径的过程，通俗的说就是在解一个问题的时候找到一条解题过程可以从求解的开始到问题的结束。 由于求解过程中求解条件的不确定与不完备性使得问题的求解过冲中的分支有很多，这就产生了多条求解的路径，这些路径过程一个图这个图就是状态空间。问题的求解时机上就是在这个图中找个一个路径可以从开始到结束，这个过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先，广度优先是从初始状态一层一层的向下找，知道找到结果目标为止，深度优先是按照一定的顺序先查找完一个分支再查找另一个分支，知道找到目标结果为止。这两种搜索方法有的很大缺陷是它们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很适合的算法，但是当空间很大并且不可预测的情况下就不可取。这个时候这两种算法的效率太低甚至有时是无法完成，所以要用到另一种算法---启发式搜索。 启发式搜索就是在状态空间中对每一个搜索为止进行评估，指导找到最好的为止，再
从这个位置进行搜索直到目标位置为止。在启发式搜索中对为止的评估是十分重要的，采用不同的估价可能有不同的结果。 启发式搜索中的估价函数表示为： 其中是节点的估价函数，是在状态空间中从初始点到节点的实际代价，是从节点到目标节点最佳路径的估价代价。这个里主要是体现了搜索的启发信息，因为是己知的。换个说法就是代表了索索的广度优先趋势但是当 时，可以省略，从而提高效率。 启发式搜索其实也有很多算法，比如局部择优搜索，最好优先搜索等。A*也是如此，这些算法都启用了启发函数，但在具体的选取最佳搜索节点时的策略不同。比如局部择优算法就是在搜索的过程中选取了最佳节点候舍弃了其他的兄弟节点，父亲节点并且一直搜索下去。这种搜索结果很明显，由于舍弃了其他的节点因此可能也把最佳的节点舍去偶尔。最好优先就聪明一点搜索的时候并没有舍去节点，除非该节点是死节点。在没一步的估价中都吧当前的节点和以前的节点的估价值进行比较从而得到最佳节点，这样防止了最佳节点的丢失。 A*算法也是一种最好优先的算法，只是加上了一些特定的约束条件，由于在一些问题求解时，希望能够求解出状态空间搜索的最短路径也就是用最快的方法求解出问题，A*算法的目的就是这样。其估价的函数可以表示为： 这里的是估价函数，是起点到终点的最短路径值，是到目标的最短 路径的启发值。由于是无法提前预先知道的，因此用前面的估价函数做近似 代表，但是g(n)≥g'(n)才可以通常都是大于所以不要考虑，但是代替时候需要才可以。可以证明应用这样的评估函数是可以找到最短路径的，因此应
连连看寻路算法
主题：[讨论]连连看寻路算法/全程求解算法 作者：华山论剑发表时间：2007-11-28 17:51:00 楼主遇到一个算法问题，希望朋友们多给些意见。 最近SDK写了个连连看游戏，其中的两点间寻路的算法基本上是用网上的一段代码，全路径求解算法则是自己写的， 遇到容易的矩阵可以秒杀，但遇到复杂的则速度就很慢了。希望大家给些意见，改善一下效率。 先说全程求解部分。 说明： 1、如果有解，找出解法； 2、如果无解，给出相对最佳路径； 3、如果有多解，找到一个就退出； 4、连连看的矩阵为10*12(10行，每行12张牌)，加上上下左右要各留一空行以便寻路，矩阵为12*14； 5、矩阵中某点值为0表示无牌，否则有牌； 6、矩阵不一定是初始状态，因为有时我们玩到一半可能用软件来求解。 例子数组： m[12][14] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 29, 3, 18, 26, 9, 2, 6, 33, 10, 9, 4, 15, 0, 0, 19, 18, 29, 7, 14, 9, 10, 23, 34, 16, 21, 15, 0, 0, 21, 27, 26, 2, 26, 11, 30, 17, 25, 14, 10, 5, 0, 0, 19, 12, 33, 33, 31, 34, 15, 11, 28, 7, 8, 23, 0, 0, 12, 16, 27, 4, 5, 21, 27, 8, 1, 6, 23, 4, 0,
0, 19, 34, 25, 1, 6, 26, 25, 15, 17, 12, 6, 31, 0, 0, 10, 4, 16, 17, 31, 8, 8, 7, 28, 28, 34, 30, 0, 0, 3, 21, 5, 14, 18, 2, 12, 20, 20, 2, 25, 1, 0, 0, 30, 20, 19, 31, 3, 9, 14, 16, 5, 29, 33, 3, 0, 0, 1, 20, 11, 27, 28, 17, 30, 18, 7, 29, 11, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } 这个数组也许是无解的，如果无解，则给出相对最好的解法。 基本流程： 1、复制矩阵和路径数组为m和way； 2、先找一个有牌点p1； 3、然后找其它几个配对的点same[N]； 4、依次检查p1和same[N]中的元素是否相通； 5、若相通则消去两张牌，若消完则返回； 6、没消完再递归寻路。 作者：雨中飞燕发表时间：2007-11-28 17:54:00 第1楼那个叫回溯嘛。。。。 作者：华山论剑发表时间：2007-11-28 17:56:00 第2楼下面是代码：
游戏自动寻路A算法
浅谈游戏自动寻路A*算法 寻路是游戏中非常重要的一个元素，如何找到一条最短的路径是程序需要设计的算法，现在最为流行的寻路算法是A*算法。A*算法与状态空间搜索结合的相当紧密。 状态空间搜索，就是将问题求解的过程表现为从初始状态到目标状态寻找这个路径的过程，通俗的说就是在解一个问题的时候找到一条解题过程可以从求解的开始到问题的结束。 由于求解过程中求解条件的不确定与不完备性使得问题的求解过冲中的分支有很多，这就产生了多条求解的路径，这些路径过程一个图这个图就是状态空间。问题的求解时机上就是在这个图中找个一个路径可以从开始到结束，这个过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先，广度优先是从初始状态一层一层的向下找，知道找到结果目标为止，深度优先是按照一定的顺序先查找完一个分支再查找另一个分支，知道找到目标结果为止。这两种搜索方法有的很大缺陷是它们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很适合的算法，但是当空间很大并且不可预测的情况下就不可取。这个时候这两种算法的效率太低甚至有时是无法完成，所以要用到另一种算法---启发式搜索。 启发式搜索就是在状态空间中对每一个搜索为止进行评估，指导找到最好的为止，
再从这个位置进行搜索直到目标位置为止。在启发式搜索中对为止的评估是十分重要的，采用不同的估价可能有不同的结果。 启发式搜索中的估价函数表示为： f(n)=g(n)+h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估价代价。这个里主要是h(n)体现了搜索的启发信息，因为g(n)是己知的。换个说法就是g(n)代表了索索的广度优先趋势但是当h(n)>>g(n)时，可以省略g(n)，从而提高效率。 启发式搜索其实也有很多算法，比如局部择优搜索，最好优先搜索等。A*也是如此，这些算法都启用了启发函数，但在具体的选取最佳搜索节点时的策略不同。比如局部择优算法就是在搜索的过程中选取了最佳节点候舍弃了其他的兄弟节点，父亲节点并且一直搜索下去。这种搜索结果很明显，由于舍弃了其他的节点因此可能也把最佳的节点舍去偶尔。最好优先就聪明一点搜索的时候并没有舍去节点，除非该节点是死节点。在没一步的估价中都吧当前的节点和以前的节点的估价值进行比较从而得到最佳节点，这样防止了最佳节点的丢失。 A*算法也是一种最好优先的算法，只是加上了一些特定的约束条件，由于在一些问题求解时，希望能够求解出状态空间搜索的最短路径也就是用最快的方法求解出问题，A*算法的目的就是这样。其估价的函数可以表示为： f'(n)=g'(n)+h'(n) 这里的f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最短路径的启发值。由于f'(n)是无法提前预先知道的，因此用前面的估价函数f(n）做近似g(n)代表g'(n)，但是g(n)≥g'(n)才可以通常都是大于所以不要考虑，但是h(n)代替h'(n)时候需要h(n)≤h'(n)才可以。可以证明应用这样的评估函数是可以找到最短路径的，因此应用这种评估函数的最好的优先算法就是A*算法。 至于h(n)的启发函数的信息性，就是在估计一个节点值的约束条件，如果信息越多或者约束条件越多则排除节点就越多，估价函数就越好或者说这个算法就越好。这就是为什么广度优先算法很不好的原因，因为起h(n)=0一点启发信息都没有，但是在游戏的开发中由于实时性的要求，h(n)的实质信息越多计算量也大消耗的时间就长，其次在牺牲算法准确性的前提下就可以适当的减少h(n)的启发信息。 我们先看下最好优先算法的逻辑（起始为止为A结束位置是P，字母后数字为节点的估价
A星寻路算法
//主要类 package { import classes.AStar; import classes.Grid; import classes.Node; import flash.display.MovieClip; import flash.display.Shape; import flash.display.Sprite; import flash.events.Event; import flash.events.MouseEvent; import flash.geom.PerspectiveProjection; import flash.utils.getTimer; import https://www.sodocs.net/doc/a89659953.html,Util; import https://www.sodocs.net/doc/a89659953.html,yout.PaddingLayoutFacet; /** * * @author LB * */ public class AStarPathFind extends Sprite { private var i:int; private var j:int; private var grid:Grid; private var cellWidth:int; public function AStarPathFind() { initMap(); initPlayer(); } private var player:MovieClip; private function initPlayer():void { player = new MovieClip(); player.graphics.beginFill(0x000000); player.graphics.drawRect(0,0,Node.cellWidth,Node.cellWidth);