幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

岚燥伍
5 years ago
Views:

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

2 课程回顾 ( 回溯法概念 ) 适用对象 : 求解搜索问题和优化问题搜索空间 : 树, 结点对应部分解向量, 可行解在树叶上搜索过程 : 采用系统的方法遍历搜索树搜索策略 : 深度优先剪枝方法 : 约束函数限界函数结点分支判定条件 : 不满足剪枝条件分支扩张解向量满足剪枝条件回溯到该结点的父结点存储 : 当前路径 B A C D E F G H I J K L M N O 2

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

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

5 回溯法的几个应用 5

6 装载问题 6

7 贪心法的最优装载问题 ( 回忆 ) 有一批集装箱 {a,a 2,, a n } 要装上一艘载重量为 C 的轮船, 其中集装箱 a i 的重量为 W i 最优装载问题要求确定在装载体积不受限制的情况下, 将尽可能多的集装箱装上轮船贪心策略 : 轻者优先 7

8 装载问题及其应用有一批共 n 个集装箱要装上 2 艘载重量分别为 c 和 c 2 的轮船, 其中集装箱 i 的重量为 w i, 且 w w c c 2 w n 2 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船如果有, 找出一种装载方案 8

9 例子 : 出国旅行的装载问题 9

10 装载问题的解空间实例 : 物品的重量 W = 9,65,4,3,2,2, 旅行箱允许载重 c = 52, c 2 = 3 问题的解将物品,3,6,7 装第一个箱子 c + c 3 + c 6 + c 7 = 52 解的表示,,,,,,

11 装载问题的求解思路输入 : 物品重量 W, 旅行箱载重 c, c 2 首先将第一个旅行箱尽可能装满 ; 将剩余的物品装上第二个旅行箱将第一个旅行箱尽可能装满等价于选取全体物品的一个子集, 使该子集中物品重量之和最接近 max n i w x i i i n s.t. wi xi i x {,}, c i n

12 装载问题的解空间树一棵二叉树 ( 子集树 ), 实例物品重量 W = 9,65,4,3,2,2, c = 52, c 2 = 3 最优解 :,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, 2

13 装载问题的剪枝函数可行性约束函数 cw 限界函数有用的变量当前旅行箱内重量 :cw 当前最优解 :bestw 上界函数 : 剩余物品的重量 r = w i+ + w i w n 剪枝条件 : 若 cw + r bestw, 则剪枝 bestw 3 r

14 装载问题的剪枝函数实例物品重量 W = 9,65,4,3,2,2, c = 52, c 2 = 3 cw, 最优解 :,,,,,, bestw=52 cw= cw + r bestw 剪枝! r= =2 r bestw 4

