A* 启发式搜索算法是对 Dijkstra 算法的改进版本，它和后者的主要差别在于，加入了到终点的距离量化，使得 A* 算法不会像 Dijkstra 算法那样“跑偏”。
问题分析
之前我们介绍过 Dijkstra算法（下面简写成 D算法），不知道你有没有发现这样一个问题：当地图特别大的时候，D算法 的执行时间会非常长，为了确定自己找到的是最短路径，算法执行了大量的“跑偏”计算。
D算法有点儿类似 BFS算法 ，它每次回寻找与当前节点最近的顶点，向外扩展。但是，这种扩展思路其实比较盲目，这里举个例子：
地图.jpg
在 D算法 的实现过程中，最先被搜索到的顶点依次是 1，2，3。很明显，这种搜索方向“跑偏了”。
在工程中，不一定要找到问题的最优解，我们可以一定程度地接受次优解，尤其是这个次优解会节省大量计算资源的时候。基于这样的理念，A* 算法 应运而生。
算法解析
在 A* 算法中，除了当前顶点和起始顶点的距离 g(i) （ i 为顶点编号），还要考虑当前顶点到终点的 直线距离 （注意，是直线距离，不是路径距离） h(i) ,这个距离的专业叫法是 启发函数 。这个距离非常好计算，我们可以用 “勾股定理” 轻松求出，但是为了减少计算机的计算量，这里选择 曼哈顿距离 ，其计算方式如下：
int hManhattan(Vertex v1, Vertex v2) { // Vertex表示顶点，后面有定义
return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}
有了启发函数，我们可以使用 估值函数 f(i) 代替 D算法 中的 dist数组 ，它的计算如下：
f( i ) = g( i ) + h( i )
根据这个定义，我们需要修改在 D算法 中的 vertex：
private class Vertex {
public int id; // 顶点编号ID
public int dist; // 从起始顶点，到这个顶点的距离，也就是g(i)
public int f; // 新增：f(i)=g(i)+h(i)
public int x, y; // 新增：顶点在地图中的坐标（x, y）
public Vertex(int id, int x, int y) {
this.id = id;
this.x = x;
this.y = y;
this.f = Integer.MAX_VALUE;
this.dist = Integer.MAX_VALUE;
}
}
// Graph类的成员变量，在构造函数中初始化
Vertex[] vertexes = new Vertex[this.v];
// 新增一个方法，添加顶点的坐标
public void addVetex(int id, int x, int y) {
vertexes[id] = new Vertex(id, x, y)
}
A* 算法的主要代码实现在下面，这里要说明它和 D算法 的三点区别：
- 优先级队列的构建不同：A* 根据 f 构建优先队列，而 D算法根据 dist（也就是 g）构建优先队列；
- A* 会在更新 dist 的时候同步更新 f 值；
- 循环结束条件不同：D算法 在终点出队列的时候结束，A* 在遍历到终点就结束。
public void astar(int s, int t) { // 从顶点s到顶点t的路径
int[] predecessor = new int[this.v]; // 用来还原路径
// 按照vertex的f值构建的小顶堆，而不是按照dist
PriorityQueue queue = new PriorityQueue(this.v);
boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
vertexes[s].dist = 0;
vertexes[s].f = 0;
queue.add(vertexes[s]);
inqueue[s] = true;
while (!queue.isEmpty()) {
Vertex minVertex = queue.poll(); // 取堆顶元素并删除
for (int i = 0; i < adj[minVertex.id].size(); ++i) {
Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist,f
nextVertex.dist = minVertex.dist + e.w;
nextVertex.f
= nextVertex.dist+hManhattan(nextVertex, vertexes[t]);
predecessor[nextVertex.id] = minVertex.id;
if (inqueue[nextVertex.id] == true) {
queue.update(nextVertex);
} else {
queue.add(nextVertex);
inqueue[nextVertex.id] = true;
}
}
if (nextVertex.id == t) { // 只要到达t就可以结束while了
queue.clear(); // 清空queue，才能推出while循环
break;
}
}
}
// 输出路径
System.out.print(s);
print(s, t, predecessor); // print函数请参看Dijkstra算法的实现
}
这个算法比 D算法快速，但是A* 算法无法获得最短路径
如果我想获得最短路径，最笨的办法是使用回溯算法：
回溯穷举.jpg
而动态规划（D算法），可以通过剪枝减少计算：
Dijkstra剪枝.jpg
而 A* 算法 使用了贪婪策略，它选择最小的 f 值 作为路径选择的依据，且在第一次遇到终点的时候就结束，这使得 A* 算法没有考察其它路线（实际上这也是它更少耗费资源的原因），也就不可能找出最短路径了。
总结
- 启发式搜索算法通过利用估价函数避免“跑偏”
- A* 使用了贪婪策略，通过节课的例子，我们有一个新的认识：在工程中可以允许次优解的出现（如果要找到最优解会耗费大量资源的话），而寻找次优解的一大途径就是使用 贪婪策略
- 所以，我们可以笼统地对三种算法的资源耗费进行排序：回溯>动态规划>贪婪
以上就是全部内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论