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

1、算法分析与设计查找迷宫的最短路径（深度算法）计算机科学与技术12级16班2012/12/161 /12【摘要】：迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能 找到正确的路径，有的时候甚至找不到路径。类似于给定一个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 sometime

3、s 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

4、, 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 ; otherwis

5、e 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 . Ther

6、efore , 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目录 TOC o 1-5 h z 摘要

7、1关键字1 HYPERLINK l bookmark7 o Current Document Summary 1 HYPERLINK l bookmark23 o Current Document 一、问题描述3 HYPERLINK l bookmark27 o Current Document 二、算法分析3 HYPERLINK l bookmark31 o Current Document 三、设计方案31总体方案32主要设计思路3四、时间复杂度6 HYPERLINK l bookmark35 o Current Document 五、总结6 HYPERLINK l bookmark39

8、o Current Document 六、参考文献7 HYPERLINK l bookmark46 o Current Document 七、附录7一、问题描述迷宫最短路径（the shortest path of maze）问题是一个典型的搜索、遍历问题，其程序设计想在 人工智能设计、机器人设计等事务中均有应用。如图所示，一个NXM的大方块迷宫，带斜线的单元格表示墙壁（障碍）,空白的单元格表示通 道。迷宫问题可以表述为：寻找从某一个给定的起始单元格（迷宫入口）出发，经由行相邻或列相邻的通道单元格，最终 可以到达目标单元格（迷宫出口），所走过的单元格序列。行进中，只能沿上下左右四个方向前进。

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

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

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

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

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

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

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

16、aze,intm,int n)函数获取路径cout迷宫路径探索成功!n；else cout路径不存在!n;return 0;调试结果：埋戏本季豆愈和次6 清梆入困曰内召；1 1 a m k) U M 1 M U 0 0 0 0 3 119 0 3分别表示为行坐标-列坐标,方向八=1、3,3.1*皆备径探索成 珈Press any key to continueM图1-6搜索迷宫完成界面四、时间算法复杂度:O(n2)(不确定,我不太会算这个。)对相关问题的思考：这个迷宫问题的算法中，要在开始设置迷宫的大小。在探索迷宫路线的过程中，是通过不断的尝试 来得到最终的结果，由于不能对已经设定为可走路径进

17、行返回，所以在这个算法中有时候可能不能 得到走出迷宫的路径。五、总结本次设计进展比较顺利，如期完成，并且达到了预先的设计要求，完全贯彻和执行了设计的总 体方案。对于迷宫求解的模拟实现比较成功。然而，限于时间和水平，这个设计还有很多的不足之 处。迷宫问题是一个古老的问题，要在迷宫中找到出口，需要经过一连串的的错误尝试才能找到正 确的路径，有时甚至找不到路径。而且这里有很多方法可以完成迷宫问题，例如顺序表，深度优先 遍历，广度优先遍历等，但是我写不出程序。于是参考了数据结构书和我以前的一些设计，所 以我们这里用的是栈。在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为 空，入栈操作

18、，出栈操作等等。通过这次的作业，我又学会了一种解决迷宫问题的方法，我很高兴。当让在完成设计过程中， 我也遇到了很多难题，比如用什么办法解决问题，怎样创建调用栈等等，但在再次复习了当时所学 的C+，数据结构等课程后，发现这些问题还是可以解决的，而且解决的方法不止一种。在 这里我参考的最多的是数据结构中“栈的应用”那一节的知识，它给我了很大帮助。本程序虽然简短，但是却有很多难点出现。首先是对基类的调试。为了减少调试的难度，我先调试 了一下类的程序。刚开始是在主函数里面直接对程序赋值，发现这将大大限制程序的可重用性，而 且无法灵活运用。在指导老师的帮助下，我将程序改成用键盘直接输出，这样的话方便实现

19、。当然，在我遇到苦难时候，老师和同学的帮助也是很大的。他们使我进步。也让我体会到了成功的 来之不易，只有真正付出过才有满意的收获。在此，我诚心的对所有帮助过我的老师、学长、同学 们说一句：谢谢！六、参考文献严蔚敏，吴伟民.数据结构M.北京：清华大学出版社,2002.陈媛.算法与数据结构M.北京：清华大学出版社,2005.苏德富.计算机算法设计与分析M.北京：电子工业出版社,2005.七、附录:#includeusing namespace std;定义描述迷宫中当前位置的结构类型class T ,public:int x;int y;int dir;class LinkNode friend

20、class Stack;public:T data;LinkNode *next;class Stack public:Stack();Stack();void Push(T e);T Pop();T GetPop();bool empty();private:LinkNode *top;Stack:Stack()top=NULL;Stack:Stack()void Stack:Push(T e) LinkNode *P;P=new LinkNode;P-data=e;P-next=top;top=P;T Stack:Pop()T Temp;LinkNode *P;P=top; top=top

21、-next;/x代表当前位置的行坐标/y代表当前位置的列坐标/0：无效,1：右,2:下,3:左,4:上链表结点构造函数，置空栈/析构函数把元素data压入栈中/使栈顶元素出栈取出栈顶元素判断栈是否为空，如果为空则返回1，否则返回0指向第一个结点的栈顶指针构造函数，置空栈析构函数把元素x压入栈中使栈顶元素出栈Temp=P-data;delete P;return Temp;T Stack:GetPop()取出栈顶元素return top-data;bool Stack:empty()判断栈是否为空，如果为空则返回1,否则返回0if(top=NULL) return 1;else return 0

22、;int move42=0,1,1,0,0,-1,-1,0;定义当前位置移动的 4 个方向boolMazepath(int *maze,intm,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(Mazepath(maze

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

24、;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；boolMazepath（int*maze,intm,intn）/寻找迷宫 maze 中从（0，0）到（m,n）的路径到则返回true，否则返回falseStack q,p;T Temp1,Temp2; intx,y,loop;Temp1.x=1;Temp1.y=1;q.Push(Temp1);p.Push(Temp1)

25、;maze11=-1;while(!q.empty()Temp2=q.GetPop();定义栈p、q,分别存探索迷宫的过程和存储路径将入口位置入栈标志入口位置已到达过栈q非空，则反复探索获取栈顶元素if(!(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y)p.Push(Temp2);/如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0;loop4;loop+)x=Temp2.x+moveloop0;y=Temp2.y+moveloop1;if(mazexy=0)Temp1.x=x;Temp1.y=y;mazexy=-1;q.Push(Temp1);探索当前位置的4个相邻位置计算出新位置x位置值计算出新位置y位置值判断新位置是否可达标志新位置已到达过新位置入栈if(x=(m)&(y=(n)成功到达出口Temp1.x=m;Temp1.y=n;Temp1.dir=0;p.Push(Temp1)