幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

竹胃廖
5 years ago
Views:

1 算法分析与设计 Analysis and Design of Algorithm 第 12 次课

2 课程回顾贪心算法的基本概念贪心选择性质局部最优和全局最优贪心算法的应用哈夫曼编码最小生成树单源最短路径 NP 完全问题多机调度问题旅行商问题 2

3 第五章回溯法 3

4 学习要点理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架递归回溯迭代回溯子集树算法框架排列树算法框架应用范例装载问题 ; 批处理作业调度 ; 符号三角形问题 ;n 后问题 ;0-1 背包问题 ; 最大团问题 ; 图的 m 着色问题 ; 旅行售货员问题 4

5 例子 :0-1 背包问题问题 : 有 n 种物品, 每种物品的重量和价值分别为 w i, v i 如果背包的最大承重限制是 B, 每种物品至多放 1 个怎么样选择放入背包的物品使得背包所装物品价值最大? max n i 1 n v i x i w x B i i i 1 i {0,1},1 x i n 5

6 解空间树与剪枝动态规划法的剪枝策略考虑的搜索空间中子问题的重叠性贪心算法的剪枝策略以贪心选择策略为依据, 遍历搜索空间的部分分支 m[2][10] m[1][10] m[2][8] m[3][10] m[3][8] m[3][8] m[3][6] m[4][10] m[4][4] m[4][8] m[4][2] m[4][6] m[4][0] m[5][10] m[5][5] m[5][4] m[5][8] m[5][3] m[5][2] m[5][6] m[5][1] m[5][0] 0-1 背包问题的搜索空间 6

7 什么是回溯法一种通用的解法将问题建模为解空间树深度优先搜索搜索过程中剪枝适合解组合数相当大的问题 m[1][10] m[2][10] m[2][8] m[3][10] m[3][8] m[3][8] m[3][6] m[4][10] m[4][4] m[4][8] m[4][2] m[4][6] m[4][0] m[5][10] m[5][5] m[5][4] m[5][8] m[5][3] m[5][2] m[5][6] m[5][1] m[5][0] 7

8 回溯法的两个核心问题 1 如何构建解空间树? 2 如何设计剪枝函数? 8

9 回溯问题的解空间对 n 个物品的 0-1 背包问题可能解由一个不等长向量组成解向量的长度等于装入背包的物品个数如 n=3, 解空间 {( ),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)} 可能解由一个等长向量 {x 1,, x n } 组成 x i 表示是否放入物品 i 如 n=3, 解空间为 {(0,0,0), (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,1,1)} 9

10 回溯问题的解空间问题的解向量 : n 元式 (x 1,x 2,,x n ) 的形式显约束 : 对分量 x i 的取值限定隐约束 : 为满足问题的解而对不同分量之间施加的约束解空间 : 满足显式约束条件的所有多元组 10

11 回溯问题的解空间树解空间树问题的解空间的表示方式第 0 层为初始状态第 k 层为第 k 个分量做出选择后到达的状态从树的根节点到叶子节点的路径 B A 1 0 C D E F G H I J K L M N O n=3 时的 0-1 背包问题的解空间树 11

回溯问题的解空间树 (0-1 背包问题 ) 表示解 (0,1,1) 即选物品 2 和物品 3, 不选物品 1 B A 1 0 C 1 0 1 0 D E F G 1 0 1 0 1 0 1 0 H I J K L M

12 回溯问题的解空间树 (0-1 背包问题 ) 表示解 (0,1,1) 即选物品 2 和物品 3, 不选物品 1 B A 1 0 C D E F G H I J K L M N O 对物品 1 的选择对物品 2 的选择对物品 3 的选择 n=3 时的 0-1 背包问题的解空间树树中第 i 层与第 i+1 层节点之间的边上给出了对物品 i 的选择结果,8 个叶子代表 8 个可能解 12

13 解空间树的生成方法深度优先基于深度优先搜索英文缩写为 DFS 即 Depth First Search 对每一个可能的分支路径深入到不能再深入为止, 而且每个节点只能访问一次 B A 1 0 C D E F G H I J K L M N O 13

14 解空间树的生成方法广度优先基于广度优先搜索 ( 第六章分支限界算法 ) 英文缩写为 BFS 即 Breadth First Search 从根开始, 辐射状地优先遍历其周围较广的区域, 而且每个节点只能访问一次 B A 1 0 C D E F G H I J K L M N O 14

