GIS数字校园漫游导航设计+文献综述(4)
2.2.4 A* 双向分层启发式算法
对最短路径算法和A * 算法的研究 ,将使我们能够把它们推广至一个双向搜索算法 。在前面算法的讨论中 ,总是假定算法从给定原节点到目标节点搜索最小费用路径 ,这被称为前向搜索 。实际上 ,从目标节点到原节点进行后向搜索应该产生同样的结果 ( 只要每一条路段原费用是相同的 ) ,通常称为后向搜索 ,这导致了双向搜索的思想 。双向搜索的基本过程是从原节点到目标节点计算最小费用路径 ( 前向搜索 ) ,同时 ,计算从目标节点到原点的最小费用路径 ( 后向搜索) 。如果搜索算法在单处理机上运行 ,算法必须在前面和后面搜索之间迅速切换 ,双向搜索至少可以减少搜索空间 50 % ,因此 ,算法的运行时间比非双向搜索少很多 。由A * 算法检查的搜索空间与双向搜索算法检查的搜索空间之间的一般关系如图 2.3 所示。
理想情况是双向搜索在中间相遇，但是如果从原节点到目标节点存在 N 条不同的路径，搜索可能不在中间相遇，,2 种搜索可能在相遇前几乎找到完整路径，或者一个找到完整路径而另一个在它们相遇前几乎找到一条完整路径。换言之，存在重复工作。例如一个仅考虑旅行费用的启发式估价函数的不正确终止标准，可能导致双向启发式搜索工作量为单向启发式搜索的2倍。因此，终止标准和启发式估价函数的选择对于正确执行双向启发式搜索很重要。
为了消除这种最坏情况，必须设计一个较好的前向和后向启发式搜索切换标准。在双向算法中，前向和后向搜索算法不是交替进行的，它取决于最佳节点的启发式估价函数f ′(n)。如果在前向搜索中当前节点的估价函数小于后向搜索当前节点的估价函数，这就意着在前向搜索中当前节点更靠近目标节点，此时执行前向搜索。反之，则执行后向搜索。因为2个方向的搜索不是交替执行的，能够大大地节省算法的运行时间[14]。
2.2.5 几种算法对比
通过比较，可以发现：
1) 原节点与目标节点在同一区域内搜索20个节点：Djikst ras 算法所花费的时间为425s，平均用时21.3s，排名第4 ；A*单向搜索算法所花费的时间为92s ，平均用时4. 6s ,排名第2；A *优先搜索算法所花费的时间为 82s，平均用时4.1s，排名第1；A*双向分层搜索算法所花费的时间为106 s ,平均用时5.3s，排名第3。
2) 原节点与目标节点不在同一区域内搜索20个节点：Djikst ras算法所花费的时间为1040s，平均用时52s，排名第4；A*单向搜索算法所花费的时间为241.4s，平均用时12.07s，排名第3；A3优先搜索算法所花费的时间为225s，平均用时11.25s，排名第2；A*双向分层搜索算法所花费的时间为194.2s，平均用时9.71s，排名第1。
通过以上结论可以看出当原节点与目标节点在同一区域时，使用A*优先搜索时间最短，效率最高；当原节点与目标节点在不同区域时，使用A*双向分层搜索算法搜索时间最短，效率最高；其次是A*优先搜索算法。
4种常用的算分性能如下表2.1所示。
Dij kstra 算法 A * 算法 A* 优先算法 A* 双向分层启发式算法
性能 能得出最短路径的最优解，但是效率较低 折中 当原节点与目标节点在同一区域时，效率最高 当原节点与目标节点在不同区域时，效率最高
综合几种算法，在数字校园漫游导航的程序中，考虑到路径导航不会太远，可以以某一地点为中心起点，进行路径导航，加上Dijkstra算法较为简便，所以本文选择了此算法，方便程序的制作和运行。