2022年深度与广度优先搜索:迷宫问题 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《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 有路径
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年深度与广度优先搜索:迷宫问题 2022 深度 广度 优先 搜索 迷宫 问题
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内