《计算机应用研究》|Application Research of Computers

迷宫搜索算法的比较研究

Comparative study of algorithms for search in mazes

免费全文下载 (已被下载 次)  
获取PDF全文
作者 龚道雄,刘翔
机构 北京工业大学 电子信息与控制工程学院,北京 100124
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2011)12-4433-04
DOI 10.3969/j.issn.1001-3695.2011.12.008
摘要 研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较。在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度。通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法;同时,在实际迷宫中实现了深度优先搜索算法与A*算法的搜救应用。
关键词 搜救机器人;迷宫搜索;深度优先搜索算法;A*算法
基金项目
本文URL http://www.arocmag.com/article/1001-3695(2011)12-4433-04.html
英文标题 Comparative study of algorithms for search in mazes
作者英文名 GONG Dao-xiong, LIU Xiang
机构英文名 College of Electronic Information & Control Engineering, Beijing University of Technology, Beijing 100124, China
英文摘要 This paper mainly concentrated on studying the application of robotic searching.In this case, the accident environment was abstracted as a maze, and this paper compared the depth-first search algorithm and three A-star algorithms in application 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 difficulty 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 outperform 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.
英文关键词 search and rescue robot; maze search; the depth-first search algorithm; A-star algorithm
参考文献 查看稿件参考文献
 
收稿日期
修回日期
页码 4433-4436
中图分类号
文献标志码 A