A* 启发式搜索

新的算法当然要新开一片博文来水 ^ _ ^,我竟然这么久了才学这么垃圾的算法。。。。。


关于 $A$$*$ 这个算法,可以说很玄学。就像什么模拟退火一样,需要自己调一些参数,不同的参数跑出来是不一样的。

$A$$*$ 别名是启发式搜索,所以说,什么 $dfs$ 、 $bfs$ 都是 “盲目式搜索” 了??(23333

每次学习一个算法的时候,我都会先去查查 $Wikipedia$ (其实就是装。。。)。

$Wikipedia$ 中的 $A$$*$ 词条:

A*搜索算法(A* search algorithm)是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的 $NPC$ 的移动计算,或网络游戏的 $BOT$ 的移动计算上。

该算法综合了最良优先搜索和 $Dijkstra$ 算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。

在此算法中,如果以 $g(n)$ 表示从起点到任意顶点 $n$ 的实际距离, $h(n)$ 表示任意顶点 $n$ 到目标顶点的估算距离(根据所采用的评估函数的不同而变化),那么 算法的 $A$$*$ 估算函数为:

这个公式遵循以下特性:

  • 如果 $g(n)$ 为 0 ,即只计算任意顶点 $n$ 到目标的评估函数 $h(n)$ ,而不计算起点到顶点 $n$ 的距离,则算法转化为使用贪心策略的最良优先搜索,速度最快,但可能得不出最优解;
  • 如果 $h(n)$ 不大于顶点 $n$ 到目标顶点的实际距离,则一定可以求出最优解,而且 $h(n)$ 越小,需要计算的节点越多,算法效率越低,常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离;
  • 如果 $h(n)$ 为 0 ,即只需求出起点到任意顶点 $n$ 的最短路径 $g(n)$ ,而不计算任何评估函数 $h(n)$ ,则转化为单源最短路径问题,即 $Dijkstra$ 算法,此时需要计算最多的顶点。

$Wikipedia$ 中一直把 $A$$*$ 和 $Dijkstra$ 、最良优先搜索(Best-first search)进行比较。

去翻了一下斯坦福的论文($A$$*$ 就是斯坦福学生研究出来的),然后看到一些比较有意义的图片和概念。

对于这么一个情况,我们要进行搜索:

可以发现,如果对于简单最良优先搜索,就会出现这种情况(用红色路径表示),一直到箭头处才检测到障碍物(detect obstacle),我们人为看到的最短路径用蓝色路径表示。所以说,这最良优先搜索很容易被卡掉。

那么这个时候就需要配合一下估值函数:

一边走,一边计划前面的路线。显然,要在搜索和计划两个点中间找到一个平衡才能使这个算法最快。

计划路线就是 $A$$*$ 里的 $h(n)$ 。

动态的来看 $A$$*$ 算法是这样的:(图源于 $Wikipedia$)

然鹅,对于其他的算法:

在没有障碍中的表现:

  • $Dijkstra$ (因为用来求最短路,所以这里的 $Dijkstra$ 感觉更像 $bfs$ ):

搜索了一个圆才搜到答案,这就是完全没有估价函数。

  • 最良优先搜索(Best-first search):

这就是完全靠估价函数的后果。

在没有什么障碍的图中,具有贪心性质的最良优先搜索肯定更优。

但是!出题人发神经才会出这么简单的题,对于一般的障碍物来说:

  • $Dijkstra$:

好像差不多。。。。。

  • 最良优先搜索:

这就差的多了。。。

对于 $A$$*$ 来说,两种情况都比较稳定:

然后, $A$$*$ 的思想就是这样,对于那些估价函数,像上面引用的来说,有欧几里得距离、曼哈顿距离、切比雪夫距离。

这些有时间再说,估价函数也可以自己打。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×