数据结构课程设计迷宫问题求解.doc

《数据结构课程设计迷宫问题求解.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计迷宫问题求解.doc（16页珍藏版）》请在三一办公上搜索。

1、迷宫问题求解 一问题的提出： 人类建造迷宫已有5000年的历史。在世界的不同文化发展时期，这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走，寻找真相。关于迷宫，有一个引人入胜的希腊神话，这也是为什么现今每当人们提到这个问题，总是兴致勃勃（对于年青人，估计是RPG玩多了）。这则神话讲的是，从前弥诺斯王统治着克里特岛。有一年，他没有给海神波塞冬送去允诺的祭物公牛，海神十分生气，决意报复。他附体在公牛身上，勾引了弥诺斯王的妻子帕西法厄王后。不久，王后生下一个牛首人身的怪物弥诺陶洛斯(Minotaur)。为了把怪物藏起来避免家丑外扬，弥诺斯王命令岛上最优秀的工匠代达罗斯造了一座迷宫：

2、一所稀奇古怪的地下房子，走廊离亮处越来越远，根本找不到出口。发狂的弥诺陶洛斯在一堵堵墙壁之间徘徊游荡，左突右冲，以雅典王进贡的童男童女充饥。终于有一天，雅典王子忒修斯(Theseus)带着宝剑冒充进贡的童男进入迷宫。他一路退下弥诺斯王的女儿阿里阿德涅送给他的线团的线，杀死了牛头怪物弥诺陶洛斯，又沿着这根线找到出口，活着离开迷宫.一般的迷宫为二维平面图形,将迷宫的左上角作入口，右下角作出口，求出从入口点到出口点的一条通路。迷宫的大小为NN，N预定义为常数，修改N的值可以改变迷宫的大小（只要不超过屏幕显示范围），而程序不必做修改。用白色表示可走的路，红色表示墙壁不可以通过。程序还设计了两种运行方式

3、：一种是由系统自动运行探索，用递归方法实现；另一种是直接按结果搜索探索通路，颇有新意。 图1 迷宫的图例 图2 迷宫的求解老师指点二问题的分析： 图3 基本思想本问题的求解，关键是如何找到求解任意两个点间，按照以上基本思想而走出的路线。按照这个路线，我们可以通过图形函数来动态的显示迷宫的搜索过程。计算机解迷宫解通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进，否则沿着原路退回，换一个方向继续探索，直至出后位置，求得一条通路。假如所有可能的通路都探索到位能到达出口，则所设定的迷宫没有通路。为此，我们先要处理地图问题。将地图中有墙的地方设为1，而没墙的地方，

4、也即可以通行的地方设为0，如：在我们的这个程序中的一个例子中，地图如下显示：图4 地图1 当然了，有了地图，下一步就是如何在地图中查询可行路线了。按照基本思想，当前已走过的可行的应设为墙，以防止在程序的搜索过程中，其又按原路返回，造成死循环。在我们的程序中，我们设走过的路的地图所在地为2，如下示：zmaprowcol=2; /* block current position */ 搜索路线，当需要一个数组来存储可行路线了，我们在程序中如下设定：struct int row; /* the row of the position */ int col; /* the col of the pos

5、ition */ pathmaxlength;由基本思想，搜索中按东南西北的先后顺序，我们又定义一个结构体来进行搜索中的换向，如下示：struct int row,col; offsetszdir=0,1 , /* move to east */ 1,0 , /* move to south */ 0,-1, /* move to west */ -1,0 /* move to north */ ;由于迷宫问题很悠久，解决方法也有很多，如：1、回溯回溯法使用栈的方式，这与当初忒修斯使用的方法很像，只不过这里用栈代替了英雄手中的线团。简单描述一下：每到达一个能走的新位置时都要把当前位置与来时的方

6、向压栈，当遇到死路时就弹出栈顶位置，顺着下一方向继续走，直到到达出口（找到一条通路）或退回到入口（迷宫没有出口）时结束。若到达出口，此时从入口到出口的一条通路就保存在栈中，依次弹出并输出即可。由于刚学到栈，还不太熟悉，故我们没用这种方法。但过一段时间，我们会改成这种方法的。2、递归一般来说栈与递归是可以相互转化的，使用递归的地方都可以改成栈的方式，反过来也一样。但在求解迷宫问题时，栈与递归代表了两种不同的指导思想，如果说栈式的搜索方法象征着英雄忒修斯的话，那么使用递归法则更像一位手握大权的领导。当他站在迷宫入口处时，他才懒得亲自去走，这时这位领导会吩咐他的手下，让他们分别向着迷宫的各个方向去探

