在 Dijkstra 算法的实现思路中,我们用一个优先级队列,来记录已经遍历到的顶点以及这
个顶点与起点的路径长度。顶点与起点路径长度越小,就越先被从优先级队列中取出来扩
展,从图中举的例子可以看出,尽管我们找的是从 s 到 t 的路线,但是最先被搜索到的顶
点依次是 1,2,3。通过肉眼来观察,这个搜索方向跟我们期望的路线方向(s 到 t 是从西
向东)是反着的,路线搜索的方向明显“跑偏”了。
之所以会“跑偏”,那是因为我们是按照顶点与起点的路径长度的大小,来安排出队列顺序
的。与起点越近的顶点,就会越早出队列。我们并没有考虑到这个顶点到终点的距离,所
以,在地图中,尽管 1,2,3 三个顶点离起始顶点最近,但离终点却越来越远。
如果我们综合更多的因素,把这个顶点到终点可能还要走多远,也考虑进去,综合来判断哪
个顶点该先出队列,那是不是就可以避免“跑偏”呢?
当我们遍历到某个顶点的时候,从起点走到这个顶点的路径长度是确定的,我们记作 g(i)
(i 表示顶点编号)。但是,从这个顶点到终点的路径长度,我们是未知的。虽然确切的值
无法提前知道,但是我们可以用其他估计值来代替。
这里我们可以通过这个顶点跟终点之间的直线距离,也就是欧几里得距离,来近似地估计这
个顶点跟终点的路径长度(注意:路径长度跟直线距离是两个概念)。我们把这个距离记作
h(i)(i 表示这个顶点的编号),专业的叫法是启发函数(heuristic function)。因为欧几
里得距离的计算公式,会涉及比较耗时的开根号计算,所以,我们一般通过另外一个更加简
单的距离计算公式,那就是曼哈顿距离(Manhattan distance)。曼哈顿距离是两点之间
横纵坐标的距离之和。计算的过程只涉及加减法、符号位反转,所以比欧几里得距离更加高
效。
原来只是单纯地通过顶点与起点之间的路径长度 g(i),来判断谁先出队列,现在有了顶点到
终点的路径长度估计值,我们通过两者之和 f(i)=g(i)+h(i),来判断哪个顶点该最先出队
列。综合两部分,我们就能有效避免刚刚讲的“跑偏”。这里 f(i) 的专业叫法是估价函数
(evaluation function)。
1
2
3
int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示顶点,后面有定义
return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}