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

被引：5

作者：

孙玉昕

章瑾

机构：

[1] 武汉工程大学计算机与科学学院

来源：

武汉工程大学学报 | 2013年 / 35卷 / 06期

关键词：

路径搜索; 启发式搜索算法; 排序; 二叉堆;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：50 / 54

页数：5

共 8 条

[1] 记忆运动方向的机器人避障算法 [J].