二叉树路径规划算法在栅格地图中的应用

论文摘要

基于栅格图的路径规划算法主要有A~*算法、快速搜索树算法等。在栅格地图规模增大的时候,以上算法的运算量将大幅增加。笔者提出一种将图搜索与栅格搜索结合的二叉树路径规划算法。该算法通过逆向搜索优化局部路径、剪枝优化二叉树,从而得到最佳路径。相比快速搜索树算法,二叉树路径规划算法具有概率完备性,在运行测试试验中,实际展开结点数量为A~*算法的28%,运行时间仅为A~*算法的52%。

论文目录

• 1 路径规划算法
•   1.1 搜索方法
•   1.2 逆向搜索优化路径
•   1.3 生成二叉树
•   1.4 剪枝应用于二叉树
• 2 运行效率分析
•   2.1 时间复杂度计算
•   2.2 运行时间测试
• 3 结语

文章来源

类型: 期刊论文

作者: 娄安东,李向阳,阮佳琪,潘瑾瑜,冯静

关键词: 栅格地图,机器人,二叉树,路径规划,算法

来源: 矿山机械 2019年10期

年度: 2019

分类: 工程科技Ⅰ辑,基础科学,信息科技

专业: 数学,自动化技术

单位: 中信重工机械股份有限公司

分类号: TP242;O221

DOI: 10.16816/j.cnki.ksjx.2019.10.015

页码: 67-71

总页数: 5

文件大小: 1730K

下载量: 182