数据结构与算法实习 算法之二:回溯法 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang at] net. pku. edu. cn http:/www,jpk.pku.edu.cn/pkujpk/course/sjig/shixil 2011.8 张铭赵海燕王腾蛟宋国杰,《数据结构与算法实验 教程》(国家十一五规划教材),高教社2011年1
1 数据结构与算法实习 ——算法之二：回溯法 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验 教程》（国家十一五规划教材），高教社2011年1月
达菲鸭走迷宫 3D迷宫 怪盗闯古墓 瑞克闯迷宫 Hal 蜘蛛迷宫 神奇魔方 机器人闯迷宫 迷宫探宝 国 极地迷宫 疯狂迷宫 迷宫之吃冰激凌 逃出迷宫 强@ .世≈ @
回溯算法 2
迷宫问题 迷宫可用如图所示的网 格来表示。每个方格或 为通道(空白方格) 入口 或为墙(带阴影的格 012345678910 子)。入口和出口是事 先指定的两个方格。 个简单路即在球得 的路径上不能重复出现 同一通道块。 4567 出口
3 迷宫问题 ◼ 迷宫可用如图所示的网 格来表示。每个方格或 为通道（空白方格）， 或为墙（带阴影的格 子）。入口和出口是事 先指定的两个方格。 ◼ 找出从入口到出口的一 个简单路径，即在求得 的路径上不能重复出现 同一通道块
右、下、上、左枚举,回溯 把迷宫扩充一圈,加“监视哨” 入口
4 右、下、上、左枚举，回溯 把迷宫扩充一圈，加“监视哨” 入口 出口
遍历顺序(右下上左) 111111 入口。11。1n 1。。。x。。s1 111121×111 HH「鬥H:: 111111出口 111111nn111
5 入口 → 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 → 出口 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 遍历顺序（右下上左）
回溯示意(上右下左) 开始第一次回朔第二次回朔第三次回朔其他回朔 6 结束
6 回溯示意（上右下左）
经典搜索问题 ■从入口出发,沿某一方向进行探索,若 能走通,则继续向前走;否则沿原路返 回,换一方向再进行探索,直到遇到出 口或所有可能的通路都探索到为止 方向(搜索树的分枝):每个方格都有 四个可能方向 N direction[4][2] (i-1,j) 0「011方向E ★ E 110方向s (1,-1)(i,j)(i,j+1) 20-1方向W 3仁-10方向N (i+1,j)
7 经典搜索问题 ◼ 从入口出发，沿某一方向进行探索，若 能走通，则继续向前走；否则沿原路返 回，换一方向再进行探索，直到遇到出 口或所有可能的通路都探索到为止。 ◼ 方向（搜索树的分枝）：每个方格都有 四个可能方向
11111111111 101001110…01 迷宫问题算法 10-011 101110…0-0111 10001011011 int mazePath(int maze [][11l,int direction[][2], 11001011001 111000-0-0-0-01 int x1int y1 int x2, int y2t 11111111111 /*在迷宫maze[M]N]中,求从入口maze[x1[y1到出口 mazel2]y2]的一条路径,其中1<=X1x2<=M2, 1<=y1y2<=N-2*/ for(intk=0水k<4水k++){ int g=x1+direction[k]o] h=y1+ directionkkl1] if(maze[glh) continue;//遇到墙或已经搜索过 if(g==x2&&h==y2&8maze[gh]==0){//找到路径 printf( The revers path is: \n%/od, o/od)\nx2,y2; printf("(%/od%od\n"x1,y1; return 1;y mazel]ch]=2; /标记已经搜索过 if (mazePath(maze, direction, g,h, x2, y2)==1 printf("(%od,%/od)\nx1,y1)i return 1;y return0∥/从当前点出发未找到路径
8 迷宫问题算法 int mazePath(int maze[][11],int direction[][2], int x1,int y1,int x2,int y2) { /* 在迷宫maze[M][N]中，求从入口maze[x1][y1]到出口 maze[x2][y2]的一条路径，其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */ for(int k=0;k<4;k++){ int g=x1+direction[k][0], h=y1 + direction[k][1]; if (maze[g][h]) continue; // 遇到墙或已经搜索过 if (g==x2&&h==y2&&maze[g][h]==0){ // 找到路径 printf("The revers path is:\n(%d, %d)\n",x2,y2); printf(“(%d, %d)\n",x1,y1); return 1;} maze[g][h]=2; // 标记已经搜索过 if (mazePath(maze,direction,g,h,x2,y2)==1){ printf(“(%d, %d)\n",x1,y1); return 1;}} return 0; // 从当前点出发,未找到路径 }
骑士巡游问题 给定一个n×n的网格, 有一个国际象棋的马置 于一个方格上。要求找 到一条路径,使马按国 (-2 (i-2 际象棋的允许走法,从 j-1 j+1) 开始的方格出发,不重|( 复地把n2个方格都恰好2 j+2) 经过一次。 j 设马所在方格坐标为(,(+ fi+1 j),则它一步可达的方2) j+2) 格坐标如图所示。 (i+2 +2 ] j+1)
9 骑士巡游问题 ◼ 给定一个ｎ×ｎ的网格， 有一个国际象棋的马置 于一个方格上。要求找 到一条路径，使马按国 际象棋的允许走法，从 开始的方格出发，不重 复地把ｎ２个方格都恰好 经过一次。 ◼ 设马所在方格坐标为(i, j)，则它一步可达的方 格坐标如图所示。 (i-2, j-1) (i-2, j+1) (i-1, j-2) (i-1, j+2) (i, j) (i+1, j-2) (i+1, j+2) (i+2, j-1) (i+2, j+1)
骑士巡游,“马走日字” 枚举8个方向,回溯 000000000 000000000 0023 10 1542500 00|1652491400 001122118300 006172013800 0021|127129|oo 0100000000 000000000
10 骑士巡游，“马走日字” 枚举8个方向，回溯 23 10 15 4 25 16 5 24 9 14 11 22 1 18 3 6 17 20 13 8 21 12 7 2 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0