计算机应用研究2011，Vol.28Issue(12)：4433-4436,4.DOI:10.3969/j.issn.1001-3695.2011.12.008
迷宫搜索算法的比较研究
Comparative study of algorithms for search in mazes
龚道雄 1刘翔1
作者信息
- 1. 北京工业大学电子信息与控制工程学院,北京100124
- 折叠
摘要
Abstract
This paper mainly concentrated on studying the application of robotic searching. In this case, the accident environ-ment was abstracted as a maze,and this paper compared the depth-first search algorithm and three A-star algorithms in applica-tion of Perfect maze by simulation experiment. Furthermore, it also implemented the depth-first search algorithm and the 3 heuristic functions of A-star algorithms in real maze application and compared the results. In the experiment, the environment of maze was unknown by the robot. Because an unknown maze had few collision-free path to a destination, it increased the diffi-culty to search the right path. By comparing the performances of different types of A-star algorithms and the depth-first search algorithm in simulation, experiments validate the usefulness of heuristic function with the results that the A-star algorithms out-perform the depth-first search algorithm in most cases, meanwhile, has implemented the use of the depth-first search algorithm and A-star algorithmin real maze searching.关键词
搜救机器人/迷宫搜索/深度优先搜索算法/A*算法Key words
search and rescue robot/ maze search/ the depth-first search algorithm/ A-star algorithm/分类
信息技术与安全科学引用本文复制引用
龚道雄,刘翔..迷宫搜索算法的比较研究[J].计算机应用研究,2011,28(12):4433-4436,4.
