迷宫问题求解.doc

数据结构实验迷宫问题求解一、 实验内容： 利用队的结构实现迷宫求解问题。测试算法的迷宫如下图所示： 要求输入起始点的坐标，输出走出迷宫最短路径的长度。二、 实验目的：通过实验，掌握以下内容：进一步掌握指针、模板类、异常处理的使用；掌握队列的操作的实现方法；学习使用队列解决实际问题的能力；学习使用图的广度优先搜索解决实际问题的能力等。三、 实验要求：为了更好的理解所讲的概念与原理，实验前要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。四、 概要设计原理：1、存储结构: 队列顺序存储结构示意图如下: 2、关键算法分析：核心算法思想：1. 如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。2. 为查找最短路径，使用了“图”中的算法：广度优先搜索。关键算法思想描述和实现：关键算法1：为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录：struct Nodeintparent_id;/保存父节点的位置intnode_id;/当前节点的序号，以便传递给孩子节点int x,y; /当前结点对应的坐标Q10*10; /每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列关键算法2：遍历每个位置四周的位置，将没有走过的位置入队，形成树形的队列，通过出队操作就能找到最短路径。C+实现：bool GetNextPos(int *i ,int *j,int count) switch(count) case 1:(*j)+; return 1; /右 case 2:(*i)+; return 1; /下 case 3:(*j)-; return 1; /左 case 4:(*i)-; return 1; /上 default: return 0; void EnQueue(int i,int j,int k)Qrear.x = i;Qrear.y = j;/保存当前节点对应的坐标位置Qrear.parent_id = k;/保存父节点的序号Qrear.node_id = rear; /保存当前节点序号rear+;关键算法3：广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：在迷宫地图中，关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到最浅深度即为最短路径。例如H节点的坐标就是出口坐标，当层序搜索到H时就终止了，入队工作结束，不再将I和J入队。通过关键算法四逆序就能找到最短路径A-B-C。其实最短路径不一定只有一条，例如J点也可能是出口坐标，但是当搜索到H时就停止了，故此算法只是输出了所有最短路径中可能的一条。void ShortestPath_BFS(int i ,int j)int count,m,n,k;EnQueue(i,j,-1);Map11 = 1;/起点入队,标记起点已走过while(true)count = 1;DeQueue(&i,&j,&k);n = i,m = j; /保存当前位置while(GetNextPos(&i,&j,count)count+;if(!Mapij) EnQueue(i,j,k);Mapij = 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 = Qk.x;j = Qk.y;Mapij = 2;k = Qk.parent_id;时间复杂度与空间复杂度：算法一和二时间复杂度与空间复杂度均为O(1)。算法三占用空间为迷宫边长n的平方，故空间复杂度为O(n*n)。最多走n*n步,最少走1步，故时间复杂度为O(n*n/2)。五、 源代码： #includeusing namespace std;voidEnQueue(int i,int j,int k); /入队一个节点voidDeQueue(int *i,int *j,int *k); /获取当前节点的序号和对应的迷宫坐标，然后出列boolGetNextPos(int *i ,int *j,int count); /得到下一个邻接点的位置voidShortestPath_BFS(int i,int j); /广度优先遍历寻找最短路径voidShortestPath(); /输出最短路径 voidPrint(); /输出迷宫形状 int Map1010 = 1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1;struct Nodeintparent_id;/保存父节点的位置intnode_id;/当前节点的序号，以便传递给孩子节点int x,y;/当前结点对应的坐标Q10*10;/每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列 int front = 0,rear = 0;/队列头指针和尾指针void main()cout程序说明：n1.输出路径为最短路径；n2.默认的出口在最右下角，如有需要可以调整。nn;cout初始地图如下：endl; Print();inti,j;reinput:cout请输入起点坐标（x,y）： ij;if(Mapij) cout不能从该处出发，请重新输入！endl;goto reinput; ShortestPath_BFS(i,j);cout最短路径之一如下：endl;ShortestPath();void EnQueue(int i,int j,int k)Qrear.x = i;Qrear.y = j;/保存当前节点对应的坐标位置Qrear.parent_id = k;/保存父节点的序号Qrear.node_id = rear; /保存当前节点序号rear+;void DeQueue(int *i,int *j,int *k)*i = Qfront.x;*j = Qfront.y;*k = Qfront.node_id;front+;/出列一个节点bool GetNextPos(int *i ,int *j,int count) switch(count) case 1:(*j)+; return 1; /右 case 2:(*i)+; return 1; /下 case 3:(*j)-; return 1; /左 case 4:(*i)-; return 1; /上 default: return 0; void ShortestPath_BFS(int i ,int j)int count,m,n,k;EnQueue(i,j,-1);Map11 = 1;/起点入队,标记起点已走过while(true)count = 1;DeQueue(&i,&j,&k);n = i,m = j; /保存当前位置while(GetNextPos(&i,&j,count)count+;if(!Mapij) EnQueue(i,j,k);Mapij = 1;if(i = 8 & j = 9) return;/到达终点,(8,9)是默认终点，可以任意修改i = n; j = m;/保证遍历当前坐标的所有相邻位置void ShortestPath()int i,j,k,sum(0) ;k = rear-1;while(k != -1)i = Qk.x;j = Qk.y;Mapij = 2;k = Qk.parent_id;cout 0 1 2 3 4 5 6 7 8 9endl;for(i = 0;i 10;i+)couti;for(j = 0;j 10;j+)if(Mapij=2)sum+; cout;elsecout;coutendl;cout最短路径长度： sumendl;void Print()cout 0 1 2 3 4 5 6 7 8 9endl;for(int i = 0;i 10;i+)couti;for(int j = 0;j 10;j+)if(Mapij) cout;else cout;coutendl;六、 运行中出现的问题及解决方法： 1、在最初尝试编写代码时，采用的是递归算法。虽然用栈实现代码很简单，只需要向四个方向不断递归即可，但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后，我开始思索如何能输出最短路径。查找大量资料，结论是用栈很难实现，即使要实现也需要不断比较各种路径的长短，然后不断更新最短路径。偶然发现迪杰斯特拉算法，后又学习广度优先搜索算法，才用队列才最终使得问题得以解决。2、在将新算法应用到迷宫问题过程中，遇到不少困难，反复琢磨和看书才将其解