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

1、算法分析与设计查找迷宫的最短路径(深度算法)计算机科学与技术12级16班 2012/12/16 【摘要】：迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置

2、上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。【关键词】: 最短路径; 时间复杂度;深度优先搜索【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 ev

3、en 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 t

4、he 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

5、 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 ,

6、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二、

7、算法分析3三、设计方案31总体方案32主要设计思路3四、时间复杂度6五、总结6六、参考文献7七、附录7一、 问题描述迷宫最短路径( the shortest path of maze) 问题是一个典型的搜索、遍历问题, 其程序设计想在人工智能设计、机器人设计等事务中均有应用。如图 所示, 一个NM的大方块迷宫, 带斜线的单元格表示墙壁( 障碍) , 空白的单元格表示通道。迷宫问题可以表述为:寻找从某一个给定的起始单元格( 迷宫入口) 出发, 经由行相邻或列相邻的通道单元格, 最终可以到达目标单元格( 迷宫出口) , 所走过的单元格序列。行进中, 只能沿上下左右四个方向前进。而迷宫最短路径问题就

8、是找出从迷宫入口到出口所经过单元格个数最少的路径。二、 算法分析从入口出发, 顺着某一方向向前探索, 若能走通, 则继续往前走; 否则沿原路退回( 回溯) , 换一个方向再继续探索, 直至所有可能的通路都探索到为止。如果恰好某一步探索到出口, 则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回, 防止死循环, 需要使用堆栈来保存大量记录。而要求解迷宫最短路径, 则必须用深度优先搜索出所有到达出口的路径, 通过比较得到最短距离的路径, 这样也必然要求增加数据空间来保存搜索过程中当前最短路径, 增加了空间复杂度。三、 设计方案1总体方案 走迷宫问题的走迷宫的过程可以模拟为一个搜索的过

9、程：每到一处，总让它按东、南、西、北、4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。2主要设计思路用一个字符类型的二维数组表示迷宫，输入值的范围是0，1，其中0表示路径，1为非路径(即障碍)，输入的矩阵大小和矩阵的内容是靠手动输入。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。解决迷宫问题，面对的第一个问题是迷宫的表示方法。假定用n*m矩阵来描

10、述迷宫。左上角为入口，右下角为出口。n和m分别表示迷宫的行数和列数。矩阵中，0表示可通行的路径，1代表障碍。如图1-1表示4*6的迷宫矩阵表示。011000000100 000000011000图1-1 迷宫问题的矩阵表示如果现在的位置（i,j）,则下一步有：上、下、左、右四种走法，如图1-2表示。(i-1,j)(i,j-1)（i,j）(i,j+1)(i+1,j)图1-2 四种可能的移动方向迷宫内部的位置有四种移动的位置：上、下、左、右。而迷宫的边界位置有两种或三种可能的移动。为避免在处理内部和边界位置是存在差异，可在迷宫的周围增加一圈障碍物，如图1-3表示。11111111101100011

11、0001001100000011011000111111111图1-3 为迷宫增加一圈障碍物增加一圈障碍物之后，原迷宫中的每个位置都可以有四种移动方向。而且可以使程序不必去处理边界条件，从而大大简化代码的设计。这种简化是以稍稍增加数组amze的空间为代价的。分别用x和y来指定每个迷宫位置的行坐标和列坐标。可以定义一个类class T来表示迷宫的位置。class T /定义描述迷宫中当前位置的结构类型public: int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int dir; /0:无效,1:右,2:下,3:左,4:上;当输入一个二维数组时，每次输入的元素都存

12、放在一个栈里面。所以定义一个栈Stack用于存放二维数组元素。这里用到栈，栈是限定尽在表位进行插入和删除的线性表。对于栈来说，允许进行插入和删除的一段，称为栈顶；不允许插入和删除的另一端，则成为栈底。在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。这里是栈的一个重要应用，就是实现递归。 class Stack public: Stack(); /构造函数，置空栈 Stack(); /析构函数 void Push(T e); /把元素data压入栈中 T Pop(); /使栈顶元素出栈 T GetPop(); /取出栈顶元素 void Clear()

