2022年深度与广度优先搜索：迷宫问题 .pdf

《2022年深度与广度优先搜索：迷宫问题 .pdf》由会员分享，可在线阅读，更多相关《2022年深度与广度优先搜索：迷宫问题 .pdf（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 数 据 结 构 课 程 设 计 报 告题目：深度与广度优先搜索-迷宫问题专业计算机科学与技术学生姓名李柏班级B 计算机 115 学号1110704512 指导教师巩 永 旺完成日期2013 年 1 月 11日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 19 页 -程序实践报告（2010）目录1 简介.12 算法说明 .13 测试结果 .34 分析与探讨 .75 小结.8附录.10附录 1 源程序清单 .10名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 19 页 -程序实践报告（2010）1 迷宫问题1 简介1、图的存储结构图的存储结构又称图的表示，其最常用的

2、方法是邻接矩阵和邻接表。无论采用什么存储方式，其目标总是相同的，既不仅要存储图中各个顶点的信息，同时还要存储顶点之间的所有关系。2、图的遍历图的遍历就是从指定的某个顶点（称其为初始点）出发，按照一定的搜索方法对图中的所有顶点各做一次访问过程。根据搜索方法不同，遍历一般分为深度优先搜索遍历和广度优先搜索遍历。本实验中用到的是广度优先搜索遍历。即首先访问初始点vi，并将其标记为已访问过，接着访问 vi的所有未被访问过的邻接点，顺序任意，并均标记为已访问过，以此类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。鉴于广度优先搜索是将所有路径同时按照顺序遍历，直到遍历出迷宫出口，生成的路径为

3、最短路径。因此我们采用了广度优先搜索。无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点。广度优先搜索采用队列作为数据结构。本实验的目的是设计一个程序，实现手动或者自动生成一个nm 矩阵的迷宫，寻找一条从入口点到出口点的通路。具体实验内容如下：选择手动或者自动生成一个nm 的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8 个方向行走。如果迷宫可以走通，则用“”代表“1”，用“”代表“0”，用“”代

