欢迎来到天天文库
浏览记录
ID:12670836
大小:495.00 KB
页数:17页
时间:2018-07-18
《数据结构课程设计---迷宫问题求解》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、迷宫问题求解一.问题的提出:人类建造迷宫已有5000年的历史。在世界的不同文化发展时期,这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走,寻找真相。关于迷宫,有一个引人入胜的希腊神话,这也是为什么现今每当人们提到这个问题,总是兴致勃勃(对于年青人,估计是RPG玩多了)。这则神话讲的是,从前弥诺斯王统治着克里特岛。有一年,他没有给海神波塞冬送去允诺的祭物公牛,海神十分生气,决意报复。他附体在公牛身上,勾引了弥诺斯王的妻子帕西法厄王后。不久,王后生下一个牛首人身的怪物弥诺陶洛斯(Minotaur)。为了把怪物藏起来避免家丑外扬,弥诺斯王命令岛上最优秀
2、的工匠代达罗斯造了一座迷宫:一所稀奇古怪的地下房子,走廊离亮处越来越远,根本找不到出口。发狂的弥诺陶洛斯在一堵堵墙壁之间徘徊游荡,左突右冲,以雅典王进贡的童男童女充饥。终于有一天,雅典王子忒修斯(Theseus)带着宝剑冒充进贡的童男进入迷宫。他一路退下弥诺斯王的女儿阿里阿德涅送给他的线团的线,杀死了牛头怪物弥诺陶洛斯,又沿着这根线找到出口,活着离开迷宫...一般的迷宫为二维平面图形,将迷宫的左上角作入口,右下角作出口,求出从入口点到出口点的一条通路。迷宫的大小为N×N,N预定义为常数,修改N的值可以改变迷宫的大小(只要不超过屏幕显示范围),而程序不必做修改。用白
3、色表示可走的路,红色表示墙壁不可以通过。程序还设计了两种运行方式:一种是由系统自动运行探索,用递归方法实现;另一种是直接按结果搜索探索通路,颇有新意。图1迷宫的图例图2迷宫的求解老师指点二.问题的分析:图3基本思想本问题的求解,关键是如何找到求解任意两个点间,按照以上基本思想而走出的路线。按照这个路线,我们可以通过图形函数来动态的显示迷宫的搜索过程。计算机解迷宫解通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进,否则沿着原路退回,换一个方向继续探索,直至出后位置,求得一条通路。假如所有可能的通路都探索到位能到达出口,则所设定
4、的迷宫没有通路。为此,我们先要处理地图问题。将地图中有墙的地方设为1,而没墙的地方,也即可以通行的地方设为0,如:在我们的这个程序中的一个例子中,地图如下显示:图4地图1当然了,有了地图,下一步就是如何在地图中查询可行路线了。按照基本思想,当前已走过的可行的应设为墙,以防止在程序的搜索过程中,其又按原路返回,造成死循环。在我们的程序中,我们设走过的路的地图所在地为2,如下示:zmap[row][col]=2;/*blockcurrentposition*/搜索路线,当需要一个数组来存储可行路线了,我们在程序中如下设定:struct{introw;/*therowo
5、ftheposition*/intcol;/*thecoloftheposition*/}path[maxlength];由基本思想,搜索中按东南西北的先后顺序,我们又定义一个结构体来进行搜索中的换向,如下示:struct{introw,col;}offsets[zdir]={{0,1},/*movetoeast*/{1,0},/*movetosouth*/{0,-1},/*movetowest*/{-1,0}/*movetonorth*/};由于迷宫问题很悠久,解决方法也有很多,如:1、回溯回溯法使用栈的方式,这与当初忒修斯使用的方法很像,只不过这里用栈代替了英
6、雄手中的线团。简单描述一下:每到达一个能走的新位置时都要把当前位置与来时的方向压栈,当遇到死路时就弹出栈顶位置,顺着下一方向继续走,直到到达出口(找到一条通路)或退回到入口(迷宫没有出口)时结束。若到达出口,此时从入口到出口的一条通路就保存在栈中,依次弹出并输出即可。由于刚学到栈,还不太熟悉,故我们没用这种方法。但过一段时间,我们会改成这种方法的。2、递归一般来说栈与递归是可以相互转化的,使用递归的地方都可以改成栈的方式,反过来也一样。但在求解迷宫问题时,栈与递归代表了两种不同的指导思想,如果说栈式的搜索方法象征着英雄忒修斯的话,那么使用递归法则更像一位手握大权的
7、领导。当他站在迷宫入口处时,他才懒得亲自去走,这时这位领导会吩咐他的手下,让他们分别向着迷宫的各个方向去探索;当遇到岔路口时留一个人守在这里,再分出几股人,朝着每个方向继续探索;最后总会有一个人发现出口。发现出口的这个人将出口的位置报告给离他最近的路口处留守的人,再由这个人报告给上一个路口的人,依次层层上报,最后消息传到了领导那里,于是这位领导就顺着这条画好的通路大摇大摆地通过了迷宫。了解了这种思想后对于递归法就很好理解了。在递推的过程中实际上是系统自动地进行了压栈,而在回归时又自动地进行了弹栈,只不过这个栈位于系统的堆栈区,对普通用户来说是不可见的。a.我们用的
8、正是这种方
此文档下载收益归作者所有