孙玉昕,章 瑾

(武汉工程大学计算机与科学学院，湖北 武汉 430074)

0 引 言

路径搜索的核心思想是利用计算机的处理能力，准确高效地在网络中任意两个或多个节点之间寻找出最佳路径.路径搜索算法在计算机工程中有着广泛的应用价值，比如地理信息系统、位置服务、智能交通、智能机器人等领域[1].在工程实践中，路径搜索的时间效率和空间效率是判断算法的优劣重要指标[2].启发式搜索和盲目搜索相比，可省略大量无谓的搜索路径，已能够极大提高搜索效率，但当面临百万节点的复杂网络拓扑时，启发式搜索算法的搜索耗时将会呈指数级快速增长，无法满足需求，因此考虑引入二叉堆进行进一步的算法优化，使得搜索速度进一步提升.

1 实验部分

1.1 算法选择

路径搜索的核心算法就是最短路径算法 ,它是计算机科学与地理信息科学等领域研究的热点.目前已知的最短路径算法主要有 Floyd (弗洛伊德)算法、矩阵算法和Dijkstra(迪杰斯特拉)算法.其中Dijkstra算法是最为经典的最短路径算法，其主要特点是以起始点为中心逐层外推，直到推进至终点.Dijkstra算法能确保求出最短路径的最优解，但由于它是逐层遍历的方式导致其效率比较低，无法满足工程实际的需求[3].

为了满足效率和灵活性要求，基于人工智能的启发式搜寻法(Heuristic Search Methods)的A*算法常被应用路径搜索[4].所谓启发式是在Dijkstra算法基础上，引入启发函数(Heuristic Function)来估算当前节点与目标节点的距离，通过启发函数的……