4、表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，则只输出迷宫原型图。2 算法说明迷宫中存在通路和障碍，为了方便迷宫的创建，可用0 表示通路，用1 表示障碍，这样迷宫就可以用0、1 矩阵来描述。设置迷宫的长为n、宽为 m，范围为 4949，用 int mazeN+2M+2 来表示，这样相当于在迷宫外层包了一层1，即防止搜索路径时跳出迷宫。（1）手动生成迷宫名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 19 页 -程序实践报告（2010）2 void hand_maze(int m,int n)/手动生成迷宫 int i,j;for(i=0;im;i

5、+)for(j=0;jmazeij;（2）自动生成迷宫void automatic_maze(int m,int n)/自动生成迷宫 int i,j;for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2;/随机生成 0、1 maze00=0;/将开始和结束位置强制为 0，保证有可能出来迷宫mazem-1n-1=0;2、迷宫路径的搜索在生成的 0、1 矩阵迷宫中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其北（-1，0），东北（-1，1），东（0,1），东南（1,1），南（1,0），西南（1，-1），西（0，-1）

6、，西北（-1，-1）8 个方向位，是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。逆序输出路径，将已输出的路径标记为3。实验数据如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 19 页 -程序实践报告（2010）3 表 3.

7、1 方向 move 的偏移量Name dir Movedir.vert Movedir.horiz N 0-1 0 NE 1-1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1-1 W 6 0-1 NW 6 0-1 3 测试结果图 1 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 19 页 -程序实践报告（2010）4 图 2 图 3 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 19 页 -程序实践报告（2010）5 图 4 图 5 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 19 页 -程序实践报告（2010）6 图 6

8、 图 7 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 19 页 -程序实践报告（2010）7 4 分析与探讨首先明确题目中的已知条件：（1）迷宫是一个 8*8 大小的矩阵。（2）从迷宫的左上角进入，右下角为迷宫的终点。（3）mazeij=0 代表第 i+1 行第 j+1 列的点是通路；mazeij=1 代表该点是墙，无法通行。（4）迷宫有两种生成方式：手工设定和自动生成。（5）当老鼠处于迷宫中某一点的位置上，它可以向 8 个方向前进，分别是：“上、下、左、右、左上、左下、右上、右下”8 个方向。（6）要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数组 maz

9、eN+2N+2 来表示这个迷宫，其中 N 为迷宫的行、列数。当值为“0”时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫的位置在任何时候都可以由行号row 和列号 cool 表示。（7）为什么指定:mazeN+2N+2 来表示迷宫，而不是使用mazeNN 来表示迷宫？原因是当老鼠跑到了迷宫的边界点时就有可能跳出迷宫，而使用mazeN+2N+2 就可以把迷宫的外边再包一层“1”，这样就能阻止老鼠走出格。（8）老鼠在每一点都有8种方向可以走，分别是：North，NorthEast，East，SouthEast,South,SouthWest,West，NorthWest。可以用数组 mov

10、e8来表示每一个方向上的横纵坐标的偏移量，见表3.1。根据这个数组，就很容易计算出沿某个方向行走后的下一个点的坐标。方向 move 的偏移量Name dir Movedir.vert Movedir.horiz N 0-1 0 NE 1-1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1-1 W 6 0-1 NW 6 0-1 迷宫问题可以用深度优先搜索方法实现。当老鼠在迷宫中移动的时候，可能会有许多种移动选择方向。程序需要记录并用栈来保存当前点的坐标，然后任意选择一个方向进行移动。由于应用栈保存了当前通道上各点的坐标，所以当在当前各名师资料总结-精品资料欢迎下载-名师精心整

11、理-第 9 页，共 19 页 -程序实践报告（2010）8 方向上都走不通时可以返回上一个点，然后选择另一个方向前进。可定义 element结构用于存储每一步的横纵坐标和方向。typedef struct short int row;short int col;short int dir;element;Element stackMAX _STACK_SIZE;根据表 3.1 可推算出每次移动后的坐标。设当前的坐标是（row,col）,移动的方向是dir，移动后的点是next,则有next_row=row+movedir.vert;next_col=col+movedir.horiz;可 用

12、另 一 个 二维 数 组 markN+2 来 记 录 哪 些 点 已 经 被 访问 过。当 经 过 点mazerowcol 时，相应地将 markrowcol 的值从 0 置为 1。本程序支持自动生成迷宫。利用random（2）函数可随机产生0 或 1，来支持迷宫的自动生成。注意mazeNN 和 maze11一定要等于 0，因为他们分别是起点和终点。如果找到了一条走出迷宫的路径，则需要在屏幕中打印出如图3.5 所示格式的信息。这里要用到 graphics.h即 TC 中的图形库（注意：本程序是TC 上的实现，而VC+有自己的图形库，所以使用VC+编译提示错误）。针对图3.5，可使用 circl

13、e（）函数画圆，outtexttxy（）函数标记文字，并用line（）函数来划线。程序的主要函数如下：函数 void add（int*top,element item），将当前步的信息 item 压入到作为全局变量的栈 stack（栈顶为 top）中。函数 element delete（int*top），返回 stack中栈顶的元素。函数 void path（void），采用深度优先搜索算法，首先取出栈顶元素作为当前点选择一个方向前进到下一个点（如果能走得话）；然后，将下一个点压入栈，并将二维数组 mark 中对应的值改为 1，表示该点已经走到了。反复执行上面两步，当走到一个点不能再走下去了（

14、已经尝试了各个方向并失败），并且这个点不是终点，则这个点的上一个点会从栈中被跑抛出，从而“回朔”到上一点；当遇到终点时，程序结束，找到一条路径；当在程序循环过程中遇到栈为空，则说明该迷宫根本无法走到终点。5 小结为期一个星期的数据结构课程设计快结束了，这使我对深度和广度优先搜索有了更加深刻的理解和认识。我们团队负责的迷宫问题的课程设计就是充分的利用深度和广度优先搜索的有关知识，主要运用的是广度优先搜索遍历。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 19 页 -程序实践报告（2010）9（1）深度优先搜索遍历：深度优先搜索是一个递归过程。首先访问一个顶点 Vi 并将其标记为

15、已访问过，然后从Vi 的任意一个未被访问的邻接点出发进行深度优先搜索遍历。如此执行，当Vi 的所有邻接点均被访问过时，则退回到上一个顶点 Vk，从 Vk 的另一未被访问过的邻接点出发进行深度优先搜索遍历。如此执行，直到退回到初始点并且没有未被访问过的邻接点为止。（2）广度优先搜索遍历：广度优先搜索过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi 的所有未被访问过的邻接点，其访问顺序可以任意，假定依次为Vi1、Vi2，Vin，并标记为已访问过，然后按照Vi1、Vi2，Vin 的次序访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点Vi 有路径

16、相通的顶点都被访问过为 止。在 设 计 迷 宫 问 题 时 要 考 虑 使 用 二 维 数 组，在 数 组 中 我 们 选 择mazeN+2N+2 来表示迷宫，而不是用mazeNN 来表示，这样就可以避免老鼠走迷宫会出格。通过这一个星期的学习实践，我更加深层次的了解了关于数据结构的相关知识，也越来越发现自己对数据结构方面知识的欠缺，使我对自己所学得的知识有了一个深刻的理解，对于这方面的知识，我还缺少很多，纸上得来终觉浅，再强大的理论也要通过实践来证明。在今后的学习中我要多练习，做一个专业的计算机学生。名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 19 页 -程序实践报告（20

17、10）10 参考文献1 刘振安,刘燕君.C程序设计课程设计 M.北京 机械工业出版社,2004 年9月2 谭浩强.C程序设计（第三版）.清华大学出版社,2005 年7月3 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月4 李志球实用 C语言程序设计教程北京：电子工业出版社，1999 5 王立柱：C/C+与数据结构北京：清华大学出版社，2002 6 吴文虎 程序设计基础北京：清华大学出版社，2003 7 郭福顺，王晓芬，李莲治数据结构（修订本），大连理工大学出版社，1997 8 潘道才，陈一华数据结构，电子科技大学出版社，1994 名师资料总结-精品资料欢迎下载-名师精心整

18、理-第 12 页，共 19 页 -程序实践报告（2010）11 附录附录 1 源程序清单#include/库中包含system(pause)和 rand()函数#include/c 语言里的库#include using namespace std;#define N 49/定义为全局变量,这是迷宫数组的上线，可以自行修改#define M 49 int X;int mazeN+2M+2;int head=0,tail=0;/队列的头尾指针，初始值设为0 struct point/存放迷宫访问到点的队列结构体，包含列，行，序号 int row,col,predecessor;queue1200

19、;void hand_maze(int m,int n)/手动生成迷宫 int i,j;coutendl;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 19 页 -程序实践报告（2010）12 cout请按行输入迷宫，0 表示通路，1 表示障碍:endl;for(i=0;im;i+)for(j=0;jmazeij;void automatic_maze(int m,int n)/自动生成迷宫 int i,j;coutn 迷宫生成中nn;system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2;/随机生成0、1 maze

20、00=0;/将开始和结束位置强制为0，保证有可能出来迷宫mazem-1n-1=0;void data(int m,int n)/当用户输入的不是规整的m 行 n 列的迷宫，用来生成规则的数字迷宫int i,j;coutendl;cout 根据您先前设定的迷宫范围endl;coutendl;cout 我们将取所输入的前m*n 个数生成迷宫 endl;coutn 数字迷宫生成结果如下:nn;cout 迷宫入口 n;cout;for(i=0;im;i+)coutn;for(j=0;jn;j+)if(mazeij=0)cout 0;if(mazeij=1)cout 1;cout 迷宫出口 n;void

21、 print_maze(int m,int n)/打印迷宫外壳int i,j,k;coutn 字符迷宫生成结果如下:nn;cout 迷宫入口 n;cout;coutendl;cout;/生成上外壳名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 19 页 -程序实践报告（2010）13 for(k=0;kn;k+)cout;/这两个黑三角用来生成顶部外壳 for(i=0;im;i+)coutn;/生成左外壳cout;for(j=0;jn;j+)if(mazeij=0)printf();if(mazeij=1)printf();cout;/生成右外壳 coutendl;for(k=

22、0;kn;k+)cout;cout n;/生成底部外壳for(i=0;in;i+)cout;cout n;for(i=0;in;i+)cout;cout 迷宫出口 n;void result_maze(int m,int n)/这个是打印输出迷宫的星号路径 int i,j;cout 迷宫通路(用表示)如下所示：nt;for(i=0;im;i+)coutn;for(j=0;jn;j+)if(mazeij=0|mazeij=2)/2 是队列中访问过的点cout;if(mazeij=1)cout;if(mazeij=3)/3 是标记的可以走通的路径cout;void enqueue(struct p

23、oint p)/迷宫中队列入队操作 queuetail=p;tail+;/先用再加，队列尾部加1 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 19 页 -程序实践报告（2010）14 struct point dequeue()/迷宫中队列出队操作，不需要形参，因此用结构体定义 head+;return queuehead-1;int is_empty()/判断队列是否为空 return head=tail;void visit(int row,int col,int maze5151)/访问迷宫矩阵中的节点 struct point visit_point=row,col

24、,head-1;/head-1 的作用是正在访问的这个点的序号为之前的点序号mazerowcol=2;/将访问过的点位标记为2 enqueue(visit_point);/入队 int path(int maze5151,int m,int n)/路径求解 X=1;/初始值定为1 struct point p=0,0,-1;/定义入口节点if(mazep.rowp.col=1)/入口为 1 时，迷宫不可解 coutn=n;cout=0)&(p.row-1)m)&(p.col+0)=0)&(p.row-1)m)&(p.col+1)n)&(mazep.row-1p.col+1=0)visit(p.

25、row-1,p.col+1,maze);/东北if(p.row+0)m)&(p.col+1)n)&(mazep.row+0p.col+1=0)visit(p.row+0,p.col+1,maze);/东if(p.row+1)m)&(p.col+1)n)&(mazep.row+1p.col+1=0)visit(p.row+1,p.col+1,maze);/东南if(p.row+1)m)&(p.col+0)n)&(mazep.row+1p.col+0=0)visit(p.row+1,p.col+0,maze);/南名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 19 页 -程序实践

