Microsoft PowerPoint - Chap05

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chap05"

偃坑尹
5 years ago
Views:

1 第五章回溯法 2

2 学习要点理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架递归回溯最优子结构性质迭代回溯贪心选择性质子集树算法框架排列树算法框架通过应用范例学习回溯法的设计策略 n 后问题 0-1 背包问题旅行售货员问题装载问题图的着色问题 3

3 回溯法概述

4 回溯法有许多问题, 当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时, 往往要使用回溯法回溯法的基本做法是搜索, 或是一种组织得井井有条的 ( 带有系统性 ), 能避免不必要搜索 ( 带有跳跃性 ) 的穷举式搜索法这种方法适用于解一些组合数相当大的问题 5

5 回溯问题的解空间问题的解向量 : 回溯法希望一个问题的解能够表示成一个 n 元向量 (x 1, x 2,, x n ) 的形式显约束 : 对分量 x i 的取值限定隐约束 : 为满足问题的解而对不同分量之间施加的约束解空间 : 对于问题的一个实例, 解向量满足显式约束条件的所有多元组, 构成了该实例的一个解空间注意 : 同一个问题可以有多种表示, 有些表示方法更简单, 所需表示的状态空间更小 ( 存储量少, 搜索方法简单 ) 6

6 回溯问题的解空间例如 : 有 6 根火柴, 以之为边搭建 4 个等边三角形该问题易产生误导, 它暗示是一个二维空间, 为解决问题需拓展到三维对任意一个问题, 解的表示方式和它相应的解隐含了解空间及其大小 7

7 几个回溯法的例子

8 9

9 4 后问题问题 : 在 4 4 的方格棋盘上放置 4 个皇后, 使得没有两个皇后在同一行同一列也不在同一条 45 度的斜线上问有多少种可能的布局? 解是 4 维向量 :<x 1, x 2, x 3, x 4 > 解 :<2,4,1,3>, <3,1,4,2> 推广到 8 后问题解 :8 维向量, 有 92 个例如 :<1,5,8,6,3,7,2,4> 是解 10

10 搜索空间 :4 叉树 <1> <4> <2> <3> 第 1 层代表第 1 个皇后可能选择的列号 <2,4> <2,4,1> <2,4,1,3> 每个结点有 4 个儿子, 分别代表选择 1,2,3,4 列位置第 i 层选择解向量中第 i 个分量值最深层的树叶是解按深度优先次序遍历树, 找到所有解 11

11 0-1 背包问题问题 : 有 n 种物品, 每种物品的重量和价值分别为 w i, v i 如果背包的最大承重限制是 B, 每种物品至多放 1 个怎么样选择放入背包的物品使得背包所装物品价值最大? 实例 :V={12,11,9,8}, W={8,6,4,3}, B=13 最优解 :<0,1,1,1>, 价值 :28, 重量 :13 12

12 算法设计解 :n 维 0-1 向量 <x 1, x 2,..., x n > x i =1 物品 i 选入背包结点 :<x 1, x 2,..., x k >( 部分向量 ) 搜索空间 : 一棵 0-1 取值的二叉树, 称为子集树, 有 2 n 片树叶可行解 : 满足约束条件 ( 不超重 ) 的解最优解 : 可行解中价值达到最大的解 13

13 实例输入 :V={12,11,9,8}, W={8,6,4,3}, B=13 2 个可行解 : <0,1,1,1>, 价值 :28, 重量 :13 <1,0,1,0>, 价值 :21, 重量 :12 最优解 :<0,1,1,1> 14

14 搜索空间实例 :V={12,11,9,8}, W={8,6,4,3}, B=13 搜索空间 : 子集树, 2 n 片树叶 <1> <0> <1> <0> <1> <1> <0> <1> <0> <0> <1,0,1,0> 可行解 <0,1,1,1> 最优解 15

15 旅行售货员问题问题 : 一个售货员需要在 n 个城市销售商品, 已知任两个城市之间的距离, 求一条每个城市恰好经过一次的回路, 使得总长度最小建模 : 城市集 C={c 1,c 2,...,c n }, 距离 d(c i,c j )=d(c j,c i ) 求解 :1,2,...,n 的排列 k 1,k 2,...,k n 使得 n 1 min dc ( k, c ) (, ) i k dc i 1 k c n k 1 i 1 16

16 实例输入 : C={1,2,3,4} d(1,2)=5, d(1,3)= d(1,4)=4, d(2,3)=13 d(2,4)=2, d(3,4)=7 解 :<1,2,4,3>, 长度 = =23 17

17 搜索空间排列树, 有 (n-1)! 片树叶 <1> <1,2> <1,4> 3 13 <1,2,4,3> 18

