论文部分内容阅读
摘 要：A*（A-Star）算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。本文对A*算法的原理及实现过程进行了详细的研究分析。
关键词：A*算法 最短路径算法 启发式算法
1.启发式搜索算法
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），从而提高效率。
2.A*算法初步
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法 都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，在搜索时没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，这就是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）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。
3.A*算法在搜索最短路径中的应用
A*算法是最好优先算法的一种。只是有一些约束条件而已。 最好优先算法的算法流程如下：有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED 表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一 步只考虑OPEN表中状态最好的节点。具体搜索过程如下：
1）初始状态：
OPEN=[A5]；CLOSED=[]；
2）估算A5，取得搜有子节点，并放入OPEN表中；
OPEN=[B4，C4，D6]；CLOSED=[A5]
3）估算B4，取得搜有子节点，并放入OPEN表中；
OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]
4）估算C4；取得搜有子节点，并放入OPEN表中；
OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]
5）估算H3，取得搜有子节点，并放入OPEN表中；
OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=H3C4，B4，A5]
6）估算O2，取得搜有子节点，并放入OPEN表中；
OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]
7）估算P3，已得到解；
A*算法的流程与此是一样的，只要注意估价函数中的g（n）的h（n）约束条件就可以了。创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的h（s），将起点放入OPEN表，保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是所求的路径。算法伪代码如下
关键词：A*算法 最短路径算法 启发式算法
1.启发式搜索算法
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），从而提高效率。
2.A*算法初步
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法 都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，在搜索时没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，这就是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）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。
3.A*算法在搜索最短路径中的应用
A*算法是最好优先算法的一种。只是有一些约束条件而已。 最好优先算法的算法流程如下：有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED 表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一 步只考虑OPEN表中状态最好的节点。具体搜索过程如下：
1）初始状态：
OPEN=[A5]；CLOSED=[]；
2）估算A5，取得搜有子节点，并放入OPEN表中；
OPEN=[B4，C4，D6]；CLOSED=[A5]
3）估算B4，取得搜有子节点，并放入OPEN表中；
OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]
4）估算C4；取得搜有子节点，并放入OPEN表中；
OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]
5）估算H3，取得搜有子节点，并放入OPEN表中；
OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=H3C4，B4，A5]
6）估算O2，取得搜有子节点，并放入OPEN表中；
OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]
7）估算P3，已得到解；
A*算法的流程与此是一样的，只要注意估价函数中的g（n）的h（n）约束条件就可以了。创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的h（s），将起点放入OPEN表，保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是所求的路径。算法伪代码如下