动态拓扑网络最短路径启发式算法  

A HEURISTIC SHORTEST PATH ALGORITHM IN DYNAMIC TOPOLOGY NETWORK

作　　者：江有福[1] 吴伟志[1] 

机构地区：[1]浙江海洋学院数理与信息学院,浙江舟山316004

出　　处：《计算机应用与软件》2008年第5期36-37,44,共3页Computer Applications and Software

基　　金：国家自然科学基金(60473136)。

摘　　要：针对动态拓扑网络的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法。在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用椭圆曲线参数设定启发函数初始值,进一步缩小搜索范围。采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率。仿真试验结果表明该算法具有良好的性能。Optimal path planning is widely recognized to be a critical issue in dynamic topology network. The fast implementation technology of the shortest path searching algorithm is studied, and a fast heuristic algorithm for route planning is proposed. Based on Dijkstra and A ^＊ algorithms, ellipse curve parameter is used to initialize the initial value of the A^＊ heuristic function, and the searching nodes are reduced. Binary heap data structure is used to fulfill the operation of priority queue, and the computational efficiency of the algorithm is improved. Simulation results show that the performance of the algorithm is satisfactory.

关 键 词：最短路径 A^＊算法 二叉堆 动态拓扑 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论] O223[自动化与计算机技术—计算机科学与技术]