算法分析與设计查找迷宫的最短路径(广度算法).docVIP

算法分析与设计 查找迷宫的最短路径(广度算法) 计算机科学与技术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 ; breadth-first search  目 录 摘要 1 关键字… 1 一、问题描述 3 二、算法 3 1深度优先有哪些信誉好的足球投注网站 3 2广度优先有哪些信誉好的足球投注网站 3 三、参考代码 4 四、编程调试方面 5 五、小结 5 六、参考文献 5