首页 > 代码库 > 聪明的搜索算法’ A*算法

聪明的搜索算法’ A*算法

A*算法

    是一种启发式的搜索算法。

    了解BFS、DFS或者Dijkstra算法的人应该知道。这些算法都是一种向四周盲目式搜索的方法。

 

启发式搜索:

    启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是十分重要的。不同的估价可以有不同的效果。因此,A*算法的关键就在于如何建立这个启发函数。

   公式表示为:f(n)=g(n)+h(n),

  f(n) 是从初始点经由节点n到目标点的估价函数,

   g(n) 是在状态空间中从初始节点到n节点的实际代价,

   h(n) 是从n到目标节点最佳路径的估计代价。

 

A* 算法与广度、深度优先和 Dijkstra 算法的联系:

   1、g(n) = 0 时:该算法类似于DFS。

    2、h(n) = 0 时:该算法类似于BFS。

    3、如果h(0) = 0,只需求出g(n)(即起点到任意点n的最短路径)时,则转化成单源最短路径问题。

 

A*算法浅析:

A*算法与其他搜索路径的算法的最大区别在于其估计函数的设计,也就是公式:f(n)=g(n)+h(n)中h(n)的设计

一般计算h(n)的方法有下面几种:

1、曼哈顿距离: |x1-x2| + |y1-y2|。

2、欧式距离:  两点之间的直线距离。

3、切比雪夫距离:max(|x2-x1|,|y2-y1|)。

 技术分享这幅图中绿色的线代表欧式距离,其他均为曼哈顿距离

技术分享该图中,F6E2切比雪夫距离为:4

 

接下来的分析中,我们的h(n)为曼哈顿距离,g(n)为欧式路径

假设我们需要搜索的情况如下:

技术分享

绿色为起始点,红色为目标,蓝色为障碍物,黑色为可通行路径。

 

F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F,G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的,F被打印在左上角,G在左下角,H则在右下角

技术分享

 

 

接下来我们来讲讲A*算法的流程:

1,把起始格添加到开启列表。

2,重复如下的工作:

      a) 寻找开启列表中F值最低(最佳估值)的格子,把它切换到关闭列表。

      b) 对相邻的格中的每一个格子进行判断

          * 如果它不可通过或者已经在关闭列表中,略过它。反之如下。

          * 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。

          * 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。

      c) 停止,当你

          * 把目标格添加进了关闭列表(注解),这时候路径被找到,或者

          * 没有找到目标格,开启列表已经空了。这时候,路径不存在。

3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。

 

下篇文章,我将使用A*算法解决一个经典的八数码问题。

from: http://blog.csdn.NET/cyh_24/article/details/8018752

聪明的搜索算法’ A*算法