文档介绍：******@hust.
搜索方法专题
路志宏
华中科技大学数学与统计学院
内容
2. Divide-Conquer
1. 回溯法
迷宮
在迷宫中求从入口到出口的所有路径是一个经典的程序设计问题。
迷宫可用图(a)所示的方块来表示,其中每个元素或为通道(以空白方块表示),或为墙(以带阴影的方块表示)。迷宫问题要求的就是:从入口到出口的一个以空白方块构成的(无环)路径。
1. 引言
求解迷宫问题的简单方法是:
从入口出发,沿某一方向进行探索,若能走通,则继续向前走;
否则沿原路返回,换一方向再进行探索,直到所有可能的通路都探索到为止。
这类方法统称回溯法。
只允许在一端插入和删除的顺序表
允许插入和删除
的一端称为栈顶
(top),另一端称
为栈底(bottom)
特点
后进先出(LIFO)
退栈
进栈
栈又称为后进先出表(Last In First Out表,简称LIFO表)或下推表,如图所示
用回溯法求迷宫问题解的过程,可以用一个栈来保存探索的序列。其算法框架如下:
mazeFrame( void ) {
创建一个(保存探索过程的)空栈;
把入口位置压入栈中;
while 栈不空时{
取栈顶位置并设置为的当前位置;
while 当前位置存在试探可能{
取下一个试探位置;
if (下一个位置是出口)
打印栈中保存的探索过程然后返回
if(下一个位置是通道)
把下一个位置进栈并且设置为的当前位置;
}
}
}
迷宫可用二维数组maze[m][n]来表示,
数组中元素为0的表示通道,为1的表示墙。
迷宫的入口处为maze[1][1],
出口处为maze[m-2][n-2],
它们的元素值必为0。
任意时刻在迷宫中的位置可用元素的行下标和列下标(i,j)来表示。