下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 队和队列应用 迷宫

队和队列应用 迷宫.doc

队和队列应用 迷宫

z0st
2012-06-10 0人阅读 举报 0 0 暂无简介

简介:本文档为《队和队列应用 迷宫doc》,可适用于高等教育领域

北京邮电大学电信工程学院北京邮电大学电信工程学院数据结构实验报告实验名称:实验二栈和队列学生姓名:班级:班内序号:学号:日期:年月日.实验要求a实验目的通过选择下面五个题目之一进行实现掌握如下内容:·进一步掌握指针、模板类、异常处理的使用·掌握栈的操作的实现方法·掌握队列的操作的实现方法·学习使用栈解决实际问题的能力·学习使用队列解决实际问题的能力b实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下:心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫迷宫中设置很多隔壁对前进方向形成了多处障碍心理学家在迷宫的唯一出口放置了一块奶酪吸引老鼠在迷宫中寻找通路以到达出口测试算法的迷宫如下图所示。程序分析存储结构存储结构:队列顺序存储结构示意图如下:关键算法分析核心算法思想:如果采用直接递归的方式用栈很容易实现路径的输出但是这条路径不一定是最短路径。为了改进算法达到输出最短路径的目标采用队列的实现方式。为查找最短路径使用了“图”中的算法:广度优先搜索。关键算法思想描述和实现:关键算法:为寻求最短路径采用广度优先搜索算法使用队列实现路径存储队列中每个元素用结构体存储系包含迷宫坐标、队列中的序号、父节点的序号实现了对路径的记录。C实现:structNode{intparentid保存父节点的位置intnodeid当前节点的序号以便传递给孩子节点intx,y当前结点对应的坐标}Q*每个节点包含迷宫坐标、队列中的序号、父节点的序号多个节点形成队列关键算法:遍历每个位置四周的位置将没有走过的位置入队形成树形的队列通过出队操作就能找到最短路径。C实现:boolGetNextPos(int*i,int*j,intcount){switch(count){case:(*j)return右case:(*i)return下case:(*j)return左case:(*i)return上default:return}}voidEnQueue(inti,intj,intk){Qrearx=iQreary=j保存当前节点对应的坐标位置Qrearparentid=k保存父节点的序号Qrearnodeid=rear保存当前节点序号rear}关键算法:广度优先搜索算法的实现找到最短路径。广度优先算法在此相当于树的层序遍历如下图:在迷宫地图中关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队形成类似上图的树形结构之后广度搜索到最浅深度即为最短路径。例如H节点的坐标就是出口坐标当层序搜索到H时就终止了入队工作结束不再将I和J入队。通过关键算法四逆序就能找到最短路径A>B>C。其实最短路径不一定只有一条例如J点也可能是出口坐标但是当搜索到H时就停止了故此算法只是输出了所有最短路径中可能的一条。C实现:voidShortestPathBFS(inti,intj){intcount,m,n,kEnQueue(i,j,)Map=起点入队,标记起点已走过while(true){count=DeQueue(i,j,k)n=i,m=j保存当前位置while(GetNextPos(i,j,count)){countif(!Mapij){EnQueue(i,j,k)Mapij=if(i==j==)return到达终点,(,)是默认终点可以任意修改}i=nj=m保证遍历当前坐标的所有相邻位置}}}关键算法:使用队列指针查找父节点的方式从队尾回溯到队首标记出最短路径。队列的元素示意图如下:入队之后的队列如下图:…………例如从号节点可以读出它在迷宫地图中的坐标()通过第三个元素就能找到第七号节点也即其父节点()从父节点又可以同理找到它的父节点第三号节点。这样就能实现逆序找到路径。C实现:k=rearwhile(k!=){i=Qkxj=QkyMapij=k=Qkparentid}时间复杂度与空间复杂度:算法一和二时间复杂度与空间复杂度均为O()。算法三占用空间为迷宫边长n的平方故空间复杂度为O(n*n)。最多走n*n步,最少走步故时间复杂度为O(n*n)。程序运行结果测试条件:以实验题目中给出的迷宫图进行测试。测试时固定终点位置选择不同的起点位置进行测试测试各个位置下的输出是否正常。测试结论:本程序对于测试地图在不同起始和终止位置输出都完全正确。总结、在最初尝试编写代码时采用的是递归算法。虽然用栈实现代码很简单只需要向四个方向不断递归即可但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后我开始思索如何能输出最短路径。查找大量资料结论是用栈很难实现即使要实现也需要不断比较各种路径的长短然后不断更新最短路径。偶然发现迪杰斯特拉算法后又学习广度优先搜索算法才用队列才最终使得问题得以解决。、在将新算法应用到迷宫问题过程中遇到不少困难反复琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系实际将一个顺序队列以指针的作用变成了一棵树的结构而树的深度恰好能反映最短路径。、从一个小小的迷宫问题引出了许多知识这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解再到队列的运用后又到树与图以及队列的综合运用将很多知识点串联起来了加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。、改进:本题为了实现代码的简便没有采用链队结构因而浪费了一定的空间特别是当迷宫的边长很长的时候空间复杂度以O(n*n)增长程序效率将大大降低因而如果是计算复杂的迷宫可以考虑将本程序的顺序队列稍加修改变为链队实现动态分配内存以节省空间消耗。、进一步的思考:此方法只能输出一条最短路径如何能输出所有最短路径?初步算法是将同一深度的节点全部遍历如果后续还有同样长度的路径则输出该路径如果没有则只有一条最短路径。附录源代码:本程序在windows、visualstudio环境下调试运行成功#include<iostream>usingnamespacestdvoidEnQueue(inti,intj,intk)入队一个节点voidDeQueue(int*i,int*j,int*k)获取当前节点的序号和对应的迷宫坐标然后出列boolGetNextPos(int*i,int*j,intcount)得到下一个邻接点的位置voidShortestPathBFS(inti,intj)广度优先遍历寻找最短路径voidShortestPath()输出最短路径voidPrint()输出迷宫形状intMap={{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,},{,,,,,,,,,}}structNode{intparentid保存父节点的位置intnodeid当前节点的序号以便传递给孩子节点intx,y当前结点对应的坐标}Q*每个节点包含迷宫坐标、队列中的序号、父节点的序号多个节点形成队列intfront=,rear=队列头指针和尾指针voidmain(){cout<<"程序说明:"<<'n'<<"输出路径为最短路径"<<'n'<<"默认的出口在最右下角如有需要可以调整。"<<'n'<<'n'cout<<"初始地图如下:"<<endlPrint()inti,jreinput:cout<<"请输入起点坐标(x,y):"<<endlcin>>i>>jif(Mapij){cout<<"不能从该处出发请重新输入!"<<endlgotoreinput}ShortestPathBFS(i,j)cout<<"最短路径之一如下:"<<endlShortestPath()}voidEnQueue(inti,intj,intk){Qrearx=iQreary=j保存当前节点对应的坐标位置Qrearparentid=k保存父节点的序号Qrearnodeid=rear保存当前节点序号rear}voidDeQueue(int*i,int*j,int*k){*i=Qfrontx*j=Qfronty*k=Qfrontnodeidfront出列一个节点}boolGetNextPos(int*i,int*j,intcount){switch(count){case:(*j)return右case:(*i)return下case:(*j)return左case:(*i)return上default:return}}voidShortestPathBFS(inti,intj){intcount,m,n,kEnQueue(i,j,)Map=起点入队,标记起点已走过while(true){count=DeQueue(i,j,k)n=i,m=j保存当前位置while(GetNextPos(i,j,count)){countif(!Mapij){EnQueue(i,j,k)Mapij=if(i==j==)return到达终点,(,)是默认终点可以任意修改}i=nj=m保证遍历当前坐标的所有相邻位置}}}voidShortestPath(){inti,j,k,sum()k=rearwhile(k!=){i=Qkxj=QkyMapij=k=Qkparentid}cout<<""<<endlfor(i=i<i){cout<<ifor(j=j<j)if(Mapij==){sumcout<<"□"}elsecout<<"■"cout<<endl}cout<<"最短路径长度:"<<sum<<endl}voidPrint(){cout<<""<<endlfor(inti=i<i){cout<<ifor(intj=j<j)if(Mapij)cout<<"■"elsecout<<"□"cout<<endl}}开始输出迷宫图输入x,y否(x,y)是否合法是广度优先搜索标记最短路径输出最短路径结束第页第页

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/14

队和队列应用 迷宫

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利