深度与广度优先搜索：迷宫问题.doc

《深度与广度优先搜索：迷宫问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构课程设计》报告题目：深度与广度优先搜索--迷宫问题专业计算机科学与技术学生姓名李柏班级B计算机115学号指导教师巩永旺完成日期2013年1月11日目录1简介12算法说明13测试结果34分析与探讨65小结8附录10附录1源程序清单10迷宫问题1简介1、图的存储结构图的存储结构又称图的表示，其最常用的方法是邻接矩阵和邻接表。无论采用什么存储方式，其目标总是相同的，既不仅要存储图中各个顶点的信息，同时还要存储顶点之间的所有关系。2、图的遍历图的遍历就是从指定的某个顶点（称其为初始点）出发，按照一定的搜索方法对图中的所有顶点各做一次访问过程。

2、根据搜索方法不同，遍历一般分为深度优先搜索遍历和广度优先搜索遍历。本实验中用到的是广度优先搜索遍历。即首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点，顺序任意，并均标记为已访问过，以此类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。鉴于广度优先搜索是将所有路径同时按照顺序遍历，直到遍历出迷宫出口，生成的路径为最短路径。因此我们采用了广度优先搜索。无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点。广度优先搜索采用队列作为数据结

3、构。本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。具体实验内容如下：选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“☆”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，则只输出迷宫原型图。2算法说明迷宫中存在通路和障碍，为了方便

4、迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。设置迷宫的长为n、宽为m，范围为49×49，用intmaze[N+2][M+2]来表示，这样相当于在迷宫外层包了一层1，即防止搜索路径时跳出迷宫。（1）手动生成迷宫voidhand_maze(intm,intn)//手动生成迷宫{inti,j;for(i=0;i>maze[i][j];}}（2）自动生成迷宫voidautomatic_maze(intm,intn)//自动生成迷宫{inti,j;for(i=0;i<

5、m;i++)for(j=0;j

6、索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。逆序输出路径，将已输出的路径标记为3。实验数据如下：表3.1方向move的偏移量NamedirMove[dir].vertMove[dir].horizN0-10NE1-11E201SE311S410SW5

7、1-1W60-1NW60-13测试结果图1图2图3图4图5图6图74分析与探讨首先明确题目中的已知条件：（1）迷宫是一个8*8大小的矩阵。（2）从迷宫的左上角进入，右下角为迷宫的终点。（3）maze[i][j]=0代表第i+1行第j+1列的点是通路；maze[i][j]=1代表该点是墙，无法通行。（4）迷宫有两种生成方式：手工设定和自动生成。（5）当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、下、左、右、左上、左下、右上、右下”8个方向。（6）要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数组maze[N

8、+2][N+2]来表示这个迷宫，其中N为迷宫的行、列数。当值为“0”时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫的位置在任何时候都可以由行