15 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 15

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

17 实例输入 :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> 17

18 搜索空间实例 :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> 最优解 18

19 回顾 : 旅行商问题旅行商问题 (Travelling Salesman Problem,TSP): 旅行家旅行 n 个城市, 要各城市经历且经历一次, 然后回到源点, 求出最短路程规划快递线路电路板钻洞 DNA 测序 19

20 旅行商问题的描述问题 : 一个旅行商需要在 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 d( ck, c ) (, ) i k d c i 1 k c n k 1 i 1 20

21 旅行商问题的应用 : 快递小哥送货从计算机楼出发, 如何规划线路, 使得总路程最少? 经管楼 940 桃园宿舍计算机楼梅园宿舍 21

22 实例输入 : C={ 计算机楼, 经管楼, 桃园, 梅园 } 计经桃梅计经桃梅最优解 :<1, 2, 3, 4>, 距离矩阵长度 = =3235 经管楼 625 计算机楼桃园宿舍 900 梅园宿舍 22

23 搜索空间解空间树 <1,2> A B C D E F G H I J K L M N O P <1,2,3,4> <1> <1,4> 思考 : 如果有 5 个地点, 解空间有多大? 经管楼 625 计算机楼旅行商问题的解空间树有 (n-1)! 片树叶桃园宿舍 900 梅园宿舍 23

24 子集树与排列树 B A 1 0 C D E F G H I J K L M N O 子树集 (subset trees): 从 n 个元素中找出满足某种性质子集, 相应解空间为子集树如 0-1 背包问题 void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } 时间复杂度通常各节点有相同数目子树, 记为 C C=2 时, 子集树中共有 2 n 个叶子, 因此需要 O(2 n ) 时间 24

25 子集树与排列树排列树 (permutation trees) 当所给问题是确定 n 个元素满足某种性质的排列时如旅行商问题时间复杂度第 1 层每个节点有 n 个子节点第 2 层每个节点有 n-1 个子节点第 n 层每个节点有 1 个子点有 n! 个叶子节点, 需时间 O(n!) A B C D E F G H I J K L M N O P void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } } 25

26 回溯法的时间复杂度时间复杂度子集树 : O(2 n ) 排列树 :O(n!) 蛮力穷举法, 最坏时间复杂性不可指望通用性强平均时间性能较好需设计较好的剪枝函数 26

27 回溯法的基本思想 27

28 回溯法的基本思想问题的求解方式定义整个解空间完成确定易于搜索的解空间结构深度优先方式遍历解空间并剪枝回溯法是具有剪枝函数的深度优先生成法应包括所有的可能解 B A 1 0 C D E F G H I J K L M N O 28

29 回溯法的例子例 :n=3 的 0-1 背包问题, 重量 {20, 15, 10} 价值 {20, 30, 25} 背包容量为 25 深度优先遍历 A B 选物品 1, 则容量为 5, 价值为 20; B D, 因为选物品 2 放不下, 对以 D 为根的子树剪枝 ; 从 D 回溯到 B, 选右子树 E, 不选物 2, 价仍然为 20; E J, 选物 3 放不下, 所以以 J 为根的子树剪枝 ; 从 J 回溯到 E, 再由 E K,K 不需容量, 构成一个可行解 (1,0,0), 29 价为 20 B A 1 0 C D E F G H I J K L M N O

30 剪枝的基本思想在搜索至树上任意一点时判断是否满足约束条件是否包含问题的 ( 最优 ) 解不包含跳过对以该节点为根的子树的搜索, 剪枝 (pruning) 包含进入以该节点为根的子树, 继续按深度优先搜索 30

31 剪枝的基本思想在搜索至树上任意一点时判断是否满足约束条件是否包含问题的 ( 最优 ) 解两种用于剪枝的函数约束函数 : 用约束条件剪去得不到可行解的子树限界函数 : 用目标函数剪去得不到最优解的子树利用剪枝函数可避免无效搜索, 使算法无需搜索整个搜索树 31

