注水法求解迷宫最优路径

Using Watering Algorithm to Find the Optimal Paths of a Maze

根据灌溉系统的工作原理,提出注水法算法应用于求解迷宫最优路径问题。设定迷宫为一个灌溉系统,水从迷宫的入口注入,通过迷宫的通路水从迷宫的出口流出。从入口注入的水沿通路流向各个方向,在通路的各个位置记忆水流到达的时间。当迷宫出口有水流到达时,从出口到入口根据记录在通路上的时间逐步减小的原则逆向寻找入口就可找到迷宫的所有最优路径。该算法的空间复杂度和时间复杂度同迷宫的规模成线性关系。实验结果显示该算法是一种求解迷宫问题的有效算法。

According to the principle of watering systems, a watering algorithm is proposed and applied to find the optimal paths of a maze in this paper. Assuming that a maze is a watering system, water fills the maze from the entrance and flows out from the outlet through passages of the maze. Water filled from the entrance spreads to each direction along the passages and the passing time of water is recorded at every spot in the maze. When water arrives at the outlet, all of the optimal paths will be found according to the recorded time based on the principle that the less time cost stems from the short path. The spatial complexity and the time complexity of the algorithm are linear with the size of a maze. The experimental results show that the watering algorithm is an efficient way to solve maze problems.