GIS数字校园漫游导航设计+文献综述(3)
2．2 几种路径优化算法
2.2.1 Dij kstra 算法
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min［dj, dk+lkj］ (2.1)
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min［dj, 所有未标记的点j］ (2.2)
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
i=j* (2.3)
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。
Dijkst ra 算法主要特点是以起终点为中心向外层层扩展 ,直到扩展到终点为止。图2.1 表示了 Dijkst ra 算法的搜索空间。Dijkst ra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低[13]。
2.2.2 A * 算法
A * 算法是目前广为流行的路径规划启发式算法 ,它是一种最佳优先搜索算法,对实现道路网的最佳优先搜索十分有用。A * 算法已应用于各个领域 ,而不仅仅是车辆路径规划，如机器人和其他要求最小费用的领域。引入启发式信息会高效率。启发式是一种经验方法 ,即是一种以牺牲完备性要求为代价来提高搜索效率的技巧。启发式信息有助于确定哪个节点“最有希望”生成哪些后继节点和修剪那些相关分支。通过选择合适的估价函数， A * 算法寻找最优路径所使用的搜索空间比经典 Dijkst ra 算法小 。采用启发信息的目的是提供一个节点距离目标节点有多远的估计 ,以使搜索算法优先考虑最有希望的节点 ,即具有最小估价函数的节点。定义节点 n 的启发式估价函数f ′( n) 为：
f′(n) = g ( n) + h′( n) (2.4)
式中：g ( n) 是从原点到当前节点 n 的实际费用，h′( n) 是从当前节点到目标节点的最小费用的估计函数，则A * 算法优先搜索具有最小 f (′ n) 的节点。图 2.2 为A * 算法的示例 [14]。
2.2.3 A* 优先算法
人们通过研究发现 ,驾驶员喜欢大多数时间在高速公路上行驶 ,而不是在交叉口较多的路段行驶 。而A * 优先算法就是根据驾驶员的偏好进行设计的 ,是A * 算法的改进 。确保车辆在高速公路上行驶的方法是使除了高速公路以外的道路使启发式函数 ( 2 ) 乘以一个大于 1 的数 。如图 3描述了高速公路比其他道路具有较高的优先权 。从图 3 中可以看出 ,所有的节点 ( 1 ,2 和 3 ) 到原点的距离是相同的 。假设它们的 ( x , y ) 坐标相同 , 那么它们的启发(式函数 h′ n) 也该相同 。对于正常的A * 算法 ,被扩展的节点是根据点在 O PEN表中的位置确定的 ,具有最小估价函数的节点首先被扩展 。但是对于A * 优先算法高速公路被赋予较高的优先权 ,因此 ,节点 2 将首先被扩展 。尽管从原点到节点 2 的距离等于原点到节点 1 、 的距离 ,通过节点 1 、 的启发式函数乘以一33个比 1 大的数值使得节点 2 的启发式函数比它们小 ,因此 ,节点 2 将首先被扩展 。由于高速公路赋予了较高优先权 ,将获得一个具有驾驶员偏好的最优路径 。这个最优路径可能不是距离最短的 ,但可能会更快地到达目的节点 ,这是由于车辆在高速公路上可以以较高的速度行驶 。通过试验验证 ,当原点与目标节点不在一个区域时 , A * 优先算法将比A * 算法搜索空间小 [14]。