假设有一个 N*N 的正方形迷宫(如图 1 所示),老鼠必须从起始点移动到终点,它可以向上、向下、向左、向右移动,但仅限于在白色区域内移动。
图 1 N*N 迷宫
回溯算法可以很好地解决类似的迷宫问题,该算法能够从起点开始,逐一测试所有的移动路线,并最终找到能够达到终点的移动路线。
迷宫问题的解决方案
假设迷宫中可行走的白色区域用 1 表示, 不能行走的黑色区域用 0 表示,图 1 的迷宫可以用如下的矩阵表示:
1 0 1 1 1
1 1 1 0 1
1 0 0 1 1
1 0 0 1 0
1 0 0 1 1
这是一个 5*5 的矩阵,其中 (1,1) 为起点,(5,5) 为终点。
如下为回溯算法解决迷宫问题的伪代码:
输入 maze[ROW][COL] //输入迷宫地图,0 表示黑色区域,1 表示可行走区域
//(row,col) 表示起点,(outrow,outcol)表示终点
maze_puzzle(maze,row,col,outrow,outcol):
//回溯过程中,行走的每一区域都设为 Y,表示已经做了测试
maze[row][col] <- 'Y'
//如果行走至终点,表明有从起点到终点的路线
if row == outrow && col == outcol:
print maze // 输出行走路线
return
//测试从起点向上行走是否可行
if canMove(maze,row-1,col):
maze_puzzle(maze,row-1,col,outrow,outcol)
//测试从起点向左行走是否可行
if canMove(maze,row,col-1):
maze_puzzle(maze,row,col-1,outrow,outcol)
//测试从起点向下行走是否可行
if canmove(maze,row+1,col):
maze_puzzle(maze,row+1,col,outrow,outcol)
//测试从起点向右行走是否可行
if canmove(maze,row,col+1):
maze_puzzle(maze,row,col+1,outrow,outcol)
如下为解决图 1 迷宫问题的 C 语言程序:
#include <stdio.h> typedef enum { false, true } bool; #define ROW 5 #define COL 5 //假设当前迷宫中没有起点到终点的路线 bool find = false; //回溯算法查找可行路线 void maze_puzzle(char maze[ROW][COL], int row, int col, int outrow, int outcol); //判断指定路线是否可以行走 bool canMove(char maze[ROW][COL], int row, int col); //输出行走路线 void printmaze(char maze[ROW][COL]); int main() { char maze[ROW][COL] = { {'1','0','1','1','1'}, {'1','1','1','0','1'}, {'1','0','0','1','1'}, {'1','0','0','1','0'}, {'1','0','0','1','1'} }; maze_puzzle(maze, 0, 0, ROW - 1, COL - 1); if (find == false) { printf("未找到可行线路"); } return 0; } //(row,col) 表示起点,(outrow,outcol)表示终点 void maze_puzzle(char maze[ROW][COL], int row, int col, int outrow, int outcol) { maze[row][col] = 'Y'; // 将各个走过的区域标记为 Y //如果行走至终点,表明有从起点到终点的路线 if (row == outrow && col == outcol) { find = true; printf("成功走出迷宫,路线图为:\n"); printmaze(maze); return ; } //尝试向上移动 if (canMove(maze, row - 1, col)) { maze_puzzle(maze, row - 1, col, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row - 1][col] = '1'; } //尝试向左移动 if (canMove(maze, row, col - 1)) { maze_puzzle(maze, row, col - 1, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row][col - 1] = '1'; } //尝试向下移动 if (canMove(maze, row + 1, col)) { maze_puzzle(maze, row + 1, col, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row + 1][col] = '1'; } //尝试向右移动 if (canMove(maze, row, col + 1)) { maze_puzzle(maze, row, col + 1, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row][col + 1] = '1'; } } //判断指定路线是否可以行走 bool canMove(char maze[ROW][COL], int row, int col) { //如果目标区域位于地图内,不是黑色区域,且尚未行走过,返回 true:反之,返回 false return row >= 0 && row <= ROW - 1 && col >= 0 && col <= COL - 1 && maze[row][col] != '0' && maze[row][col] != 'Y'; } //输出行走路线 void printmaze(char maze[ROW][COL]) { int i, j; for (i = 0;i < ROW; i++) { for (j = 0; j < COL; j++) { printf("%c ", maze[i][j]); } printf("\n"); } }
如下为解决图 1 迷宫问题的 Java 程序:
public class Demo { static boolean find = false; static int ROW = 5; static int COL = 5; //(row,col) 表示起点,(outrow,outcol)表示终点 public static void maze_puzzle(char [][] maze, int row, int col, int outrow, int outcol) { maze[row][col] = 'Y'; // 将各个走过的区域标记为 Y //如果行走至终点,表明有从起点到终点的路线 if (row == outrow && col == outcol) { find = true; System.out.println("成功走出迷宫,路线图为:"); printmaze(maze); return ; } //尝试向上移动 if (canMove(maze, row - 1, col)) { maze_puzzle(maze, row - 1, col, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row - 1][col] = '1'; } //尝试向左移动 if (canMove(maze, row, col - 1)) { maze_puzzle(maze, row, col - 1, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row][col - 1] = '1'; } //尝试向下移动 if (canMove(maze, row + 1, col)) { maze_puzzle(maze, row + 1, col, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row + 1][col] = '1'; } //尝试向右移动 if (canMove(maze, row, col + 1)) { maze_puzzle(maze, row, col + 1, outrow, outcol); //如果程序不结束,表明此路不通,恢复该区域的标记 maze[row][col + 1] = '1'; } } //判断指定路线是否可以行走 public static boolean canMove(char [][] maze, int row, int col) { //如果目标区域位于地图内,不是黑色区域,且尚未行走过,返回 true:反之,返回 false return row >= 0 && row <= ROW - 1 && col >= 0 && col <= COL - 1 && maze[row][col] != '0' && maze[row][col] != 'Y'; } //输出行走路线 public static void printmaze(char [][] maze) { for(int i=0;i<ROW;i++) { for(int j=0;j<COL;j++) { System.out.print(maze[i][j]+" "); } System.out.println(); } } public static void main(String[] args) { char [][]maze = new char[][]{ {'1','0','1','1','1'}, {'1','1','1','0','1'}, {'1','0','0','1','1'}, {'1','0','0','1','0'}, {'1','0','0','1','1'} }; maze_puzzle(maze, 0, 0, ROW - 1, COL - 1); if (find == false) { System.out.print("未找到可行线路"); } } }
如下为解决图 1 迷宫问题的 Python 程序:
#指定地图的行数和列数 ROW = 5 COL = 5 #初始化地图 maze =[['1','0','1','1','1'], ['1','1','1','0','1'], ['1','0','0','1','1'], ['1','0','0','1','0'], ['1','0','0','1','1']] #假设当前迷宫中没有起点到终点的路线 find = False #回溯算法查找可行路线 def maze_puzzle(maze,row,col,outrow,outcol): global find maze[row][col] = 'Y' if row == outrow and col == outcol: find = True print("成功走出迷宫,路线图为:") printmaze(maze) return if canMove(maze,row-1,col): maze_puzzle(maze, row - 1, col, outrow, outcol) #如果程序不结束,表明此路不通,恢复该区域的标记 maze[row - 1][col] = '1' if canMove(maze, row, col - 1): maze_puzzle(maze, row, col - 1, outrow, outcol) #如果程序不结束,表明此路不通,恢复该区域的标记 maze[row][col - 1] = '1' #尝试向下移动 if canMove(maze, row + 1, col): maze_puzzle(maze, row + 1, col, outrow, outcol) #如果程序不结束,表明此路不通,恢复该区域的标记 maze[row + 1][col] = '1' #尝试向右移动 if canMove(maze, row, col + 1): maze_puzzle(maze, row, col + 1, outrow, outcol) #如果程序不结束,表明此路不通,恢复该区域的标记 maze[row][col + 1] = '1' #判断指定路线是否可以行走 def canMove(maze,row,col): return row >= 0 and row <= ROW - 1 and col >= 0 and col <= COL - 1 and maze[row][col] != '0' and maze[row][col] != 'Y' #输出行走路线 def printmaze(maze): for i in range(0,ROW): for j in range(0,COL): print(maze[i][j],end=" ") print() maze_puzzle(maze,0,0,ROW-1,COL-1) if find == False: print("未找到可行路线")
以上程序的输出结果均为:
成功走出迷宫,路线图为:
Y 0 Y Y Y
Y Y Y 0 Y
1 0 0 Y Y
1 0 0 Y 0
1 0 0 Y Y
其中,'Y' 表示可行的移动路线。