迷宫问题求解.doc

数据结构实验——迷宫问题求解实验内容:利用队的结构实现迷宫求解问题。测试算法的迷宫如下图所示:要求输入起始点的坐标,输出走出迷宫最短路径的长度。实验目的:通过实验,掌握以下内容:进一步掌握指针、模板类、异常处理的使用;掌握队列的操作的实现方法;学习使用队列解决实际问题的能力;学习使用图的广度优先搜索解决实际问题的能力等。实验要求:为了更好的理解所讲的概念与原理,实验前要认真预习所做的实验内容及编写源程序伪码(写在纸上及盘中均可)以便在实验课中完成老师所布置的实验内容。概要设计原理:1、存储结构:队列顺序存储结构示意图如下:2、关键算法分析:核心算法思想:如果采用直接递归的方式,用栈很容易实现路径的输出,但是这条路径不一定是最短路径。为了改进算法,达到输出最短路径的目标,采用队列的实现方式。为查找最短路径,使用了“图”中的算法:广度优先搜索。关键算法思想描述和实现:关键算法1:为寻求最短路径,采用广度优先搜索算法,使用队列实现路径存储,队列中每个元素用结构体存储系,包含迷宫坐标、队列中的序号、父节点的序号,实现了对路径的记录:structNode { int parent_id; //保存父节点的位置 int node_id; //当前节点的序号,以便传递给孩子节点 int x,y; //当前结点对应的坐标 }Q[10*10];//每个节点包含迷宫坐标、队列中的序号、父节点的序号,多个节点形成队列关键算法2:遍历每个位置四周的位置,将没有走过的位置入队,形成树形的队列,通过出队操作就能找到最短路径。C++实现:boolGetNextPos(int*i,int*j,intcount){switch(count){case1:(*j)++;return1;//右case2:(*i)++;return1;//下case3:(*j)--;return1;//左case4:(*i)--;return1;//上default:return0;}}voidEnQueue(inti,intj,intk){ Q[rear].x=i; Q[rear].y=j; //保存当前节点对应的坐标位置 Q[rear].parent_id=k; //保存父节点的序号 Q[rear].node_id=rear; //保存当前节点序号 rear++;}关键算法3:广度优先搜索算法的实现,找到最短路径。广度优先算法在此相当于树的层序遍历,如下图:在迷宫地图中,关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队,形成类似上图的树形结构,之后广度搜索到最浅深度即为最短路径。例如H节点的坐标就是出口坐标,当层序搜索到H时就终止了,入队工作结束,不再将I和J入队。通过关键算法四逆序就能找到最短路径A->B->C。其实最短路径不一定只有一条,例如J点也可能是出口坐标,但是当搜索到H时就停止了,故此算法只是输出了所有最短路径中可能的一条。voidShortestPath_BFS(inti,intj){ intcount,m,n,k; EnQueue(i,j,-1); Map[1][1]=1; //起点入队,标记起点已走过 while(true) { count=1; DeQueue(&i,&j,&k); n=i,m=j; //保存当前位置 while(GetNextPos(&i,&j,count)) { count++; if(!Map[i][j]) { EnQueue(i,j,k); Map[i][j]=1; if(i==8&&j==9)return; //到达终点,(8,9)是默认终点,可以任意修改} i=n;j=m; //保证遍历当前坐标的所有相邻位置} }}关键算法4:使用队列指针查找父节点的方式,从队尾回溯到队首,标记出最短路径。队列的元素示意图如下:入队之后的队列如下图:563774713…………例如从13号节点可以读出它在迷宫地图中的坐标(7,4),通过第三个元素7就能找到第七号节点,也即其父节点(5,6),从父节点又可以同理找到它的父节点第三号节点。这样就能实现逆序找到路径。k=rear-1; while(k!=-1) { i=Q[k].x; j=Q[k].y; Map[i][j]=2; k=Q[k].parent_id; } 时间复杂度与空间复杂度:算法一和二时间复杂度与空间复杂度均为O(1)。算法三占用空间为迷宫边长n的平方,故空间复杂度为O(n*n)。最多走n*n步,最少走1步,故时间复杂度为O(n*n/2)。源代码:#include<iostream>usingnamespacestd; void EnQueue(inti,intj,intk);//入队一个节点 void DeQueue(int*i,int*j,int*k);//获取当前节点的