26、报告（2010）15 if(p.row+1)m)&(p.col-1)=0)&(mazep.row+1p.col-1=0)visit(p.row+1,p.col-1,maze);/西南if(p.row+0)m)&(p.col-1)=0)&(mazep.row+0p.col-1=0)visit(p.row+0,p.col-1,maze);/西if(p.row-1)=0)&(p.row-1)m)&(p.col-1)=0)&(mazep.row-1p.col-1=0)visit(p.row-1,p.col-1,maze);/西北 if(p.row=m-1&p.col=n-1)/如果当前矩阵点是出口点，

27、输出路径 coutn=n;cout 迷宫路径为：n;cout 出口 endl;cout endl;printf(%d,%d)n,p.row+1,p.col+1);cout endl;mazep.rowp.col=3;/逆序将路径标记为3 while(p.predecessor!=-1)p=queuep.predecessor;printf(%d,%d)n,p.row+1,p.col+1);cout endl;mazep.rowp.col=3;cout 入口 endl;else coutn=n;cout 此迷宫无解！nn;X=0;return 0;void main()int i,m,n,cyc

28、le=0;while(cycle!=(-1)cout*n;cout 欢迎进入迷宫求解系统n;coutendl;cout 设计者:李柏（B 计算机 115 班）n;cout*n;cout 手动生成迷宫请按：1n;名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 19 页 -程序实践报告（2010）16 cout 自动生成迷宫请按：2n;cout 退出请按：3nn;cout*n;coutn;couti;switch(i)case 1:coutm;coutn;coutn;while(m49)|(n49)coutn 抱歉，你输入的行列数超出预设范围(0-49,0-49),请重新输入：nn

29、;coutm;coutn;coutn;hand_maze(m,n);data(m,n);print_maze(m,n);path(maze,m,n);if(X!=0)result_maze(m,n);/当 X 不为 0 时，有解，调用输出路径函数coutnnPress Enter Contiue!n;getchar();while(getchar()!=n);/接受一个输入，当为回车时执行break 跳出，否则一直执行接受数据break;case 2:coutm;coutn;coutn;while(m49)|(n49)coutn 抱歉，你输入的行列数超出预设范围(0-49,0-49),请重新输

30、入：nn;coutm;coutn;coutn;automatic_maze(m,n);data(m,n);print_maze(m,n);path(maze,m,n);名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 19 页 -程序实践报告（2010）17 if(X!=0)result_maze(m,n);coutnnPress Enter Contiue!n;getchar();while(getchar()!=n);break;case 3:cycle=(-1);break;default:coutn;cout 你的输入有误!n;coutnPress Enter Contiue!n;getchar();while(getchar()!=n);break;名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 19 页 -