|本期目录/Table of Contents|

[1]孙玉昕,章瑾.利用堆排序优化路径搜索效率的分析[J].武汉工程大学学报,2013,(06):50-54.[doi:103969/jissn16742869201306010]
　SUN Yu xin,ZHANG Jin.Practical analysis of improving path searching efficiency by heap sort[J].Journal of Wuhan Institute of Technology,2013,(06):50-54.[doi:103969/jissn16742869201306010]
点击复制

利用堆排序优化路径搜索效率的分析(/HTML)
分享到：

《武汉工程大学学报》[ISSN:1674-2869/CN:42-1779/TQ]

卷:
期数:
2013年06期
页码:
50-54
栏目:
机电与信息工程
出版日期:
2013-06-30

文章信息/Info

Title:
Practical analysis of improving path searching efficiency by heap sort
文章编号:
16742869(2013)06005005
作者:
孙玉昕; 章瑾
武汉工程大学计算机与科学学院，湖北 武汉 430074
Author(s):
SUN Yuxin; ZHANG Jin
School of Computer Science and Engineering, Wuhan Institute of Technology, Wuhan 430074, China
关键词:
路径搜索; 启发式搜索算法; 排序; 二叉堆
Keywords:
path search;  heuristic search methods;  sort;  binary heap
分类号:
TP391.9
DOI:
103969/jissn16742869201306010
文献标志码:
A
摘要:
随着计算机技术的发展，路径搜索算法在许多领域内得到广泛的应用，对搜索时间要求提出更高的要求.为了解决这一问题采用基于人工智能的启发式搜索算法，利用网络拓扑图给出的信息动态地调整搜索方向，并利用二叉堆进行算法优化，从而达到提高搜索效率的要求.常规使用启发式搜索算法进行路径搜索计算，其时间复杂度是O(n2)（n为网络节点数量），即当面临百万节点的复杂网络拓扑时，启发式搜索算法的搜索耗时将会呈指数级快速增长，无法完全满足工程技术需求.通过理论分析与实验数据证明应用二叉堆的启发式搜索算法对于长路径，大搜索空间的搜索应用时表现出良好的时间线性，其时间复杂度是O(log n)(n为Openlist的节点数)，没有出现常规启发式搜索算法应用时搜索时间爆炸式增长的情况，具有较高的性能和效率，对工程实践有一定的实用参考实用价值.
Abstract:
With the development of computer technology, the method of path search algorithm has been widely used in many fields, and the higher request has been put forward for the searching time. To meet the requirement, based on artificial intelligence (Heuristic Search Methods A*) ,the method of heuristic search algorithm was adopted to improve searching efficiency ,the search direction was adjusted dynamically by using network topology information and the algorithm was optimized to improve searching efficiency requirements by binary heap .Generally, the heuristic search algorithm is used for path search , its time complexity is O (n2) (n is the number of the network nodes), while dealing with the complicated network topology of millions of nodes, the searching time of heuristic search algorithm shows with exponential growth , so it does not meet the requirements of engineering technology. A good linearity of time is shown when the heuristic search algorithm of binary heap is applied for the long path and big search space through the theoretical analysis and experimental data, time complexity of this algorithm is O (log n) (n is the number of nodes Openlist). Meanwhile, there is no explosive growth in the searching time. So it meets the requirement of the higher performance and efficiency by using this algorithm, and has certain practical value for engineering practice.

参考文献/References:

［1］陈伟亚，刘芳芳.地理信息系统在水污染控制规划中的应用\[J\].武汉工程大学学报，2013，35（1）：2125.CHEN Weiya, LIU Fangfang. Applieation of geographic information system teehnology in planing of water pollution control\[J\]. Jouranal of wuhan institute of teehnology, 2013，35（1）：2125.(in Chinese)［2］柳林，张继贤，唐新明，等.LBS体系结构及关键技术的研究［J］.测绘科学,2007,32(5)： 144146.LIU Lin, ZhANG Jixian, TANG Xinming, at al. LBS architecture and Research of key technologies\[J\]. Science of Surveying and Mapping,2007,32 (5):144146 .(in Chinese)［3］顾运筠.最短路径搜索算法的几种优化改进［J］.计算机应用与软件，2008，25(4):246247.GU Yunjun. Shortest path search algorithm several optimized and improved\[J\]. Computer Applications and Software,2008,25(4): 246 247.(in Chinese)［4］刘浩，鲍远律.A*算法在矢量地图最优路径搜索中的应用［J］. 计算机仿真,2008，25(4):253257.LIU Hao, BAO Yuanlv.The application of the A* algorithm searching the optimal vector path map\[J\]. Computer Simulation, 2008,25(4): 253257.(in Chinese)［5］陈和平，张前哨.A*算法在游戏地图寻径中的应用与实现［J］.计算机应用与软件,2005，22(12):118120.CHEN Heping, Zhang Qianshao. Application and Implementation of the A* algorithm pathfinding in game maps\[J\]. Computer Applications and Software, 2005, 22(12):118120.(in Chinese)［6］史辉，曹闻，朱述龙，等.A*算法的改进及其在路径规划中的应用［J］.测绘与空间地理信息,2009，32(6): 208211.SHI Hui, CAO Wen, ZHU Shulong, et al. A* algorithm and its application in path planning\[J\]. Geomatics & Spatial Information,2009,32 (6): 208211.(in Chinese)［7］朱福喜,傅建明.人工智能原理［M］. 武汉：武汉大学出版社，2002.ZHU Fuxi, FU Jianming. Principle of artificial intelligence\[M\]. Wuhan: Wuhan University press, 2002.(in Chinese)［8］龚劬.图论与网络最优化算法［M］.重庆：重庆大学出版社，2009.GONG Qu. Graph theory and network optimization algorithms\[M\]. Chongqing: Chongqing University Press,2009.(in Chinese)［9］鲁统伟，林芹，李熹，等.记忆运动方向的机器人避障算法\[J\].武汉工程大学学报，2013，35（4）：6671.LU Tongwei, LIN Qin, LI Xi, et al. Obestacle avoidance algorithm of robot based on recording moue direction. Jouranal of Wuhan instute of technology，2013，35（4）：6671.(in Chinese)

相似文献/References:

备注/Memo

备注/Memo:
收稿日期：20130403作者简介：孙玉昕（1977），女，黑龙江大庆人，讲师，硕士.研究方向：地理信息系统.
更新日期/Last Update: 2013-07-11