基于自动机的迷宫路径规划求解算法优化

摘要：

针对迷宫在求最优路径时存在冗余点多、内存开销大的问题,文中以自动机为基础,提出了一种针对复杂大规模迷宫中的Dijkstra优化算法.首先建立能够描述迷宫行走逻辑的自动机模型,结合其结构性质删除可行路径中的冗余点,在删除后的路径中筛选关键节点进行保存,最后在简化后的模型上用Dijkstra算法计算最短路径.仿真结果表明,与传统Dijkstra算法相比,在最终所得路径一致的情况下,此算法执行命令的次数更少、遍历节点个数更少,寻找随机大规模迷宫的最优路径用时更少.

关键词：迷宫问题;最优路径;自动机;冗余点的删除;节点优化

所属期刊栏目：41

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金62003201

在线出版日期：2021-12-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：92-100