基于迷宫问题的回溯法求解及算法实现

2013-11-15毕智超

电子测试 2013年14期

毕智超

（陕西职业技术学院,陕西西安,710100)

0 引言

回溯法也称为试探法。这种方法是按照某种次序将问题的候选解逐一进行列举和检验。本文将利用迷宫问题作为实例，讨论回溯法的求解过程。迷宫问题的提法如下：把一只小白鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫。迷宫中设置了很多墙壁，对前进方向形成了多处障碍。在迷宫的唯一出口处放置了鼠粮，吸引老鼠在迷宫中寻找通路以到达出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则得到一条最佳路线。我们利用回溯法可获得迷宫从入口到出口的最佳路线。

1 迷宫数据结构的设计

针对上述问题的提出，我们可以给出相应设计思想。首先对问题进行抽象给出数学模型。为此，用一个二维数组maze[m+2][p+2]来表示迷宫，当数组元素maze[i][j]=1时，表示该位置是墙壁，不能通行：当maze[i][j]=0时，表示该位置是通路。1≤i≤m，1≤j≤p。数组的第0行，第m+1行，第0列和第p+1列是迷宫的围墙。如图1所示。

图2 可能的前进方向

2 算法设计思想

在求解迷宫问题的过程中，当沿着某一条路径一步步走向出口但发现进入死胡同走不通时，就回溯一步或多步，寻找其他可走的路径。这就需要回溯。老鼠在迷宫中任一时刻的位置可用数组行下标i和列下标j表示。从maze[i][j]出发，可能的前进方向有8个，按顺时针方向为N[i-1][j]，NE[i-1][j+1]，E[i][j+1]，SE[i+1][j+1]，S[i+1][j]，SW[i+1][j-1]，W[i][j-1],NW[i-1][j-1]。如图2所示。

设位置[i][j]标记为X，它实际是一系列交通路口。X周围有8个前进方向，分别代表8个前进位置。如果某一方向是0值，表示该方向有路可通，否则表示该方向已堵死。为了有效地选择下一位置，可以将从位置[i][j]出发可能的前进方向预先定义在一个表内。参看表1，我们称该表为前进方向表(附上程序清单1-前进方向表的结构化定义)，它给出向各个方向的偏移量。

程序清单1 前进方向表的结构化定义

struct offsets

{//位置在直角坐标下的偏移

int a,b; //a，b是x，y方向的偏移

char *dir; //指针dir指示方向

};offsets move[8]; //所有方向的偏移表

当在迷宫中向前试探时，可根据表1所示的前进方向表，选择某一个前进方向向前试探。如果该前进方向走不通，则在前进路径上回退一步，再尝试其他的允许方向。

为了防止重走原路，另外设置一个标志矩阵mark[m+2][p+2],它的所有元素都初始化为0。一旦行进到迷宫的某个位置[i][j]，则将mark[i][j]置为1。下次这个位置就不能再走了。

3 算法实现

回溯法解决迷宫问题的递归算法参见程序清单2。

程序清单2 解决迷宫问题的递归算法实现

int Seekpath(int x,int y)

{/*从迷宫某一位置[i][j]开始，寻找通向出口[m][p]的一条路径。如果找到，则函数返回1。否则函数返回0。试探的出发点为[1][1]。*/

int i,g,h;char *d;

if(x==m & & y==p)return 1;//已到达出口，函数返回1

for(i=0;i＜8;i++)

{//依次按每一个方向寻找通向出口的路径

g=x+move[i].a; h=y+move[i].b; d=move[i].dir;

if(maze[g][h]==0 & & mark[g][h]==0)

{//下一个位置可通，试探该方向

mark[g][h]=1;

if(Seekpath(g,h))

{//从此位置递归试探

cout＜＜"("＜＜g＜＜","＜＜h＜＜"),"＜＜"Direction"＜＜dir＜＜",";

return 1;

}

//回溯，换一个方向再试探通向出口的路径

}

if(x==1 & & y==1)

cout＜＜"no path in maze"＜＜endl;

return 0;

}

为了将递归算法改为非递归算法，需要使用一个堆栈来存储在试探的过程中所走过的路径。一旦需要回退，可以从栈中取得刚才走过位置的坐标和前进方向。栈中需保存一系列三元组以记录这些信息，这些三元组的结构定义如下：

程序清单3 栈中的三元组结构

struct items

{

int x,y,dir;//位置和前进方向序号

}；

当在迷宫中向前试探时，可能同时存在几个允许的前进方向。我们利用三元组记下当前位置和上一步前进的方向，然后根据表1所示的前进方向表，选择某一个允许的前进方向前进一步，并将活动记录进栈，以记下前进路径。如果该前进方向走不通，则将位于栈顶的活动记录退栈，以在前进路径上回退一步，再尝试其他的允许方向。如果栈空则表示已经回退到开始位置。

因为数组maze中的每个位置最多只访问一次，故用来记录搜索路径的栈的大小一般不超过m*p。若设栈的大小为m*p，一般不存在栈满问题。迷宫问题的非递归算法如程序清单4所示。

程序清单4 解决迷宫问题的非递归算法实现

void path(int m,int p)

{/*算法输出迷宫maze中的一条路径。作为围墙，maze[0][i]=maze[m+1][i]=maze[j][0]

=maze[j][p+1]=1，0≤i≤p+1，0≤j≤m+1。在算法中用到一个栈st的重载函数＜＜，功能是顺序输出栈中的各个元素。*/

int i,j,d,g,h; mark[1][0]=1;

Stack＜items＞st(m*p);items tmp;

tmp.x=1;tmp.y=0;tmp.dir=2;

st.Push(tmp);

while(st.IsEmpty()==false)

{

st.Pop(tmp);