高级搜索之A星算法解析

�
�
�
F被打印在左上角，G在左下角，H则在 右下角。
� � � �
�
�
继续搜索 为了继续搜索，我们简单的从开启列表中选择 F值最低的方 格。然后，对选中的方格做如下处理： 4，把它从开启列表中删除，然后添加到关闭列表中。 5，检查所有相邻格子。跳过那些已经在关闭列表中的或者 不可通过的(有墙，水的地形，或者其他无法通过的地形 )， 把他们添加进开启列表，如果他们还不在里面的话。把选中 的方格作为新的方格的父节点。 6，如果某个相邻格已经在开启列表里了，检查现在的这条 路径是否更好。换句话说，检查如果我们用新的路径到达它 的话，G值是否会更低一些。如果不是，那就什么都不做。 另一方面，如果新的G值更低，那就把相邻方格的父节点改 为目前选中的方格（在上面的图表中，把箭头的方向改为指 向这个方格）。最后，重新计算F和G的值。
2011-4-19
� 状态空间搜索 ，将问题求解过程表现为从初始 状态到目标状态寻找这个路径的过程。 � 由于求解问题的过程中分枝有很多，使得求解的路径 很多，这就构成了一个图，这个图就是状态空间。 � 问题的求解实际上就是在这个图中找到一条路径可以 从开始到结果。这个寻找的过程就是状态空间搜索。 � 常用的状态空间搜索有深度优先和广度优先。 � 广度和深度优先搜索有一个很大的缺陷就是他们都是 在一个给定的状态空间中穷举。这在状态空间不大的 情况下是很合适的算法，可是当状态空间十分大，且 不预测的情况下就不可取了。他的效率实在太低，甚 至不可完成。在这里就要用到启发式搜索了。
�
在这一点，你应该形成如图的结构。在 图中，暗绿色方格是你起始方格的中心。 它被用浅蓝色描边，以表示它被加入到 关闭列表中了。所有的相邻格现在都在 开启列表中，它们被用浅绿色描边。每 个方格都有一个灰色指针反指他们的父 方格，也就是开产生的路径，移动到网格 上指定方格的移动耗费。 H = 从网格上那个方格移动到终点 B的预估 移动耗费。 令水平或者垂直移动的耗费为 10，对角线方 向耗费为14。 H值可以用不同的方法估算。这里使用的方法 被称为曼哈顿方法，它计算从当前格到目的 格之间水平和垂直的方格的数量总和，忽略 对角线方向。然后把结果乘 以10。

A星算法详解范文A*算法是一种常用的启发式算法，多用于解决图问题。

它是一种综合了Dijkstra算法和贪心算法的算法，利用估算函数来接近最短路径，提高效率。

下面我们来详细介绍A*算法。

A*算法的核心思想是综合考虑两个值：实际路径长度g(n)和启发式函数预估路径长度h(n)。

实际路径长度是指从起始点到当前点的路径长度，启发式函数预估路径长度是指从当前点到目标点的路径长度。

基于这两个值，A*算法会在过程中选择总的路径长度（f(n)=g(n)+h(n)）最小的点进行扩展。

A*算法的伪代码如下：1. 将起始点加入open列表，并将起始点的f(n)值设为0。

2. 当open列表不为空时：a. 从open列表中选择f(n)值最小的点，并将该点加入closed列表。

b.如果选择的点是目标点，则结束，返回路径。

c.对于选择的点的每一个相邻点：i. 如果相邻点不可通行或者已经在closed列表中，则忽略。

ii. 如果相邻点不在open列表中，则将其加入open列表，并更新相邻点的父节点为选择的点，并计算相邻点的f(n)值。

iii. 如果相邻点已经在open列表中，比较从当前选择的点到相邻点的实际路径长度是否小于之前计算的路径长度，如果是，则更新相邻点的父节点和f(n)值。

A*算法的关键在于如何选择合适的启发式函数。

一个好的启发式函数应该尽量准确地估计从当前点到目标点的路径长度。

启发式函数常用的有以下几种形式：1.曼哈顿距离：启发式函数的值为当前点到目标点在格子网格中的曼哈顿距离，即横向和纵向的距离之和。

2.欧几里得距离：启发式函数的值为当前点到目标点的欧几里得距离，即两点之间的直线距离。

3.切比雪夫距离：启发式函数的值为当前点到目标点在格子网格中的切比雪夫距离，即横向和纵向的距离中最大的距离。

4.对角线距离：启发式函数的值为当前点到目标点在格子网格中的对角线距离，即两点之间的最短距离。

