基于TdPN的迷宫问题求解

摘要：

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

关键词：时延Petri网、迷宫、并发、托肯标签

所属期刊栏目：38

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

资助基金：国家自然科学基金60473030;厦门市科技计划项目3502Z20103027;华侨大学科研启动基金项目09BS514

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

页数：共4页

页码：240-242,260