算法分析和设计 查找迷宫的最短路径(深度算法).docx

算法分析与设计查找迷宫的最短路径(深度算法)计算机科学与技术12级16班2012/12/16【摘要】：迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。【关键词】:最短路径; 时间复杂度;深度优先搜索【Summary】Maze solving is an ancient game , you want to find the exit in the maze , need to go through a series of trial and error to find the right path , and sometimes not even find the path . A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain grid , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forward to explore a direction , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure to save the path from the entrance to the current position . Therefore , in seeking labyrinth path algorithm application stack is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal .【Key phrase】Shortest path ; time complexity ; deep-first search目录摘要1关键字1Summary1一、问题描述3二、算法分析3三、设计方案31总体方案32主要设计思路3四、时间复杂度6五、总结6六、参考文献7七、附录7问题描述迷宫最短路径( the shortest path of maze) 问题是一个典型的搜索、遍历问题, 其程序设计想在人工智能设计、机器人设计等事务中均有应用。如图所示, 一个N×M的大方块迷宫, 带斜线的单元格表示墙壁( 障碍) , 空白的单元格表示通道。迷宫问题可以表述为:寻找从某一个给定的