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

Optimization algorithm for maze path planning and solving based on automata

作　　者：汤伟[1] 赵静[1] 古婵 TANG Wei;ZHAO Jing;GU Chan(College of Electrical and Control Engineering,Shaanxi University of Science and Technology,Xi'an 710021,China)

机构地区：[1]陕西科技大学电气与控制工程学院,陕西西安710021

出　　处：《南京邮电大学学报（自然科学版）》2021年第5期92-100,共9页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

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

摘　　要：针对迷宫在求最优路径时存在冗余点多、内存开销大的问题,文中以自动机为基础,提出了一种针对复杂大规模迷宫中的Dijkstra优化算法。首先建立能够描述迷宫行走逻辑的自动机模型,结合其结构性质删除可行路径中的冗余点,在删除后的路径中筛选关键节点进行保存,最后在简化后的模型上用Dijkstra算法计算最短路径。仿真结果表明,与传统Dijkstra算法相比,在最终所得路径一致的情况下,此算法执行命令的次数更少、遍历节点个数更少,寻找随机大规模迷宫的最优路径用时更少。Aiming at the problems of many redundant points and large memory overhead when finding the optimal path of the maze,an optimization Dijkstra algorithm based on automata in a complex large⁃scale maze is proposed.Firstly,an automaton model for describing the logic of maze walking is established.Then,its structural properties are combined to delete redundant points in the feasible path,key nodes in the deleted path for storage are selected,.Finally,the shortest path with Dijkstra algorithm on the simplified model is calculated.Simulation results show that compared with the traditional Dijkstra algorithms,when the final path is the same,the algorithm executes fewer commands,traverses fewer nodes and takes less time to find the optimal path of a random large⁃scale maze.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]