A Maze Routing Algorithm Based on Two Dimensional Cellular Automata
A Maze Routing Algorithm Based on Two Dimensional Cellular Automata
复制标题
一种基于二维元胞自动机的迷宫路由算法
DOI：
10.1007/11861201_65
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
M. Meybodi
中科院分区：
文献类型：
--
作者：
S. Golzari;M. Meybodi
提出了一种基于元胞自动机的迷宫布线算法。该算法的目标是找到源小区和目标小区之间的最短路径，使路径不经过障碍物。算法有两个阶段，探索和回溯。在探索阶段，波从源单元扩展，并在扩展时通过它们的单元上放置令牌。在回溯阶段，我们从目标细胞开始，跟随波到达源细胞;在这个阶段创建的路径是可取的。该算法简单，事务是局部的，并且遵循元胞自动机的性质。该算法在O（m2）时间步内找到m×m二维CA中的期望路径。
This paper propose a maze routing algorithm based on cellular automata. The aim of this algorithm is find the shortest path between the source cell and the target cell , so that the path does not pass from the obstacles. Algorithm has two phases, exploration and retrace. In exploration phase a wave is expanded from source cell and it puts token on cells which it passes via them while expanding. In the retracing phase , we start from target cell, follow the wave and arrive to source cell; the path created in this phase is desirable. Propose algorithm is simple and it’s transactions are local and follow the cellular automata properties. This algorithm find the desirable path in m×m two dimensional CA in O(m2) time step.