13、; /把栈清空 bool empty(); /判断栈是否为空，如果为空则返回1，否则返回0private: LinkNode *top; ; /指向第一个结点的栈顶指针调试结果如图1-4：图1-4 迷宫和矩阵的建立如果位置（i,j）的下一步的四个方向都是可以走的，假设出发的先后顺序是向上.向下.向左.向右。每个结点都是按照先后顺序来决定下一个结点的方向。一旦做出了决定，就需要知道下一个位置的坐标。可通过保留一个如图1-5所示的偏移量表来计算这些坐标。可以把向右.向左.向下.向上移动分别编号为0.1.2.3。在图1-3中，movei.x和movei.y分别给出了从当前位置沿方向移动到下一个相连位

14、置时，x和y坐标的增量。方向索引值（dir）movedir.xmovedir.x方向001右110下20-1左3-10上图1-5 偏移量表因此假设现在的位置是（2，3），则其右边相连位置坐标的行坐标为2+move0.x=2,列坐标为3+move0.y=4.定义一个主函数int main()，用于调用其他函数实现函数的嵌套调用，实现整个程序。这里运用的二维指针我是参考书上的。int main() int m=0,n=0; /定义迷宫的长和宽 int *maze; /定义二维指针存取迷宫maze=GetMaze(m,n); /调用GetMaze(int &m,int &n)函数，得到迷宫 if(M

15、azepath(maze,m,n) /调用Mazepath(int *maze,int m,int n)函数获取路径 cout迷宫路径探索成功!n; else cout路径不存在!n; return 0;调试结果：图1-6 搜索迷宫完成界面四、 时间算法复杂度：O(n）（不确定,我不太会算这个。）对相关问题的思考：这个迷宫问题的算法中，要在开始设置迷宫的大小。在探索迷宫路线的过程中，是通过不断的尝试来得到最终的结果，由于不能对已经设定为可走路径进行返回，所以在这个算法中有时候可能不能得到走出迷宫的路径。五、 总结本次设计进展比较顺利，如期完成，并且达到了预先的设计要求，完全贯彻和执行了设计的总

16、体方案。对于迷宫求解的模拟实现比较成功。然而，限于时间和水平，这个设计还有很多的不足之处。迷宫问题是一个古老的问题，要在迷宫中找到出口，需要经过一连串的的错误尝试才能找到正确的路径，有时甚至找不到路径。而且这里有很多方法可以完成迷宫问题，例如顺序表，深度优先遍历，广度优先遍历等，但是我写不出程序。于是参考了数据结构书和我以前的一些设计，所以我们这里用的是栈。在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。通过这次的作业，我又学会了一种解决迷宫问题的方法，我很高兴。当让在完成设计过程中，我也遇到了很多难题，比如用什么办法解决问题，怎样创建调用栈等等，

17、但在再次复习了当时所学的C+,数据结构等课程后，发现这些问题还是可以解决的，而且解决的方法不止一种。在这里我参考的最多的是数据结构中“栈的应用”那一节的知识，它给我了很大帮助。本程序虽然简短，但是却有很多难点出现。首先是对基类的调试。为了减少调试的难度，我先调试了一下类的程序。刚开始是在主函数里面直接对程序赋值，发现这将大大限制程序的可重用性，而且无法灵活运用。在指导老师的帮助下，我将程序改成用键盘直接输出，这样的话方便实现。当然，在我遇到苦难时候，老师和同学的帮助也是很大的。他们使我进步。也让我体会到了成功的来之不易，只有真正付出过才有满意的收获。在此，我诚心的对所有帮助过我的老师、学长、同

18、学们说一句：谢谢！ 六、 参考文献1 严蔚敏, 吴伟民.数据结构M.北京: 清华大学出版社, 2002.2 陈媛.算法与数据结构M.北京: 清华大学出版社, 2005.3 苏德富.计算机算法设计与分析M.北京: 电子工业出版社, 2005.七、 附录：#includeusing namespace std;class T /定义描述迷宫中当前位置的结构类型public: int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int dir; /0:无效,1:右,2:下,3:左,4:上;class LinkNode /链表结点 friend class Stack;pu

19、blic: T data; LinkNode *next;class Stack public: Stack(); /构造函数，置空栈 Stack(); /析构函数 void Push(T e); /把元素data压入栈中 T Pop(); /使栈顶元素出栈 T GetPop(); /取出栈顶元素 bool empty(); /判断栈是否为空，如果为空则返回1，否则返回0private: LinkNode *top; /指向第一个结点的栈顶指针;Stack:Stack() /构造函数，置空栈 top=NULL;Stack:Stack() /析构函数void Stack:Push(T e) /把

20、元素x压入栈中 LinkNode *P; P=new LinkNode; P-data=e; P-next=top; top=P;T Stack:Pop() /使栈顶元素出栈 T Temp; LinkNode *P; P=top; top=top-next; Temp=P-data; delete P; return Temp;T Stack:GetPop() /取出栈顶元素 return top-data;bool Stack:empty() /判断栈是否为空，如果为空则返回1，否则返回0 if(top=NULL) return 1; else return 0;int move42=0,1

21、,1,0,0,-1,-1,0; /定义当前位置移动的4个方向bool Mazepath(int *maze,int m,int n); /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsevoid PrintPath(Stack p); /输出迷宫的路径int* GetMaze(int &m,int &n); /获取迷宫 /返回存取迷宫的二维指针int main() int m=0,n=0; /定义迷宫的长和宽 int *maze; maze=GetMaze(m,n); /调用GetMaze(int &m,int &n)函数，得到迷宫 if(Mazepat

22、h(maze,m,n) /调用Mazepath(int *maze,int m,int n)函数获取路径 cout迷宫路径探索成功!n; else cout路径不存在!n; return 0;int* GetMaze(int &m,int &n)/返回存取迷宫的二维指针 int *maze; /定义二维指针存取迷宫 int i=0,j=0; coutab; /输入迷宫的长和宽 cout请输入迷宫内容:n; m=a; n=b; /m,n分别代表迷宫的行数和列数 maze=new int *m+2; /申请长度等于行数加2的二级指针 for(i= 0;im+2;i+) /申请每个二维指针的空间 m

23、azei=new intn+2; for(i=1;i=m;i+) /输入迷宫的内容，1代表不通，0代表可通 for(j=1;jmazeij; for(i=0;im+2;i+) mazei0=mazein+1=1; for(i=0;in+2;i+) maze0i=mazem+1i=1; return maze; /返回存贮迷宫的二维指针maze;bool Mazepath(int *maze,int m,int n)/寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回false Stack q,p; /定义栈p、q,分别存探索迷宫的过程和存储路径 T Temp1,Te

24、mp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /将入口位置入栈 p.Push(Temp1); maze11=-1; /标志入口位置已到达过 while(!q.empty() /栈q非空，则反复探索 Temp2=q.GetPop(); /获取栈顶元素 if(!(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop4;loop+) /探索当前位置的4个相邻位置 x=Temp2.x+moveloop0; /计算出新位置x位置值 y=Temp2.y+moveloop1; /计算出新位置y位置值 if(mazexy=0) /判断新位置是否可达 Temp1.x=x; Temp1.y=y; mazexy=-1; /标志新位置已到达过 q.Push(Temp1); /新位置入栈 if(x=(m)&(y=(n) /成功到达出口 Temp1.x=m; Temp1.y=n; Temp1.dir=0; p.Push(Temp1); /把最后一个位置入栈 PrintPath(p); /输出路径 return true; /表示成功找到路径 if(p.