文章编号:1006-7353(2004)01-0042(14)-04
迷宫最短路径问题的计算机解法
Ξ
周 丰
(武汉交通职业学院，湖北武汉 430062)
摘要：本文应用数组、栈、队列等数据结构，针对数字化的迷宫图形，采用广度搜索的程序设计思想，完成了迷宫最短路径问题的一种计算机算法，并解决了搜索过程中的循环绕道问题。
关键词：最短路径；算法；数据结构；栈；队列
中图分类号:TP 312 文献标识码:A
迷宫最短路径(the Shortest Path of
Labyrinth )问题是一个典型的搜索、遍历问题，其程序设计思想在许多计算机运算程序、计算机管理程序中均有应用。一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行调试、调整，直至得到最终解答。其中，寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学语言加以描述。但是，迷宫最短路径问题处理的对象不仅仅是纯粹的数值，而且还包括字符、表格、图象等多种具有一定结构的数据，这些非数值计算问题无法用数学方程加以描述，这就给程序设计带来一些新的问题。1.问题描述
迷宫最短路径问题即从一个迷宫的入口(Sour )到出口(Destination )找出一条最短路径。求迷宫中从入口到出口的路径并找出其中最短者的计算机解法，应当用“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路
退回(回溯)，换一个方向再继续探索，直至所有可能的通路都探索到并确定出最短路径为止。为了保证在任何位置上都能沿原路退回，确保正确记录各个路径的长度，在求迷宫最短路径问题中应用诸如顺序表数组、栈、队列等数据结构，也就是自然而然的事了。2.数据的输入与输出
迷宫最短路径问题的数据输入主要包括程序规模、数字化迷宫形成、行进方向设定等。其数据输出包括迷宫图形和运行结果。2.1输入迷宫问题的大小规模
采用m 行n 列数值矩阵描述迷宫。控制问题规模的系数m 、n 都应该是正整数，反映迷宫的长宽尺度。Pat (路墙比)也是一个正整数，用来调整迷宫中0与1的个数比例。该数越大，迷宫中0的个数越多，宫墙相对越少，迷宫越容易通过。2.2建立数值迷宫图形
可用一个二维数组maze [m +1][n +1]模拟该数值迷宫，由随机函数产生随机数(Random Value )0或1。数组元素为0表示该位置允许通过，数组元素为1表示该位置已被封锁，用以表示通路或宫墙。maze [1]
Ξ
收稿日期:2003-11-16
[1]和maze [m ][n ]分别为迷宫的入口和出
口。这样便得到了以矩阵形式排列的迷宫数值模型。
2.3走向(Direction )控制
减法口诀用二维数组dire[8][2]存放八个方向上的位移量，如图1所示[1][2]。2.4数据输出
跑步手表运行该程序首先输出模拟迷宫的二维数组,
若其中存在最短路径，则由出口回溯到入口，再打印这一条路径，如下所示[2]:
(m ,n ),(i ,j ),…,(1,1)
若无通路，则打印:“There is no path !”
图1
3.数据结构
本问题将用到多种类型的数据结构(Da 2ta Structure )，其优点在于实现了信息的隐蔽，即将一切用户不必了解的细节都封装在某种结构类型中。3.1数组(Array )
数组是一种应用广泛的数据结构，其元素之间的关系由下标体现，用二维数组模拟迷宫形象贴切。为了程序中判断方便，把迷宫扩展成为maze[m +2][n +2]，扩展部分的元素(迷宫外围)设置为1，相当于在迷宫周围布上一圈不准通过的墙。这样，在迷宫的任何一个位置(i ,j )上都有八个可供考虑的移动方向。3.2栈(Stack )
栈是回溯(Backtracking )通道时常用的一种数据结构，为了标志已经通过的位置，采用一个状态顺序栈status[m ][n ]，初值为0。
在寻找路径的过程中，若通过了位置(i ,j )，则将元素status[i ][j ]设置为1。3.3队列(Queue )
队列是一种具有先进先出特点的线性数据结构，为了记录寻找过程中到达的位置(点)及其前一个位置(点)，建立一个迷宫行进记录数组at [m 3n ][3]。对于某一个数组元素at [p ]，其中,at [p ][0]和at [p ][1]记下到达位置的坐标i 和j ,at [p ][2]记下其前一个位置在at 数组中的下标。4.算法基本
思想
迷宫最短路径问题的计算机算法(Algo 2rithm )是一个对数字化图形的搜索问题，一般采用狄克斯特拉(Dijkstra ,1959)算法。由于本问题具有迷宫中相邻两点路长恒为1的特点，可对该算法进行改进。4.1基本算法思想
(1)若已经到达出口，则停止搜索并输出结果；否则执行第(2)步。
(2)若前面的道路被封锁，则改变前进方
向并再次执行第(2)步；否则执行第(3)步。
(3)前进一格并记录在案，然后转去执行第(1)步。
上述步骤基于一个简单的“顺时针规则”，即按北、东北、东、……西北八个方向，依次考虑前进的方向。这种方法称为广度搜索法(Breadth Search )。4.2具体实施
从入口maze [1][1]开始，将其记入行进记录数组at ，譬如记入at [1]，并以它作为第一个出发点，依次对八个方向进行搜索。若下一个位置maze [i ][j ]可通行且尚未经过(即maze [i ][j ]=0且status [i ][j ]=0)，则也记入at 数组，譬如记在at [p ]，则在at [p ][2]中要记下其前一个位置在at 数组中的
下标1。在八个方向都搜索过以后，根据先进先出的原则从at 数组中重新取出一个位置作为新的出发点。显然,at 数组是作为一个顺序表示的队列出现的。
重复以上过程，若能够到达出口位置maze[m][n]，表示已经找到最短路径。因为，我们采用的是广度搜索法，且每一层上的路径长度都相等，所以最先到达出口maze [m][n]的路径一定属于最短路径。若at 数组中已经没有位置可以作为新的出发点了，即迷宫中所有位置都搜索完毕，则表示迷宫没有通路。
利用“顺时针规则”虽能顺利地通过迷宫，但实际上却走了许多弯路，即在不少的数组元素处会重复进出。因此，在第一次行进的过程中，计算机不但要确定当前的行进路线，还须利用栈在重复进出两次的方向上设置一道“虚拟封锁门”；这样，当再次通过迷宫时，便能从“虚拟封锁门”折回而避免绕道，好象计算机变得聪明起来。计算机的这种本领是其“智能”的一种表现，当然，这种“智能”必须由人通过栈等数据结构“教”会它。
5.算法细化参考
本算法采用类C语言描述，其数据结构部分前面已进行说明，此处不再赘述。
#include<stdio.h>
#include<stdlib.h>
#define M50
#define N60
int maze[M][N],status[M][N],dire[9][3], at[3000][3];
void function-the-shortest-path(int m,int n)
//0<m≤M-2,0<n≤N-2芋头饺
{//变量声明部分———对所用其它变量完成变量声明
i=0;//此处开始给迷宫设置围墙
while(i<=n+1)
{maze[0][i]=1;maze[m+1][i]=1;
i=i+1;}
纯天然蜂蜜
i=1;
while(i<=m+1)
{maze[i][0]=1;maze[i][n+1]=1;i=i+1;}
i=1;
卫生间的爱//此处开始建立迷宫；并对标志数组初始化
while(i<=m)
{j=1;
while(j<=n)
{maze[i][j]=random(1);
//随机函数产生0或1并赋予迷宫西红柿的功效与作用及营养价值
//可用Pat值调整0与1的比例，然后打印迷宫相应位置(略)
status[i][j]=0;j=j+1;}
i=i+1;}
//读入dire数组；按顺时针建立八个方向上的位移(略);
//寻找最短路径
if(maze[1][1]==0&&maze[m][n]==0) //出入口都可通行
{at[1][0]=1;at[1][1]=1;
//迷宫入口记入at[1]
at[1][2]=-1;
//假设迷宫入口的出发点存于at[-1]
status[1][1]=1;
top=1;
/
/top指向at数组中最新记入迷宫通行点的位置f=1;
//f指向at数组中存放即将作为新出发点的位置j=0;//j=0，表示找不到最短路径;j=1，表示成功找到最短路径
西游记中的好句while(f<=top)//以下为Critical Loop循环
{i=1;
while(i<=8)
{//从f所指的出发点出发，对八个方向搜索可通行的位置
x=at[f][0]+dire[i][1];
y=at[f][1]+dire[i][2];
if(x==m&&y==n)
{//找到最短路径，打印输出
printf(“%d,%d\n”,m,n);
while(f!=-1)
{printf(“%d,%d\n”,at[f][0],at[f] [1]);
f=at[f][2];}
j=1;//建立找到路径的标志
f=top;}//找到一条最短路径，为退出Critical Loop停止搜索准备条件
el
{if(status[x][y]==0&&maze[x][y]==
0)
{//新的通行位置(x,y)记入at数组
top=top+1;
at[top][0]=x;at[top][1]=y;
你是我一生最爱的人
at[top][2]=f;
status[x][y]=1;}
i=i+1;}//继续搜索下一个方向
}//end of while(i<=8)
f=f+1;//准备取出一个新的出发点
}//此时,at数组中已经没有数据，退出Criti2 cal Loop循环
}
if(j==0)printf(“There is no path!”);
//迷宫无通路
el printf(“S our or Destination can’t pass!”);//出口或入口被封锁
return;}
/
/the end of function-the-shortest-path
6.算法分析
6.1时间复杂性
这里选用渐进时间复杂度(Asymptotic Time Complexity)。作为问题的基本操作的原操作，应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度(Frequency Count)相同。因此，建立迷宫需要的时间为O(m3 n)。在最坏情况下有m3n-1个位置要进入at数组，所以寻找路径也需要O(m3 n)，总的时间复杂性为O(m3n)。6.2空间复杂性
本问题的空间复杂度(Space Complexi2 ty)与算法密切相关，它不仅需要存储空间来寄存迷宫本身所用的信息，还需要一些对数据进行操作的工作单元和存储一些实现计算所需信息的辅助空间。
其中，数组maze、status、at所需要的空间都与m3n成正比，其余都是常数。所以，总的空间复杂性为O(m3n)。
此外，尚需说明的是，所谓当前位置“可通”，指的是未曾走到过的通道，即要求该位置不仅是通道，而且既不在当前路径上(否则所求路径就不是简单路径)，也不是曾经纳入过路径的通道(否则只能在死
胡同内转圈)。
一个迷宫的最短路径可能不止一条，本算法只给出首先找到的一条。首先找到哪一条最短路径，与在任一位置上对八个方向的搜索次序有关，即与dire数组元素值的排列次序有关(如图1所示)，调整dire数组元素值的排列次序，就可得到其它的最短路径。
参考文献
[1]严蔚敏、吴伟民.数据结构[M].北京：清华大学
出版社,2002.
[2]郭洁志.计算机软件实践[M].陕西：西北电讯出
版社,1985.
[3]黄刘生、唐策善.数据结构[M].安徽：中国科学
技术大学出版社,2002.
[4]王立柱.C/C++与数据结构[M].北京：清华大
学出版社,2002.
