迷宫最短通路的反应扩散搜索

Reaction Diffusion Shortest Path-Finding of Labyrinth

本文探索迷宫最短通路的搜索方法。在传统反应扩散方法的理论基础和算法思路基础上,本文利用扩散波在反应介质中并行性、无衰减性的特点,提出将迷宫转换为用二维数组描述的数字图像、设计出通过波的并行性扩散传导与回溯法来确定迷宫最短路径的新方法。计算机模拟证明此方法的快速和有效性。

During the past few decades, many algorithms have been proposed to solve the propblem of finding the shortest path from the entrance to the exit in labyrinth. One category of the well known algorithms with lower computational complexity is based on biomolecular and biological information processing technology, among which a tecchnique called wave propagation in reaction diffusion media attracts more research attention. In this paper, the theoretical principle of some well-known traditional wave propagation in reaction diffusion media algoritms is analyzed as to discover their limitations. Base on above analysis, a novel algorithm completely based on computer programn is proposed. Acording to this algorithm, the labyrinth is regarded as a digital image represented by a 2-D array. Pixels in this image corresponding to the path are given special value representing the reaction media in which reaction wave can propagate parallelly without attenuation. The searching prcedure is based on the model of cellular automata. Another 2D array called SP picture is designed to record the time when the wave front arrives. The sortest path can be found by tacking back the SP pecture. Results of computer simulation demostate that the proposed algorthm can be effectively used to speed up the process of shortest path searching in the labyrinth.