利用堆排序优化路径搜索效率的分析

Practical analysis of improving path searching efficiency by heap sort

随着计算机技术的发展,路径搜索算法在许多领域内得到广泛的应用,对搜索时间要求提出更高的要求.为了解决这一问题采用基于人工智能的启发式搜索算法,利用网络拓扑图给出的信息动态地调整搜索方向,并利用二叉堆进行算法优化,从而达到提高搜索效率的要求.常规使用启发式搜索算法进行路径搜索计算,其时间复杂度是O(n2)(n为网络节点数量),即当面临百万节点的复杂网络拓扑时,启发式搜索算法的搜索耗时将会呈指数级快速增长,无法完全满足工程技术需求.通过理论分析与实验数据证明应用二叉堆的启发式搜索算法对于长路径,大搜索空间的搜索应用时表现出良好的时间线性,其时间复杂度是O(log n)(n为Openlist的节点数),没有出现常规启发式搜索算法应用时搜索时间爆炸式增长的情况,具有较高的性能和效率,对工程实践有一定的实用参考实用价值.

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 efficiency by using this algorithm, and has certain practical value for engineering practice.