A*算法的优点是可以找到最短路径，而且在启发式函数设计合理的情况下，能够较快地找到最优解。

，
估价值h(n)<= n到目标节点的距离实际值，这种情况下， 搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 估价值>实际值,搜索的点数少，搜索范围小，效率高 ，但丌能保证得到最优解 PPT DESIGN
常见估价函数
（1）曼哈顿距离： 就是在欧几里德空间的固定直角坐标系上两点所形成的线 段对轴产生的投影的距离总和，例如在平面上，坐标（x1,y1） 的点P1不坐标（x2, y2）的点P2的曼哈顿距离为：|x1 - x2| + |y1 - y2|。 （2）欧氏距离： 它是在m维空间中两个点之间的真实距离。在二维和三维 空间中的欧氏距离的就是两点之间的距离。例如在平面上，坐 标（x1,y1）的点P1不坐标（x2, y2）的点P2的欧氏距离为： sqrt((x1-x2)^2+(y1-y2)^2 )。 （3）切比雪夫距离： 是两个向量之间各分量差值的最大值。例如在平面上，坐 标（x1, y1）的点P1不坐标（x2, y2）的点P2的切比雪夫距离 为：max(|x1 - x2| , |y1 - y2|) PPT DESIGN
【2】/page/resources/_/technical/artificialintelligence/a-pathfinding-for-beginners-r2003
PPT DESIGN
1，把起始格添加到开启列表。 2，重复如下的工作： a) 寻找开启列表中F值最低的格子。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的格中的每一个？ * 如果它丌可通过戒者已经在关闭列表中，略过它。反之如下。 * 如果它丌在开启列表中，把它添加迚去。把当前格作为这一格的父节点。记录 这一格的F,G,和H值。 * 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值 意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一 格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列 表排序。 d) 停止，当你 * 把目标格添加迚了关闭列表(注解)，这时候路径被找到，戒者

算法策略1
• A*算法的核心是一个估价函数：f(n) = g(n) + h(n)，它是选择从当前位置移动到下一位置 的依据。 • g(n):起点到当前位置的实际耗费； • h(n):当前位置到终点的估计耗费（A*之所 以叫做启发式）
算法策略2
• A*结合Dijkstra和贪心BFS 的有效信息。 • h（n）=0的A*就是Dijkstra算法。每一步估 价中，保证了g（n）距离起点的最小性和 与其父亲的指向关系。 • 从当前结点扩展到下一节点的依据：取f最 小者，在open表（考虑g等值的结点）中选 择离终点最近的结点-----贪心BFS。
实际效果
• 在图的规模比较大的时候，该算法是比较 快速的一种寻路方法，大大的降低了搜索 空间。 • 空间需求太大 。 • 时间复杂度依赖于估值函数。 • H（n）----应该是选择最优的启发式的函数
发展和应用
• 算法灵活，适用性广（A*是最基本的“元 素”，我看到很多算法都是在A*基础上改 变的） • 在游戏中有它很典型的用法，是人工智能 在游戏中的代表。 • 在游戏开发中由于实时性的问题，h(n)的信 息越多，它的计算量就越大，耗费的时间 就越多。就应该适当的减小h(n)的信息，即 减小约束条件（平衡的问在图中进行搜索，高效地找到两个指定结 点之间的一条最短路。
提出的动机
• 为了在（大的）状态空间中高效率的找到 最短路径，提出了启发式搜索，它利用一 个估价函数，省掉大量无关的搜索路径 • A*是一种启发式搜索算法，它在每一步估 价中，选择当前所有节点（open表）中的 “最佳结点”，从而高效的找到图中的两 个结点间的最短路。
算法策略3
• 1，把起始格添加到open表。 • 2，重复如下的工作： a) 寻找开启列表中F值最低的格子。我们称它为当前格。 b) 把它切换到closed表。 c) 对相邻的所有格中的每一个 * 如果它不可通过或者已经在关闭列表中，略过它。 反之如下。 * 如果它不在开启列表中，把它添加进去。把当前 格作为这一格的父节点。记录这一格的F,G,和H值。 * 如果它已经在开启列表中，用G值为参考检查新的 路径是否更好。更低的G值意味着更好的路径。如果是这样，就 把这一格的父节点改成当前格，并且重新计算这一格的G和F值。 d) 停止，当 * 把目标格添加进了关闭 关闭列表，这时候路径被找到， 关闭 ， 或者 * 没有找到目标格，开启列表已经空了。这时候， 路径不存在。 • 3，保存路径。从目标格开始，沿着每一格的父节点移动直到回 到起始格。这就是最短路径。