归本程子末军 5.15子集树与排列树 SHANDONG UNIVERSITY OF TECINOLOGY 3会合实的六会a空会 ● 当所给问题是从个元素的集合S中找出满 足某种性质的子集时，解空间为子集树。 ●当所给问题是从n个元素的集合S中找出满 足某种性质的排列时，解空间为排列树。 2025年4月3日 26
2025年4月3日 26 5.1.5 子集树与排列树 ⚫当所给问题是从n个元素的集合S中找出满 足某种性质的子集时，解空间为子集树。 ⚫ 当所给问题是从n个元素的集合S中找出满 足某种性质的排列时，解空间为排列树
归东程子末军 5.1.5子集树与排列树 SHANDONG UNIVERSITY OF TECINOLOGY B B E 0 2 3 (D G G H 0 (I T2 3 M过 4 Q 遍历子集树需O(2)计算时间 遍历排列树需 更换排列顺序当 void backtrack(int t) void backtrack 前的第一个元素和 下面的交换 if (t>n)output(x); if(t>n)output( else else for (int i=0;i<=1;i++){ for (int i=t;i<+){ [t]=i swap(x[t],xfil): if(constraint(t)&&bound(t))backtrack(t+1); if(constrail 搜索完毕后恢复 backtrack( } swap(x[t],); 2025年4月3日 27
2025年4月3日 27 遍历子集树需O(2n )计算时间 遍历排列树需要O(n!)计算时间 void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (constraint(t)&&bound(t)) backtrack(t+1); } } void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (constraint(t)&&bound(t)) backtrack(t+1); swap(x[t], x[i]); } } 5.1.5 子集树与排列树 //更换排列顺序 当 前的第一个元素和 下面的交换 //搜索完毕后恢复
山东程子太军 SHANDONG UNIVERSITY OF TECHNOLOOY ●对于=4的旅行售货员问题（TSP)，其解空间树如下图 所示。叶子结，点代表该问题的可能解，例如结点5代表一 个可能解，路径为1→23→4→1，长度为各边代价之和。 18 24 3 2 3 8 13 19 24 29 35 40 45 50 5⑤ 60 42/43 3/41/ 1 32 41 2 3/ 21 3 2 ④)6)9)①1④6②0222⑤2⑦30236384①434648①③⑤68①③ 342 234 34131 4241 2 1 2 3 2 5)⑦1⑩12⑤17①232628313337394②4④4⑦492⑤④⑦9626④ =4的TSP问题的解空间树 2025年4月3日 28
2025年4月3日 28 ⚫ 对于n=4的旅行售货员问题（TSP），其解空间树如下图 所示。叶子结点代表该问题的可能解，例如结点5代表一 个可能解，路径为1→2→3→4→1，长度为各边代价之和。 2 4 3 4 2 2 3 4 3 4 1 3 1 4 2 4 1 2 1 2 3 3 1 2 1 3 4 2 4 3 42 3 4 1 4 1 3 2 4 1 4 1 2 3 2 1 3 1 2 1 3 4 1 2 4 1 2 3 n=4的TSP问题的解空间树 5 7 10 12 15 17 21 23 26 28 31 33 37 39 42 44 47 49 52 54 57 59 62 64 4 6 9 11 14 16 20 22 25 27 30 32 36 38 41 43 46 48 51 53 56 58 61 63 3 8 13 19 24 29 35 40 45 50 55 60 2 18 34 24 1 1 2 3 4 3 4
归东程子末军 SHANDONG UNIVERSITY OF TECINOLOGY 5.1.6回溯法的求解过程 会会是会会8会 )针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (③)深度优先搜索解空间，并在搜索中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。 需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造 一棵真正的树结构。在任何时刻，算法只保存从根结点到当前扩展结点 的路径。如果解空间树中从根结点到叶结点的最长路径的长度为()，则 回溯法所需的计算空间通常为O()。而显式地存储整个解空间则需要 O(2h()或O(h())内存空间。 2025年4月3日 29
2025年4月3日 29 5.1.6 回溯法的求解过程 (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3) 深度优先搜索解空间，并在搜索中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。 需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造 一棵真正的树结构。在任何时刻，算法只保存从根结点到当前扩展结点 的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则 回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要 O(2 h(n))或O(h(n)!)内存空间
山东程子太军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 一、} 回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题 2025年4月3日 30
2025年4月3日 30 提纲 一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题