7、索；当遇到岔路口时留一个人守在这里，再分出几股人，朝着每个方向继续探索；最后总会有一个人发现出口。发现出口的这个人将出口的位置报告给离他最近的路口处留守的人，再由这个人报告给上一个路口的人，依次层层上报，最后消息传到了领导那里，于是这位领导就顺着这条画好的通路大摇大摆地通过了迷宫。了解了这种思想后对于递归法就很好理解了。在递推的过程中实际上是系统自动地进行了压栈，而在回归时又自动地进行了弹栈，只不过这个栈位于系统的堆栈区，对普通用户来说是不可见的。a.我们用的正是这种方法，如下所示：int zfindpath(int row,int col,int erow,int ecol) int dir

8、,row2,col2; if(row=erow)&(col=ecol) path0.row=erow; path0.col=ecol; /* judge if is the exit */ return 1; zmaprowcol=2; /* block current position */ for(dir=0;dir0) pathlen.row=row2; /* use recursion to find the path */ pathlen.col=col2; return +len; return 0;下面这一段，我们将给出对这一段程序的分析： 首先，我们定入了函数int zfind

9、path(int row,int col,int erow,int ecol) 来进行求解。其中row和 col为传入函数中的入口地址坐标， 而erow 和ecol则是出口地址的坐标。其次，给出了递归程序退出的出口条件：if(row=erow)&(col=ecol) path0.row=erow; path0.col=ecol; /* judge if is the exit */ return 1; 即，如果出口与入口的坐标相同，说明我们已找到终点，可以退出了。如若不然，说明我们还没到达最终目的地，还需继续寻找；如前所述，当前已走过的可行的应设为墙，以防止在程序的搜索过程中，其又按原路返回，

10、造成死循环，即为以下程序所示示：zmaprowcol=2; /* block current position */当然，如果在当前方向下没找到出路，我们将要换向下，用语句row2=row+offsetsdir.row; /* step to next space */ col2=col+offsetsdir.col; /* if want to observe the trace of the ball,you should add code after here!*/来实现我们的目的，其中dir的0，1，2，3值的取向，分别代表了东西南北的搜索过程。如果当前路的下一步为0，说明此路可通，我

11、们深入下一层递归之中，以便找出最终解： if(zmaprow2col2=0) /* mean the way could go at this stage */ len=zfindpath(row2,col2,erow,ecol); 正如前面所述，如果找到终点，则返回一个true 值。此时，len将是大于0的。便将执行以下程序：if(len0) pathlen.row=row2; /* use recursion to find the path */ pathlen.col=col2; return +len;即告诉我们，已找到合适的路径了，正在记录。这样等这段程序运行完成后，我们合适的路径

12、就在pathlen中保存了。 b.当然，如果仅是这样输出的话，肯定不好看，也不好观察具体中间程序的运行细节，于是我们进行了图行界面的输出以动态显示。 首先，我们要根据地图来创建图形式的迷宫：createmap()函数正是来完成这个工作。 void createmap(int n1,int n2,int n3,int n4) int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22; void *buf; int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,c:tc); cleardevice()

13、; setbkcolor(10); setcolor(1); settextstyle(4, 0, 5); outtextxy(70,20,hello,welcome to here! ); setcolor(4); setfillstyle(1, 4); for(i=0;i10;i+) for(j=0;j10;j+) if(zmapij=1) setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ else setfillstyle(1, 15); bar( 150+j*22,100+i*22,1

14、70+j*22,120+i*22);/*sleep(1);*/ line(100,80,150+n2*22,100+n1*22); /* draw a line */ line(337+(n4-8)*22,287+(n3-8)*22,337,360); setcolor(1); settextstyle(4, 0, 3); outtextxy(80,60,this is the entrance! ); outtextxy(320,360,this is the exit! );其中的参数n1,n2,n3,n4并不是产生图形界面所必需的，而仅是做为输出一些字符辅助文字而附加的定义坐标。接下来，

15、我们将对这个函数进行一些细致的分析： 首先，我们应遵循应用图形界面的一些套话：int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,c:tc);来实现图形模式的初始化。接着，在用setbkcolor(10); setcolor(1); settextstyle(4, 0, 5); 进行了前景色、背景色及填充色的设定后，便可以进行画格子了： for(i=0;i10;i+) for(j=0;j0;i-) /* the total number of the path is len */ trow=pathi-1.row-pathi.ro

16、w; tcol=pathi-1.col-pathi.col; sleep(1); x=x+tcol*22; y=y+trow*22; putimage(x,y, buf, COPY_PUT);putimage函数正好有这一功能。于是，程序这样就结束了。在中途中，我们在移动小球的过程中，用了系统sleep函数来使他暂停。为了更好的显示小球在搜索过程中的动态效果，我们特地设置了两个地图，以资对比；当然，更多的地图也是可以的，但我们只仅仅提供个样例。图5 地图2本程序进行了通俗化处理，以显示任意不同的两点间的搜索路径。并且设置了死循环（while(1)），可以一直输入求解和求解目标。三问题的求解：（

