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

第 25卷第 5期 　　　 计算机应用与软件 Vo l25 No. 5 2008年 5月 　　 Compu ter App lication s and Software M ay 2008 动态拓扑网络最短路径启发式算法 江有福 　吴伟志 (浙江海洋学院数理与信息学院　浙江 舟山 3 16004 ) 摘 　要 　　针对动态拓扑网络的最优路径规划中存在的问题 ,研究了最短路径搜索算法的快速实现技术 ,提出了一种启发式快速最 优路径规划算法 。在分析经典迪杰斯特拉最短路径搜索算法和 A 启发式搜索算法的基础上 ,利用椭圆曲线参数设定启发函数初 始值 ,进一步缩小搜索范围。采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作 ,从而提高了算法的执行效率 。仿真 试验结果表明该算法具有 良好的性能 。 关键词 　　最短路径 　A 算法 　二叉堆 　动态拓扑 A HEUR I ST I C SHO RTEST PA TH AL GO R I THM I N DY NAM I C TO POLO GY NETW O RK J iang Youfu　W u W eizh i ( Colleg e of M a ths, P hy sics and Inf orm a tion, Z hej iang O cean Un iversity, Z houshan 316004, Z hej iang, Ch ina) A b stract　　Op tim al p ath p lann ing isw idely recogn ized to be a critical issue in dynam ic topo logy network. The fast imp lem entation techno lo gy of the shorte st p ath search ing algorithm is studied, and a fast heu ristic algorithm for rou te p lann ing is p ropo sed. B ased on D ijk stra and A algorithm s, ellip se cu rve p aram eter is u sed to in itialize the in itial value of the A heuristic function, and the search ing node s are reduced. B i nary heap data structure is u sed to fu lfill the op eration of p riority queue, and the comp utational efficiency of the algorithm is imp roved. Simu lation resu lts show that the p erform ance of the algorithm is satisfactory. Keyword s　　Shortest p ath　A algorithm 　B inary heap 　Dynam ic topology 0　引　言 1　A 优化算法