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

• 作者: 孙玉昕 章瑾
• 来源期刊: 武汉工程大学学报
• 学科: 工学
• 关键词: 路径搜索 启发式搜索算法 排序 二叉堆
• 年，卷（期）: 2013,（6）
• 页码范围: 50-54
• 页数: 5页
• 分类号: TP391.9
• 字数: 2642字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-2869.2013.06.010

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	章瑾	武汉工程大学计算机与科学学院	23	56	3.0	7.0
2	孙玉昕	武汉工程大学计算机与科学学院	11	56	5.0	7.0