18 小结问题解性质解向量搜索空间搜索方式约束条件 n 后问题 0-1 背包问题 TSP 问题特点可行解最优解最优解搜索解 <x 1, x 2,..., x n > x i : 第 i 行列号 <x 1, x 2,..., x n > x i =0/1 x i =1 选 i <k 1, k 2,..., k n > 1,2,...,n 的排列扩张部分向量 n 叉树子集树排列树树深度 / 宽度优先深度 / 宽度优先深度 / 宽度优先跳跃式遍历彼此不攻击不超过背包重量选未经过的城市约束条件回溯判定 19

19 回溯法设计思想和适用条件

20 回顾一下深度与宽度优先搜索深度优先访问顺序 : 宽度优先访问顺序 :

21 回溯法基本设计思想适用对象 : 求解搜索问题和优化问题搜索空间 : 树, 结点对应部分解向量, 可行解在树叶上搜索过程 : 采用系统的方法隐含遍历搜索树搜索策略 : 深度 / 宽度优先函数优先宽深结合结点分支判定条件 : 满足约束条件分支扩张解向量不满足约束条件回溯到该结点的父结点结点状态 : 动态生成可以约定 : 白色结点 ( 尚未访问 ) 灰色结点 ( 正在访问 ) 黑色结点 ( 该结点为根的子树遍历完成 ) 存储 : 当前路径 22

22 结点状态例子策略 : 深度优先访问次序 : 已完成访问 :2,8 已访问但未结束 :1,3,5 尚未访问 :9,6,7,

23 算法分析与设计 Analysis and Design of Algorithm Lesson 12

24 要点回顾回溯法设计要素适用对象 : 求解搜索问题和优化问题搜索空间 : 树, 结点对应部分解向量, 可行解在树叶上搜索过程 : 采用系统的方法隐含遍历搜索树搜索策略 : 深度 / 宽度优先函数优先宽深结合结点分支判定条件 : 满足约束条件分支扩张解向量不满足约束条件回溯到该结点的父结点结点状态 : 动态生成可以约定存储 : 当前路径 25

25 要点回顾回溯法的几个简单实例 n 后问题 0-1 背包问题 TSP 问题回溯法的适用条件 ( 开端 ) 26

26 回溯法适用条件在结点 <x 1, x 2,..., x k > 处 P(x 1, x 2,..., x k ) 为真向量 <x 1, x 2,..., x k > 满足某个性质 ( 约束条件 ) ( 例如 :n 后中 k 个皇后放在彼此不攻击的位置 ) 多米诺性质 P(x 1, x 2,..., x k+1 ) P(x 1, x 2,..., x k ) 0< k < n 逆否命题 : P(x 1, x 2,..., x k ) P(x 1, x 2,..., x k+1 ) 0< k < n 作用 :k 维向量不满足约束条件, 扩张向量到 k+1 维仍旧不满足, 可以回溯! 27

27 一个实例例 : 求不等式的整数解 5x 1 +4x 2 -x 3 10, 1 x k 3, k=1,2,3 P(x 1, x 2,..., x k ): 将 x 1, x 2,..., x k 代入原不等式的相应部分, 部分和小于等于 10 不满足多米诺性质 : 5x 1 +4x 2 -x x 1 +4x 2 10 变换使得问题满足多米诺性质 : 令 x 3 =3-x 3*, 那么原不等式变换为 5x 1 +4x 2 +x 3* 13 1 x 1, x 2 3, 0 x 3* 2 28

28 小结回溯法适用条件 : 多米诺性质回溯法设计步骤 1. 定义解向量和每个分量的取值范围解向量为 <x 1, x 2,..., x n > 确定 x i 的取值集合为 X i 2. 由 <x 1, x 2,..., x k-1 > 确定如何计算 x k 取值集合 S k, S k X k 3. 确定结点儿子的排列规则 4. 判断是否满足多米诺性质 5. 确定每个结点分支的约束条件 6. 确定搜索策略 : 深度优先 / 宽度优先, 确定存储搜索路径的数据结构 29

29 回溯法的实现及实例

30 回溯法两种实现递归实现算法 ReBack(k) 1. if k>n then <x 1, x 2,..., x n > 是解 2. else while S k do 3. x k S k 中最值 4. S k S k -{x k } 5. 计算 S k+1 6. ReBack(k+1) 算法 ReBacktrack(n) 输入 :n 输出 : 所有解 1. for k 1 to n 计算 X k 且 S k X k 2. ReBack(1) 31

31 回溯法两种实现迭代实现算法 Backtrack(n) 输入 :n 输出 : 所有解 1. 对于 i=1,2,...,n 确定 X i 2. k 1 3. 计算 S k 4. while S k do 确定初始取值满足约束分支搜索 5. x k S k 中最值 ;S k S k -{x k } 6. if k<n then 7. k k+1; 计算 S k 8. else <x 1, x 2,..., x n > 是解 9. if k>1 then k k-1; goto 4 回溯 32