17、程序）a.程序：#include stdio.h#include conio.h /*provide the support of getch */#define max 10#define maxlength (max*max) /*the max lenth of the path*/#define zdir 4 /*the total direction*/#include graphics.h /*provide the support of graphics*/#include dos.h /* provide the support of function:sleep */#inc

18、lude time.h /* provide the support of sleep */#define M 10 /*the max lenth of the map*/ #define N 10 /*the max lenth of the map*/*the following four function are stating functions*/void printmap(void);int zfindpath(int row,int col,int erow,int ecol);void creategraphich(int n1,int n2,int n3,int n4);v

19、oid creategraphich(int n1,int n2,int n3,int n4);int zmapmaxmax= 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,1, 1,1,1,1,1,1,1,1,1,1 ;struct int row,col; offset

20、szdir=0,1 , 1,0 , 0,-1, -1,0 ;struct int row; int col; pathmaxlength;/*define a globle variable to convenience output*/int len;int zfindpath(int row,int col,int erow,int ecol) int dir,row2,col2; /* int x=150+col*22,y=100+row*22; */ sleep(1); setcolor(10); /* draw a cirlce */ setfillstyle(1, 14); cir

21、cle(150+(col)*22+10,100+(row)*22+10, 8); floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10); if(row=erow)&(col=ecol) path0.row=erow; path0.col=ecol; /* judge if is the exit */ return 1; /* the end of if */ zmaprowcol=2; /* block current position */ for(dir=0;dir0) pathlen.row=row2; /* use recursion

22、 to find the path */ pathlen.col=col2; return +len; /*the end of if */ /*the end of if */ /* the end of for */ sleep(1); setfillstyle(1, 15); bar( 150+col*22,100+row*22,170+col*22,120+row*22); /* sleep(1); */ return 0; /* the end of zfindpaht */void printmap() /* first ,print the map that we will go

23、 */ int i,j; for(i=0;imax;i+) for(j=0;jmax;j+) printf( %d,zmapij); printf(n); getch();void createmap(int n1,int n2,int n3,int n4) int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22; void *buf; int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,c:tc); cleardevice(); setbkcolor(10); setcolor(1); se

24、ttextstyle(4, 0, 5); outtextxy(70,20,hello,welcome to here! ); setcolor(4); setfillstyle(1, 4); for(i=0;i10;i+) for(j=0;j10;j+) if(zmapij=1) setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ else setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ l

25、ine(100,80,150+n2*22,100+n1*22); /* draw a line */ line(337+(n4-8)*22,287+(n3-8)*22,337,360); setcolor(1); settextstyle(4, 0, 3); outtextxy(80,60,this is the entrance! ); outtextxy(320,360,this is the exit! ); void creategraphich(int n1,int n2,int n3,int n4) int i,j,size,trow,tcol,x=150+n2*22,y=100+

26、n1*22; void *buf; int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,c:tc); cleardevice(); setbkcolor(10); setcolor(1); settextstyle(4, 0, 5); outtextxy(70,20,hello,welcome to here! ); setcolor(4); setfillstyle(1, 4); for(i=0;i10;i+) for(j=0;j0;i-) /* the total number of the path is len-1 */

27、trow=pathi-1.row-pathi.row; tcol=pathi-1.col-pathi.col; sleep(1); x=x+tcol*22; y=y+trow*22; putimage(x,y, buf, COPY_PUT); /* printf the result*/ setcolor(1); settextstyle(4, 0, 3); outtextxy(357,287,sussessfully!); getch(); closegraph(); free(void *)buf); void changemap(int d) FILE *fw; int i,j; if(

28、d=1) fw=fopen(c:tca.txt,r); if(!fw) printf(not found!); getch();return; for(i=0;iM;i+) for( j=0;jN;j+ ) fscanf(fw,%d,&zmapij); /* the end of for */ /* the end of first if*/ else fw=fopen(c:tcb.txt,r); if(!fw) printf(not found!); getch();return; for(i=0;iM;i+) for( j=0;jN;j+ ) fscanf(fw,%d,&zmapij);

29、/* the end of for */ /* the end of else */ printf(the map we will follow to search :n); for(i=0;iM;i+) for(j=0;jN;j+) printf( %d,zmapij); printf(n); getch();fclose(fw); main() while(1) int i,j,n1,n2,n3,n4,n5,n6; int zch; /* while(1) */ len=0; printf(if you want to use the default map,press 1,if you want to use the spare map,press 2 :n); scanf(%d,&zch); if(zch=2) changemap(1); /*