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

摘要

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