A是一种启发式搜索,根据目标地点和当前点的距离
和估计要走的步数
来决策下一步走哪个方向。而这两个参数,一般用$g(x)$和$h(x)$,其中$g(x)$为$x$点到目标点的实际距离。 所以最终的我们要走哪个点取决于$g(x)+h(x)$,取可选点中$g(x)+h(x)$最优的那个点走。 *而k短路,就是终点第K次被找到的时候。
随便从网上扒了一份图,根据图来详细了解下 这份图因为在博客园出现过,在简书也出现过,且都未标注原创是谁,所以这里我直接拿来用了,如有侵权,请回复,我会删除此文
现在来看看图,现在我们要从$A$点走到$B$点,假设我们可走8个方向($↑,↓,←,→,↖,↗,↙,↘$)。(后文均用箭头代指方向) 先求出实际花费(就是↑,↓,←,→,↖,↗,↙,↘8个点到$B$点的最短路,用Dijkstra或者SPFA等常用最短路算法跑一遍就行了) 尊重原图,这里设每走一格花费为10,所以走第一步的$g$如下: ↑:50(表示从$A$向上走一步再走到$B$的最短路长为50,注意这里的50是从$A$->$A↑$到$B$的最短路,不是从$A↑$到$B$的最短路。下同) ↓:50 ←:50 →:30 ↖:60 ↗:40 ↙:60 ↘:40
上图中左下角为到B点的估算值$h(x)$, 右下角为 实际距离。左上角为二者之和。最短路问题,走过了该点就不再走第二次了,所以我们把$A,C$点标记,不再进入这2个点。然后再根据$C$点的可行路径,在所有可走范围内再次寻找加权和最小的那点,这里我们用
优先队列
实现这个不断BFS搜寻可行路,并且不断取出加权和最小的点的过程 最终结果如下:
1 |
|
A的时间复杂度取决于h(x)函数的选择,在网上并未找到具体的分析,不过需要注意的是,如果图为n元环,A算法的时间花费将会是指数级的(摘自wiki),一般遇到这类问题的时候,都是采用可持久化可并堆进行优化,具体怎么优化。。。。。蒟蒻博主还未学习学会了再来贴上代码和分析~~~