南京邮电大学学报(自然科学版)

作者：汤　伟,赵　静,古　婵

单位：陕西科技大学 电气与控制工程学院，陕西 西安　710021陕西科技大学 电气与控制工程学院，陕西 西安　710021陕西科技大学 电气与控制工程学院，陕西 西安　710021

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

基金：国家自然科学基金(62003201)资助项目

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

来源：2021年第05期

《南京邮电大学学报(自然科学版)》期刊编辑部

查看南京邮电大学学报(自然科学版)杂志2021年第05期