迷宫问题课程设计报告.doc-资料库

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第1页.png

第1页 / 共21页

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第2页.png

第2页 / 共21页

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第3页.png

第3页 / 共21页

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第4页.png

第4页 / 共21页

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第5页.png

第5页 / 共21页

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第6页.png

第6页 / 共21页

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第7页.png

第7页 / 共21页

zhaoyongganghedan-4839077-课设说明书.doc.pdf-第8页.png

第8页 / 共21页

目录摘要.................................................................................... 错误！未定义书签。前言.......................................................................................................................1 正文.......................................................................................................................3 1. 采用类 C 语言定义相关的数据类型...........................................................3 2. 各模块的伪码算法.......................................................................................3 3. 搜索算法流程图...........................................................................................6 4. 调试分析.......................................................................................................7 5. 测试结果.......................................................................................................7 6. 源程序（带注释）.....................................................................................10 总结.....................................................................................................................16 参考文献.................................................................................................................17 致谢.....................................................................................................................18 附件Ⅰ 部分源程序代码...................................................................................... 19

摘要在现实生活中，会遇到很多很多关于迷宫这样很复杂、很难解决的问题的问题。如果人工去解决这些问题，会很麻烦，花很长的时间，甚至无法解决。假如用计算机去解决，可以通过手动生成迷宫，也可以通过计算机随机的产生迷宫，最终退出。而且可以很快的求解迷宫，找到从入口到出口的通路，或者当没有通路时，得出没有通路的结论。找出通路之后，会显示出通路路经，而且以图示的方式显示出通路，这样会使人一目了然的看清此迷宫的通路。迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组 maze[M+2][N+2],然后用它的前 m 行 n 列来存放元素，即可得到一个 m×n 的二维数组，这样(0,0)表示迷宫入口位置， (m-1,n-1)表示迷宫出口位置。关键词：迷宫；通路；二维数组；路径 1

前言随着社会经济的发展，信息化程度的不断深入，传统的人工求解迷宫问题已不能满足生活的需要。近几年，随着迷宫问题越来越复杂、科技也越来越发达，人们逐渐的开始用计算机求解迷宫问题。迷宫问题很复杂，但是人们又不得不去研究这个问题，因为人们的生活中需要它，离不开它。在迷宫路径的搜索过程中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为 2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。 2

正文 1. 采用类 c 语言定义相关的数据类型节点类型和指针类型迷宫矩阵类型：int maze[M+2][N+2];为方便操作使其为全局变量迷宫中节点类型及队列类型：struct point{int row,col,predecessor} que[512] 2. 各模块的伪码算法 1、迷宫的操作 (1)手动生成迷宫 void shoudong_maze(int m,int n) {定义 i,j 为循环变量 for(i<=m) for(j<=n) 输入 maze[i][j]的值 } (2)自动生成迷宫 void zidong_maze(int m,int n) {定义 i,j 为循环变量 for(i<=m) for(j<=n) maze[i][j]=rand()%2 //由于 rand()产生的随机数是从 0 到 RAND_MAX,RAND_MAX 是定义在 stdlib.h 中的,其值至少为 32767),要产生从 X 到 Y 的数,只需要这样写：k=rand()%(Y-X+1)+X; } (3)打印迷宫图形 void print_maze(int m,int n) {用 i,j 循环变量，将 maze[i][j]输出 □、■} (4)打印迷宫路径 void result_maze(int m,int n) 3

{用 i,j 循环变量，将 maze[i][j]输出 □、■、☆} (5)搜索迷宫路径 ①迷宫中队列入队操作 void enqueue(struct point p) {将 p 放入队尾，tail++} ②迷宫中队列出队操作 struct point dequeue(struct point p) {head++,返回 que[head-1]} ③判断队列是否为空 int is_empty() {返回 head==tail 的值，当队列为空时，返回 0} ④访问迷宫矩阵中节点 void visit(int row,int col,int maze[41][41]) { 建立新的队列节点 visit_point, 将其值分别赋为 row,col,head-1,maze[row][col]=2,表示该节点以被访问过;调用 enqueue(visit_point),将该节点入队} ⑤路径求解 void mgpath(int maze[41][41],int m,int n) {先定义入口节点为 struct point p={0,0,-1},从 maze[0][0]开始访问。如果入口处即为障碍，则此迷宫无解，返回 0 ，程序结束。否则访问入口节点，将入口节点标记为访问过 maze[p.row][p.col]=2,调用函数 enqueue(p)将该节点入队。判断队列是否为空，当队列不为空时，则运行以下操作： { 调用 dequeue()函数，将队头元素返回给 p，如果 p.row==m-1 且 p.col==n-1,即到达出口节点，即找到了路径，结束如果 p.col+1

通路,则 visit(p.row+1,p.col,maze),将下方节点入队标记已访问如果 p.col-1>0 且 maze[p.row][p.col-1]==0,说明未到迷宫左边界，且其左方有通路,则 visit(p.row,p.col-1,maze),将左方节点入队标记已访问如果 p.row-1>0 且 maze[p.row-1][p.col]==0,说明未到迷宫上边界，且其上方有通路,则 visit(p.row,p.col+1,maze),将上方节点入队标记已访问 } 访问到出口(找到路径)即 p.row==m-1 且 p.col==n-1,则逆序将路径标记为 3 即 maze[p.row][p.col]==3; while(p.predecessor!=-1) {p=queue[p.predecessor]; maze[p.row][p.col]==3;} 最后将路径图形打印出来。 2.菜单选择 while(cycle!=(-1)) ☆ 手动生成迷宫请按：1 ☆ 自动生成迷宫请按：2 ☆ 退出请按：3 scanf("%d",&i); switch(i) { case 1：请输入行列数(如果超出预设范围则提示重新输入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); case 2 ：请输入行列数(如果超出预设范围则提示重新输入) zidong_maze(m,n); print_maze(m,n); 5

mgpath(maze,m,n); if(X!=0) result_maze(m,n); case 3：cycle=(-1); break; } 3. 搜索算法流程图 6

4. 调试分析 a、调试中遇到的问题及对问题的解决方法在调试过程中，刚开始系统自动生成的迷宫并不是随机的，而是每次生成的都一样；求解时，不能正确的得到结果，有时还会求错；输出的路径是乱的，而不是按顺序显示。出现上述问题之后，经过和同学的探讨研究，重写随机函数、修改语句、调换语句的位置等一次一次的试验，最终问题才得以解决。在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以通过算法比较，改用此算法 b、算法的时间复杂度和空间复杂度该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比，迷宫长为 m，宽为 n，在最好情况下的时间和空间复杂度均为 O（m+n），在最差情况下均为 O（m*n），平均情况在它们之间 5. 测试结果进入系统主菜单： 7

资料库

迷宫问题课程设计报告.doc

相关推荐

课程资源

热门标签

最新资料