基于TdPN的迷宫问题求解

在对传统迷宫求解算法的不足进行分析的基础上,提出一种新的基于时延Petri网求迷宫通路的算法(Algo-rithm of Maze problem based on TdPN,M-TdPN)。先将迷宫中冗余点填充为墙,再将简化后的迷宫转换成时延Petri网,利用Petri网的并发性,保证运行过程中每个参与活动的托肯个体都有自己的活动轨迹,最终出口库所中每个托肯上附着的全序时间线即为迷宫中通路。算法有效地提高了迷宫中可行路径的搜索效率。仿真结果表明,对多拐点、大规模的复杂迷宫的求解效果优于回溯法。