Astar算法笔记

A*算法笔记

A*算法介绍

A*算法最初发表于1968年，由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展。

A*算法属于启发式搜索(Heuristically Search)。

---

其他搜索算法

1.广度优先搜索

以广度为优先级向外拓展。

2.Dijkstra算法

由迪杰斯特拉在1956年提出，利用贪心策略，每次拓展权值最小的节点直到终点，如果每个节点权值相同，将退化成BFS。

3.最佳优先搜索(Best First)

预先计算出每个节点到终点的距离，利用优先队列选取代价最小的节点，但是又最大的缺点就是搜索结果不一定是最优解。

---

A*算法具体实现

A*算法利用下面的函数计算优先级

$$f(n)=g(n)+h(n)$$

其中:

• f(n)为综合优先级

• g(n)为从起点出发已消耗的代价

• h(n)为节点距离终点预计代价，即启发式函数

并且使用两个集合表示待遍历节点(open)和已遍历节点(close)。

input：图，点和边的集合。

output：最优路径

伪代码

将起点加入open表;
while(open表不为空){
    取出open表中优先级最高的节点n;
    if(n为终点){
        从终点回溯构造最优路径;
        返回最优路径;
    }else{
        将n加入close表;
        for(遍历邻居节点){
            if(邻居节点在close表中||无法拓展) 跳过;
            if(邻居节点在open表中){
                更新g(n);
            }else{
                计算优先级;
                将n设置为父节点;
                将此邻居节点加入open表中;
            }
        }
    }
}
如果open表为空，则起点终点不连通;

启发式函数

利用启发式函数可控制A*算法行为。

• 如果h(n) = 0，算法退化为Dijkstra算法。

• 如果h(n)总小于实际值，则结果一定为最短路径，不会漏解。越小可扩展节点越多，算法越慢。

• 如果h(n)等于实际值，扩展路径即为最短路径，无法实现。

• 如果h(n)大于实际值，有可能漏解，但是扩展节点变少，算法速度变快。

通过以上几种情况可知，我们可以设计h(n)函数达到我们目的，这就是A*算法灵活所在。

---

关于地图

算法关注的只有图(Graph)，对于算法效率而言，图的节点数越少越好，这样扩展节点少遍历次数也少。

包括栅格地图，多边形地图 …

---

关于距离

基于栅格地图

Manhattan距离

在不允许对角扩展的情况下，可以使用曼哈顿距离,D为移动代价。

$$h(n)=D\ast (abs(n.x-goal.x)+abs(n.y-goal.y))$$

对角线距离

在允许对角移动是，可以使用对角线距离，D为上下左右移动代价，D2为对角移动代价，如D2=sqrt(2)*D。

$$h\_diagonal(n)=min(abs(n.x-goal.x),abs(n.y-goal.y))$$

$$h\_straight(n)=(abs(n.x-goal.x)+abs(n.y-goal.y))$$

$$h(n)=D2\ast h\_diagonal(n)+D\ast (h\_straight(n)-2\ast h\_diagonal(n))$$

参考资料：

Introduction to the A* Algorithm

https://zhuanlan.zhihu.com/p/54510444

PathFinding.js

A*—java代码 - 木子木泗 - 博客园

https://www.gamedev.net/reference/articles/article2003.asp

A*算法中启发函数的使用_free4wuyou的专栏-CSDN博客_启发函数