15 装载问题的算法实现 void backtrack (int i) {// 搜索第 i 层结点 if (i > n) 更新最优解 bestx,bestw;return; r -= w[i]; if (cw + w[i] <= c) { x[i] = ; cw += w[i]; backtrack(i + ); cw -= w[i]; } if (cw + r > bestw) { x[i] = ; backtrack(i + ); } r += w[i]; } 搜索左子树搜索右子树到达叶结点 5

16 批处理作业调度问题 6

17 批处理作业调度及其应用给定 n 个作业的集合 {J,J 2,,J n } 每个作业必须先由机器处理, 然后由机器 2 处理 t ji 是作业 J i 需要机器 j 的处理时间 F i 是作业 i 的完成时间目标 : 求最佳作业调度方案使作业完成时间和最小 Web 服务器调度网络交换机的流调度 7

18 实例 : 批处理作业调度问题的解空间梅园打印店每天要处理很多打印任务, 分两步 : 将文件拷贝至电脑在打印机打印问题 : 给定一系列任务, 且任务的拷贝和打印时间已知, 请找出这些任务先后顺序, 使所有任务的总完成时间最短 t ji 拷贝打印网络作业 2 概率作业 3 算法作业 2 3 8

19 批处理作业调度问题的解空间问题的解可行解,2,3,3,2 2,,3 2,3, 3,,2 3,2, 完成时间网络作业算法作业概率作业任务拷贝打印网络作业 2 2 概率作业 3 3 算法作业

20 实例批处理作业调度问题的解空间树任务拷贝打印网络作业 2 2 概率作业 3 3 算法作业 2 3, 解空间排列树 (n=3) 剪枝函数当前方案的执行时间 > 最优解,2,

21 批处理作业调度问题的算法实现 void Backtrack(int i) { if (i > n) { 到达叶子结点当前方案的执行时间 } for (int j = ; j <= n; j++) bestx[j] = x[j]; bestf = f;} else for (int j = i; j <= n; j++) { 若不被剪枝 } f+=m[x[j]][]; f2[i]=((f2[i-]>f)?f2[i-]:f)+m[x[j]][2]; f+=f2[i]; if (f < bestf) { Swap(x[i], x[j]); Backtrack(i+); Swap(x[i], x[j]); } f- =M[x[j]][]; f- =f2[i]; M, // 各作业所需的处理时间 x, // 当前作业调度 bestx, // 当前最优作业调度 f2, // 机器 2 完成处理时间 f, // 机器完成处理时间 f, // 完成时间和 bestf, // 当前最优值 N // 作业数 2

22 两个核心问题小结定义解空间解向量为 <x, x 2,..., x n > 确定 x i 的取值集合为 X i 子集树排列树 n 叉树定义剪枝函数可行性约束函数限界函数 22

23 回溯法的剪枝技巧 23

24 两种剪枝函数可行性约束函数 2 限界函数 24

25 两种剪枝函数可行性约束函数 2 限界函数 25

26 图着色问题及其应用 ( 回顾 ) 给定无向连通图 G=(V,E), 是否可 k 种颜色对 G 中顶点着色, 可使任意两个顶点着色不同是与否的判定问题解向量 : x, x 2,, x n, x i 表示顶点 i 所着颜色地图着色程序编译器的寄存器分配算法任务调度 26

27 实例 : 给中国地图着色 A B C D E 是否可以用三种不同颜色给这个地图着色? 27

28 图的 m 着色问题的解空间树 3 着色问题三叉树 A 剪枝函数可行性约束函数 A= B=2 B C 解空间有 3 5 =243 个结点, 而回溯只搜了其中 4 个结点就找到了解 D= C=3 D=3 D E E= 28

29 两种剪枝函数可行性约束函数 2 限界函数 29

30 回溯法与组合优化问题 ( 回顾 ) 例如 :- 背包问题最大化 x + 3x 2 + 5x 3 + x 4 回溯法常用于解决组合优化问题满足约束条件 2x + 3x 2 + 6x 3 + 7x 4 x i,, i =, 2, 3, 4 组合优化问题目标函数 ( 极大化或极小化 ) 约束条件 ( 解满足的条件 ) 可行解 : 搜索空间满足约束条件的解最大化价值重量约束定义域约束最优解 : 使目标函数达极大 ( 或极小 ) 的可行解 3

31 回溯法的代价函数代价函数的计算位置搜索树的结点代价函数的值 F 代价函数 F v(x) 极大化可行解 X 对于极大化问题, 以该点为根的子树所有可行解的值的上界 ( 极小化问题为下界 ) 代价函数的性质对于极大化问题, 父结点代价不小于子结点的代价 ( 极小化问题相反 ) 3

32 回溯法的界界的含义当前得到可行解的目标函数的最大值 ( 极小化问题相反 ) 界的初值极大化问题初值为 ( 极小化问题为最大值 ) 界的更新得到更好的可行解时 F 代价函数界 B=v(x) 32

33 回溯法的剪枝函数剪枝函数不满足约束条件 ( 可行性约束函数 ) 代价函数值不优于当前的界 ( 限界函数 ) 界的更新对于极大化问题, 如果一个新的可行解的优化函数值大于 ( 极小化问题为小于 ) 当前的界, 则把界更新为该可行解的值 33

34 回溯法剪枝的实例 - 背包问题 4 种物品, 重量 w i 和价值 v i 分别为 v =, v 2 = 3, v 3 = 5, v 4 = w = 2, w 2 = 3, w 3 = 6, w 4 = 7 背包重量限制为例如 :- 背包问题最大化 x + 3x 2 + 5x 3 + x 4 满足约束条件 2x + 3x 2 + 6x 3 + 7x 4 x i,, i =, 2, 3, 4 34

35 物品 2 物品 3 v 3 = 5 w 3 = 6 物品 4 v 4 = w 4 = 7 通常的回溯法做法物品 v 2 = 3 w 2 = 3 v = w =

36 代价函数的设定按 v i /w i 从大到小排序,i =, 2,, n 假设位于结点 x, x 2,, x k 代价函数 = 已装入价值 +Δ Δ: 还可继续装入最大价值的上界 Δ= 背包剩余重量 v k+ /w k+ ( 可装 ) Δ=( 不可装 ) 36

37 实例 :- 背包问题最大化 x + 3x 2 + 5x 3 + x 4 满足约束条件 2x + 3x 2 + 6x 3 + 7x 4 x i,, i =, 2, 3, 4 对元素重新排序使得排序后 v i w i v i+ w i+ 最大化 x + 3x 2 + 5x 3 + x 4 满足约束条件 7x + 3x 2 + 6x 3 + 2x 4 x i,, i =, 2, 3, 4 37

38 实例 : 代价函数结点 x, x 2,, x k 的代价函数代价函数 = 已装入价值 +Δ Δ: 还可继续装入最大价值的上界 k F X = i= k 若对某个 j > k 有 b i= k F X = i= k v i x i + b i= v i x i 否则 ( 即放不下剩下的任一物品 ) w i x i v k+ /w k+ w i x i w j ( 即放得下某个物品 ) b: 背包容量 w i : 物品 i 重量 v i : 物品 i 价值 38

39 实例 : 改进的回溯法最大化 x + 3x 2 + 5x 3 + x 4 满足 7x + 3x 2 + 6x 3 + 2x 4 ; x i,, i =, 2, 3, 4 x = /7 v w x 2 = + 3 3/3 7 3/3 3 x 3 = x 4 = + 3 5/6 3 39

40 圆排列问题问题定义给定 n 个大小不等的圆排进一个矩形框中, 各圆与矩形框的底边相切目标 : 求有最小长度的圆排列半径 : 半径 :4 半径 :2 长度 :

41 圆排列问题的解空间实例给出三个圆,2,3 半径为,2,4 3 半径 : 2 问题的可行解圆的所有排列如,2,3,,3,2 半径 :4 半径 :2 4

42 圆排列问题的解空间树实例给出三个圆,2,3 半径为,2,4 2 3 限界函数界 : 当前最短长度的圆排列代价函数?,2,2,

43 圆排列问题的代价函数 r i : 第 i 个圆的半径 d k : 第 k- 个圆和第 k 个圆的圆心距离 x k : 原点到第 k 个圆的圆心距离 l k : 前 k 个圆排列的长度 r k r k r d k r k x k l k d n r n 43

44 圆排列问题的代价函数前 k 个圆排列的长度 :l k = x k + r k + r 排列长度 :l n = x k + d k+ + d k d n + r + r n r k r k r d k r k x k l k d n r n 44

45 圆排列问题的代价函数 d k = r k + r k 2 r k r k 2 = 2 r k r k r k r k d k 45

46 圆排列问题的代价函数估算排列长度 : l n = x k + d k+ + d k d n + r + r n = x k + 2 r k r k+ + 2 r k+ r k r n r n + r + r n x k + 2 n k r min + r min + r r min :r k, r k+, r n 中的最小值 d k = 2 r k r k 代价函数 : x k = x k + d k F X = x k + 2 n k r min + r min + r 剪枝条件 : F X bestlength 46

47 最大团问题及其应用最大团问题 (Maximum Clique Problem) 图论中经典的组合优化问题完全图 : 图中任意两顶点都有边相连子图 : 若 U 是 G 的子图, 则 G 含 U 中所有顶点和边目标 : 找出图中顶点最多的所有完全子图社会网络中的聚类分析计算机视觉 47

48 最大团问题的解空间实例个顶点, 条边问题的解顶点 2,3,4,5 构成最大团解的表示,,,,,

49 最大团问题的解空间树一棵二叉树

50 最大团问题的剪枝函数可行性约束函数剪枝条件 : 当前的解不是团假设顶点数为 n, 在第 i 层限界函数界 : 已找到的最大团的顶点数 (bestn) 代价函数 : 当前解的顶点数 (cn)+ 未检查的顶点的数目 (n-i) 剪枝条件 :cn+n-i < bestn 5

51 剪枝之可行性约束函数当前解是不是团 5

52 剪枝之限界函数 cn+n-i < bestn 52

53 最大团问题的运行实例 () 正被访问结点未被访问结点已访问结点 53

54 最大团问题的运行实例 (2) 正被访问结点未被访问结点已访问结点 54

55 最大团问题的运行实例 (3) 正被访问结点未被访问结点已访问结点 55

56 最大团问题的运行实例 (4) 正被访问结点未被访问结点已访问结点当前解不是团 56

57 最大团问题的运行实例 (5) 2 当前最大团规模为正被访问结点未被访问结点已访问结点找到一个解! 57

58 最大团问题的运行实例 (6) 2 当前最大团规模为正被访问结点未被访问结点已访问结点当前解不是团 58

59 最大团问题的运行实例 (7) 2 当前最大团规模为正被访问结点未被访问结点已访问结点 cn+n-i < bestn 59

60 最大团问题的运行实例 (8) 2 当前最大团规模为正被访问结点未被访问结点已访问结点 6

61 最大团问题的运行实例 (9) 2 当前最大团规模为正被访问结点未被访问结点已访问结点 6

62 最大团问题的运行实例 (9) 2 当前最大团规模为正被访问结点未被访问结点已访问结点共访问了 6 个结点 62

63 最大团问题的算法实现 void Clique::Backtrack(int i){ if (i > n) { for (int j = ; j <= n; j++) bestx[j] = x[j]; bestn = cn; return; } 到达叶结点 int OK = ; for (int j = ; j < i; j++) if (x[j] && a[i][j] == ) {OK = ; break;} 是否还有更好的剪枝策略? } if (OK) {x[i] = ; cn++; Backtrack(i+); x[i] = ; cn--;} 检查是不是团复杂度分析 if (cn + n - i > bestn) {x[i] = ; Backtrack(i+);} 搜索左子树最大团问题的回溯算法 backtrack 所需的计算时间为 O(n2 n ) 搜索右子树 63

64 最大团问题改进的代价函数观察右边团的特征各顶点要和其他 3 个顶点相连每个顶点的度为 3 一个结论若图中的某顶点的度小等于 n 则该顶点一定不属于规模大于 n+ 的团 64

65 最大团问题改进的代价函数合适的搜索顺序图顶点的度 : 顶点所连的边数将顶点按度从小到大排序优先检查度数较小的顶点代价函数搜索树结点所对应的图顶点的度 d i 剪枝条件 ( 选择某顶点时检查 ):d i +<bestn 65

66 优化后的运行实例 () 正被访问结点未被访问结点已访问结点 66

67 优化后的运行实例 (2) 4 2 当前解不是团 3 正被访问结点未被访问结点已访问结点 67

68 优化后的运行实例 (3) 正被访问结点未被访问结点已访问结点当前解不是团 68

69 优化后的运行实例 (4) 4 当前最大团规模为正被访问结点未被访问结点已访问结点找到一个解! 69

70 优化后的运行实例 (5) 4 当前最大团规模为正被访问结点未被访问结点已访问结点 cn+n-i < bestn 7

71 优化后的运行实例 (6) 4 当前最大团规模为正被访问结点未被访问结点已访问结点 7

72 优化后的运行实例 (7) 4 当前最大团规模为正被访问结点未被访问结点已访问结点找到一个解! 72

73 优化后的运行实例 (8) 4 当前最大团规模为正被访问结点未被访问结点已访问结点 cn+n-i < bestn 73

74 优化后的运行实例 (9) 4 当前最大团规模为正被访问结点未被访问结点已访问结点 cn+n-i < bestn 74

75 优化后的运行实例 () 4 当前最大团规模为 cn+n-i < bestn 正被访问结点未被访问结点已访问结点 75

76 优化后的运行实例 () 4 当前最大团规模为正被访问结点未被访问结点已访问结点共访问了个结点优化效果明显! 76

77 最大独立集问题 ( 最大团问题的推广 ) 最大独立集问题 (Maximal Independent Set Problem) 独立集 : 任意两顶点都没边相连的顶点集合目标 : 找出图中最大的独立集无线传感器网络 77

78 最大独立集问题的求解思路问题的解顶点 2,3,4,5 构成最大独立集解的表示,,,,, 2 3 求解思路等价于补图的最大团问题

79 提高回溯法效率的技巧对输入的序列排序 - 背包 ( 按单位价值由重自轻 ) 最大团 ( 按度数排 ) 设计精确的代价函数圆排列问题 ( 数学推导 ) 79

80 本章小结回溯法的概念一种通用的求解解法具有剪枝函数的深度优先生成法回溯法的核心问题构造解空间树 ( 子集树排列树 n 叉树 ) 设计剪枝函数 ( 可行性约束函数限界函数 ) 回溯法的应用装载问题 ; 批处理作业调度 ;n 后问题 ;- 背包问题 ; 最大团问题 ; 图的 m 着色问题 ; 旅行商问题圆排列问题 8

Microsoft PowerPoint - Chap05

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