32 装载问题问题 : 有 n 个集装箱, 需要装上两艘载重分别为 c 1 和 c 2 的轮船 w i 为第 i 个集装箱的重量, 且 w 1 +w w n c 1 +c 2 问是否存在一种合理的装载方案把这 n 个集装箱装上船? 实例 : W=<90, 80, 40, 30, 20, 12, 10> c 1 =152, c 2 =130 解 :1,3,6,7 装第一艘船, 其余第 2 艘 33

33 求解思路输入 :W=<w 1, w 2,..., w n > 为集装箱重量,c 1 和 c 2 为船的最大载重算法思想 : 令第一艘船的载入量为 W 1 1. 用回溯法求使得 c 1 -W 1 达到最小的装载方案 2. 若满足 w 1 +w w n -W 1 c 2 则回答 YES, 否则回答 NO 34

34 算法伪码算法 Loading(W,c 1 ) 1. Sort(W) 2. B c 1 ; best c 1 ; i 1 3. while i n do 4. if 装入 i 后重量不超过 c 1 5. then B B-w i ; x[i] 1; i i else x[i] 0; i i if B<best then 记录解 ; best B 8. Backtrack(i) 9. if i=1 then return 最优解 10. else goto 3 B 为当前空隙 best 为最小空隙回溯 35

35 子过程 Backtrack 算法 Backtrack(i) 1. while i >1and x[i]=0 do 2. i i-1 3. if x[i]=1 4. then x[i] 0 5. B B+w i 6. i i+1 沿右分支一直回溯发现左分支边或到根为止 36

36 实例 W=<90, 80, 40, 30, 20, 12, 10> c 1 =152, c 2 =130 解 : 可以装, 方案如下 : 1,3,6,7 装第一艘船 2,4,5 装第二艘船时间复杂度 :O(2 n )

37 图的着色问题输入 : 无向连通图 G 和 m 种颜色的集合, 用这些颜色给图的顶点着色, 每个顶点一种颜色要求是 :G 的每条边的两个顶点着不同颜色输出 : 所有可能的着色方案如果不存在着色方案, 回答 NO 38

38 实例 n=7, m=3 39

39 解向量设 G=(V, E), V={1,2,...,n} 颜色编号 :1,2,..., m 解向量 :<x 1, x 2,..., x n > x i {1,2,...,m} 结点的部分向量 <x 1, x 2,..., x k >,1 k n 表示只给顶点 1,2,...,k 着色的部分方案 40

40 算法设计搜索树 :m 叉树约束条件 : 在结点 <x 1,..., x k > 处, 顶点 k+1 的邻接表中结点已用过的颜色不能再用如果邻接表种结点已用过 m 种颜色, 则结点 k+1 没法着色, 从该结点回溯到其父节点满足多米诺性质搜索策略 : 深度优先时间复杂度 :O(n m n ) 41

41 运行实例 n=7, m={1 2 3}

42 搜索树第一个解向量 :<1, 2, 1, 3, 1, 2, 3> 43

43 时间复杂度与改进途径时间复杂度 :O(n m n ) 根据对称性, 只需搜索 1/3 的解空间当 1 和 2 确定, 即 <1,2> 以后, 只有 1 个解, 在 <1,3> 为根的子树中, 也只有一个解由于 3 个子树的对称性, 总共有 6 个解在取定 <1,2> 后, 不可扩张成 <1,2,3>, 因为 7 和 1,2,3 都相邻 7 没法着色可以从打叉的结点回溯, 而不必搜索其子树 44

44 着色问题的应用会场分配问题 : 有 n 项活动需要安排, 对于活动 i,j, 如果 i,j 时间冲突, 就说 i,j 不相容如何分配这些活动, 使得每个会场的活动相容且占用会场数最少? 建模 : 活动作为图的顶点, 如果 i,j 不相容, 则在 i 和 j 之间加一条边, 会场标号作为颜色标号求图的一种着色方案, 使得使用的颜色数最少 45

45 第五章小结理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架递归回溯最优子结构性质迭代回溯贪心选择性质子集树算法框架排列树算法框架通过应用范例学习回溯法的设计策略 n 后问题 0-1 背包问题旅行售货员问题装载问题图的着色问题 46

幻灯片 1

幻灯片 1 算法分析与设计 Analysis and Design of Algorithm 第 12 次课课程回顾贪心算法的基本概念贪心选择性质局部最优和全局最优贪心算法的应用哈夫曼编码最小生成树单源最短路径 NP 完全问题多机调度问题旅行商问题 2 第五章回溯法 3 学习要点理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架递归回溯迭代回溯子集树算法框架排列树算法框架应用范例