迷宫问题

迷宫问题求解

一．问题描述：

请设计一个算法实现迷宫问题求解。

二．需求分析：

程序可实现用户与计算机的交互过程。在计算机显示提示信息后，可由用户输入迷宫的大小与形态，以“0”表示墙壁，以“1”表示通路。利用栈操作寻找一条从入口至出口的通路，最终输出带有路线的迷宫。

三．算法思想：

1. 栈的设计：

用计算机解迷宫问题时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通则继续向前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，可以利用“栈”来求解迷宫问题。

2. 表示迷宫的数据结构：

设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中0表示墙壁（不通），1表示通路，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为0。这样做可使问题简化，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。

0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0 0 0

1 0 1 0 0 0 1 0 0 0 0

2 0 1 1 0 1 0 0 0 0 0

3 0 1 1 1 1 1 1 1 0 0

4 0 1 1 0 0 1 0 0 0 0

5 0 0 1 1 1 0 1 1 1 0

6 0 1 0 0 1 1 1 1 1 0

7 0 0 0 0 0 0 0 0 0 0

3. 试探方向：

在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组direct [ 4 ]中，在该数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。

*******************

实践教学

*******************

兰州理工大学

计算机与通信学院

2011年春季学期

数据结构 课程设计

题 目：

专业班级：

姓 名：

学 号：

指导教师：

成 绩：_____________________ 1 目 录

摘 要 ............................................... 2

前 言 ............................................... 3

正 文 ............................................... 4

1. 采用类C语言定义相关的数据类型 .................... 4

2. 各模块的伪码算法.................................. 5

3. 函数的调用关系图.................................. 8

4. 调试分析 ......................................... 9

5. 测试结果 ........................................ 11

6. 源程序（带注释）................................. 11

总 结 .............................................. 18

参考文献 ............................................ 19

致 谢 .............................................. 20

求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。

首先用如图所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下:

int mg[M+1][N+1]={ /*M=10,N=10*/

{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} };

伪代码：

c语言描述如下： void mgpath() /*路径为:(1,1)->(M-2,N-2)*/

{

int i,j,di,find,k;

top++; /*初始方块进栈*/

Stack[top].i=1;

Stack[top].j=1;

Stack[top].di=-1;

mg[1][1]=-1;

while (top>-1) /*栈不空时循环*/

2019年10月 中“呤政魏咬 总第兄期

算法园地

迷宫问题中的算法

陈道蓄

“走迷宫”要求在一个复杂“道路”系统中根据指定起点与终点寻找可行路径。迷宫问题可以上

溯到西方文明的幼年期。希腊神话中，克里特岛一地下迷宫藏着一个怪兽，当地人必须每年送7对少

年男女给它作为祭品，英雄忒修斯主动充当祭品，被送人迷宫。他用宝剑杀死了怪兽，并借助悄悄带

人的毛线团顺利地走出了迷宫。（读者能说出为什么毛线团能帮忒修斯走出迷宫吗?）近代考古发现印

证了古希腊迷宫的存在。[1]

迷宫的神话色彩以及中世纪加给它的宗教隐喻早已淹没在历史的烟尘中，今天迷宫成了一种广为

流传的智力游戏。在网络上用关键字“maze

”能搜索到大量有关迷宫的网页，既有形式多样的迷宫

图案，又有为数众多可以按用户输入参数自动生成迷宫的软件。图1就是按照6X

6和20X

20两个参

数分别得到的两个输出。[2]参数的含义我们会在后面介绍。

图1两个迷宫图例子

迷宫的形式非常多，本文只讨论上图所示的二维矩形迷宫。每个迷宫有指定的人口与要求到达的

终点。终点可以是迷宫对外的出口，也可以是迷宫内部的某个位置（例如克里特迷宫中怪兽隐藏的地

方）。为了与迷宫内部特定位置的出入口区分，我们用entry

表示迷宫的入口，用exit

表示终点（不

—定非得是对外的出口）。

如果我们有整个迷宫的地图，可以看到全貌，走迷宫其实很简单：只需将所有“断头路”用色块

堵死，正确的路径自然会显现（如图2所示）。

图2在看到迷宫全貌的情况下容易发现正确路径

但是当我们身处迷宫之中，周围被高墙阻挡，只能看到前后左右的很小范围，必须“走一步，看

一步”。许多人都知道走迷宫的“右手法则”：如果从entry

能够通达exit

,那么只要始终用手摸着右

边墙壁前行，必定能找到exit

。但是这个方法对图3这样的终点在内部且有回路的迷宫不适用[3]。

• 76

•图3终点在内部且有回路的一种迷宫

我们需要一个普遍适用的策略。由于只能走一步看一步，能够选择的策略其实很简单：尝试+纠