数据结构与算法实习 算法之二:回溯法 北京大学信息科学技术学院 主讲:张铭、郝丹 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 遍历顺序（右下上左）