|
之前我们已经讨论了采用回溯（Backtracking)方法来解决国际象棋中马的遍历问题。 为了让大家更加熟悉回溯方法，我们将在后面的课程中再分析几个例子。 今天先看一个使用回溯方法解决老鼠走迷宫的问题。 下图是一个迷宫，其中涂上灰色的方格，老鼠不能进入，请找出老鼠从起点到终点的线路。老鼠只能向两个方向移动：向前和向下，在下面的例子中也就是只能向右或向下移动。（注意，这是迷宫问题的一个简单版本。 而在更复杂的版本中，老鼠可以在4个方向上移动或甚至可以跳着走） 下图表示一条从起点到终点的可行路径。 算法思路 我们把老鼠迷宫问题做一个抽象。 假设迷宫是一个N*N的二维矩阵（矩阵简称为M），矩阵中的每个元素M[i][j](0≤i≤N-1,0≤j≤N-1)是一个单元格方块。 其中最左上方的块，即M[0][0]是老鼠出发的格子，而最右下的格子M[N-1][N-1]是它的出口。 问题就变成从格子M[0][0]开始，寻找到达M[N-1][N-1]的路径。 在老鼠闯荡迷宫矩阵的过程中，我们用0和1来表示老鼠是否可以进入某个方格。如果某方格M[i][j]被标注为0，那么表示它是一个死胡同，老鼠无法进入该方格；而如果它被标注为1，则表示老鼠可以进入它。 因此上面的例子对应的抽象矩阵为： {1, 0, 0, 0} {1, 1, 0, 1} {0, 1, 0, 0} {1, 1, 1, 1} 朴素算法的思路 朴素算法生成从起点格子到终点格子的所有路径，并逐个检查每个路径是否能满足约束条件。 如有还有未经验证的路径 { 生成下一条路径 如果此路径的所有方格都为1 { 输出这条路径; } } 朴素算法需要列举所有可行的路径，可能效率会不高，特别是迷宫比较大的时候。 回溯算法的思路 下面是回溯算法的解题思路。 从起点方格开始，如果当前所在的方格已经是终点方格 打印输出找到的路径矩阵，结束 否则 a）将当前方格标记为1 b）在水平方向向右移动一个方格并递归检查是否该移动可以找到解 c）如果在上述步骤中选择的移动没有找到解 那么向下移动一个方格并并递归检查此移动是否可以找到解 d）如果上述方法都不起作用，则将该方格标记为0，表示需要回退（Backtracing）并返回false 代码实现 以下是老鼠迷宫问题的c/C++代码实现。 它以二维矩阵形式打印出一种可能的解决方案。 最后的输出是一个矩阵，显示为1的格子是老鼠经过的格子。 #include <stdio.h> // 迷宫大小 #define N 4 bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]); /* 该函数可以输出找到的解矩阵[N][N] */ void printSolution(int sol[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) printf(' %d ', sol[i][j]); printf('\n'); } } /* 该函数检查坐标(x,y)是否是一个有效的方格 */ bool isSafe(int maze[N][N], int x, int y) { // 如果（x,y）超出了迷宫的范围返回false if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1) return true; return false; } /* 使用回溯算法解决迷宫问题。主要思路： 使用solveMazeUtil（）来寻找路径。 如果没有找到可行的路径，则返回false 否则返回true并打印出找到的路径（采用1来表示） 请注意，可能有多个解决方案，这里只找出一个可行的解决方案 */ bool solveMaze(int maze[N][N]) { int sol[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveMazeUtil(maze, 0, 0, sol) == false) { printf('Solution doesn't exist'); return false; } printSolution(sol); return true; } /*采用递归函数来解决迷宫问题*/ bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) { //如果（x,y）正好是目标方格，那么返回true if (x == N - 1 && y == N - 1) { sol[x][y] = 1; return true; } //检查（x,y）是否是一个合法的方格 if (isSafe(maze, x, y) == true) { // mark x, y as part of solution path //把（x，y）标记为路径中的一个方格 sol[x][y] = 1; /*向x方向，也就是右边移动*/ if (solveMazeUtil(maze, x + 1, y, sol) == true) return true; /* 如果向x方向移动，没有找到合适的路径，那么，改向y方向，也就是向下移动*/ if (solveMazeUtil(maze, x, y + 1, sol) == true) return true; /* 如果以上的移动步骤，无法找到路径，那么，将（x,y）标记为0*/ sol[x][y] = 0; return false; } return false; } // 主程序 int main() { int maze[N][N] = { { 1, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 0 }, { 1, 1, 1, 1 } }; solveMaze(maze); return 0; } 输出的样子如下： 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 请你试着运行看看是否能得到正确的答案。 |
|
|