32 回溯法算法框架递归回溯递归形式 void backtrack (int t) { if (t>n) output(x); else } for (int i=f(n, t); i<=g(n, t);i++) { x[t]=h(i); } 到达叶子节点, 输出结果 if (constraint(t)&&bound(t)) backtrack(t+1); B A 1 0 C D E F G H I J K L M N O 剪枝函数 f(n, t): 第 t 层未搜索过子树的起始编号 g(n, t): 第 t 层未搜索过子树的终止编号 32

33 void iterativebacktrack (){ int t=1; while (t>0) { if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else {t++;break;} }} else t--; } } 迭代回溯非递归的迭代形式 B A 1 0 C D E F G H I J K L M N O 剪枝函数到达叶子节点, 输出结果 f(n, t): 第 t 层未搜索过子树的起始编号 g(n, t): 第 t 层未搜索过子树的终止编号 33

34 回溯法的空间复杂度回溯法的存储特点动态产生问题的解空间只保存从根结点到当前扩展结点的路径空间复杂度根到叶子的最长路径的长度为 h(n) 空间复杂性通常为 O(h(n)) 显式地存储整个解空间则需要 O(2 h(n) ) 或 O(h(n)!) 34

35 回溯法与其他算法比较保证算法高效性的机制动态规划 : 避免计算重叠子问题贪心算法 : 只考虑局部最优解回溯法 : 利用剪枝函数 B A 1 0 C D E F G H I J K L M N O 动态规划的特点重叠子问题 35

36 回溯法与其他算法比较保证算法高效性的机制动态规划 : 避免计算重叠子问题贪心算法 : 只考虑局部最优解回溯法 : 利用剪枝函数 B A 1 0 C D E F G H I J K L M N O 贪心算法的特点 36

37 回溯法与其他算法比较保证算法高效性的机制动态规划 : 避免计算重叠子问题贪心算法 : 只考虑局部最优解回溯法 : 利用剪枝函数 B A 1 0 C D E F G H I J K L M N O 回溯法的特点 37

38 n 皇后问题 38

39 国际象棋皇后的走法又称皇后走法是横直斜走均可, 格数不限, 但不可越过其他棋子吃子和走法相同 39

40 n 皇后问题及其应用在一个 n n 的方格内放置 n 个皇后, 使得没有两个皇后在同一行同一列也不在同一条 45 度的斜线上问有多少种可能的布局? 并行内存系统的存储模式超大规模集成电路设计检测程序中的死锁问题 40

41 n 皇后问题的解空间当 n=4 时解是 4 维向量 x 1, x 2, x 3, x 4 解 : 2,4,1,3, 3,1,4,2 当 n=8 时解是 8 维向量, 有 92 个解例如 : 1,5,8,6,3,7,2,4 是解 41

42 n 皇后问题的解空间树一棵 n 叉树 ( 假设 n=4) ,4 树的特点 : 每个节点有四个子节点, 表示选择 1,2,3,4 四个位置第 i 层选择表示解向量中第 i 个分量的值最深层的叶子是解按深度优先次序遍历树, 找到所有解 2,4,1 2,4,1,3 42

43 n 皇后问题的算法实现 bool Queen::Place(int k) { for (int j=1;j<k;j++) if ((abs(k-j)==abs(x[j]-x[k])) (x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t) { if (t>n) sum++; else for (int i=1;i<=n;i++) { x[t]=i; if (Place(t)) Backtrack(t+1); } } 43

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

45 回溯法适用问题分析问题解性质解描述向量搜索空间搜索方式约束条件 n 皇后可行解 0-1 背包最优解旅行商最优解 x 1, x 2,, x n x i : 第 i 行列号 x 1, x 2,, x n x i {0,1} k 1, k 2,, k n 1,2,, n 的排列 n 叉树深度优先搜索彼此不攻击子集树排列树深度优先搜索深度优先搜索不超过总重量选没有经过的城市特点搜索解向量, 不断扩张部分向量树跳跃式遍历约束条件, 回溯判定 45

Microsoft PowerPoint - Chap05

Microsoft PowerPoint - Chap05 第五章回溯法 2 学习要点理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架递归回溯最优子结构性质迭代回溯贪心选择性质子集树算法框架排列树算法框架通过应用范例学习回溯法的设计策略 n 后问题 0-1 背包问题旅行售货员问题装载问题图的着色问题 3 回溯法概述回溯法有许多问题, 当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时, 往往要使用回溯法回溯法的基本做法是搜索,