A~*算法在Shortest-Path方面的优化研究  被引量:4

Optimization of A~* Algorithm in Finding Shortest-Path

在线阅读下载全文

作  者:梁昭阳 蓝茂俊 陈正铭 LIANG Zhao-Yang;LAN Mao-Jun;CHEN Zheng-Ming(College of Information Science and Engineering, Shaoguan University, Shaoguan 512005, China)

机构地区:[1]韶关学院信息科学与工程学院,韶关512005

出  处:《计算机系统应用》2018年第7期255-259,共5页Computer Systems & Applications

基  金:韶关学院大学生创新创业训练计划立项项目(国家级)(201710576001);韶关学院第十六批教育教学改革研究一般项目(SYJY20151623)~~

摘  要:在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.In the field of NPC game or GIS system development,there are more studies on finding the efficient method of the shortest path search problem,especially the research of A~* algorithm efficiency optimization in the search of finding shortest path algorithm.Most of the maps used in artificial intelligence or algorithm research are based on arbitrary graphs rather than grid-based graphs.Based on above mentioned scenario,by combining arbitrary graphs with grid graphs and directions,an optimization of A^* algorithm is proposed in this study.The heuristic search strategy is improved,which can reduce the scale and range of algorithm search and improve the efficiency of A^* algorithm.Finally,the experimental results show that compared with the traditional A^* algorithm,after the optimization of A^* algorithm,the heuristic search strategy is more accurate and the computational efficiency became more efficient and more quickly.

关 键 词:启发式搜索策略 A^*算法 方向 最短路径搜索 

分 类 号:TP301.6[自动化与计算机技术—计算机系统结构]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象