基于TdPN的迷宫问题求解

计算机科学 ›› 2011, Vol. 38 ›› Issue (7): 240-242.

基于TdPN的迷宫问题求解

叶剑虹，叶双，宋文，孙世新

(华侨大学计算机科学与技术学院泉州362021)　(西华大学数学与计算机学院成都610039)　(电子科技大学计算机科学与工程学院成都610054)

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(60473030),厦门市科技计划项目(3502220103027)，华侨大学科研启动基金项目(09BS514)资助。

Maze Problem's Solution Based on Timed Petri-net

YE Jian-hong,YE Shuang,SONG Wen,SUN Shi-xin

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

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

关键词: 时延Petri网，迷宫，并发，托肯标签

Abstract: M-TdPN, an improved search algorithm, was presented in this paper in view of the shortage of traditional solutions of maze problem. Redundancy points were eliminated to reduce the space complexity. The timed Petri net was applied to simulate the maze. Using the concurrency, every token has its own traces. The flags attached on tokens in the end place arc the feasible paths of maze problem. hhe searching efficiency is improved effectively. Results of experimental showed that the M-TdPN algorithm has better search results in case of more complicated maze or more impasse vertexes specially.

Key words: Limed petri nets, Maze problem, Concurrency, Token flag

叶剑虹，叶双，宋文，孙世新. 基于TdPN的迷宫问题求解[J]. 计算机科学, 2011, 38(7): 240-242. https://doi.org/

YE Jian-hong,YE Shuang,SONG Wen,SUN Shi-xin. Maze Problem's Solution Based on Timed Petri-net[J]. Computer Science, 2011, 38(7): 240-242. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed