递割归回溯：通用算法框架 @R 回溯法对解空间作深度优先搜索 因此在一般情况下用递归方法实现回溯法 void backtrack(intt){h(i)表示在当前扩展结点处 if (t n){ x[t]的第i个可选值 output(x); f(,t)表示在当前扩展结点处未搜索过的子树的起始编号 else{g(n,t)表示在当前扩展结点处未搜索过的子树的终止编号 for (int i f(n,t);i <g(n,t);i++){ x[t]=h(i); if (constraint(t)&&bound(t)) backtrack(t+1); constraint(t)为true表示 在当前扩展结点处×[1：t]的取值满足问题的约束条件 bound(t)为true表示 在当前扩展结点处x[1:t]的取值尚未导致目标函数越界
递归回溯：通用算法框架 回溯法对解空间作深度优先搜索 因此在一般情况下用递归方法实现回溯法 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); } } } } h(i)表示在当前扩展结点处 x[t]的第i个可选值 f(n, t)表示在当前扩展结点处未搜索过的子树的起始编号 g(n, t)表示在当前扩展结点处未搜索过的子树的终止编号 constraint(t)为true表示 在当前扩展结点处x[1:t]的取值满足问题的约束条件 bound(t)为true表示 在当前扩展结点处x[1:t]的取值尚未导致目标函数越界
两类常见的解空间树 RR 用回溯法解题时常用到两种典型的解空间树：子集树与排列树 3第一类解空间树：子集树 当问题是：从个元素的集合S中找出满足某种性质的子集时 Φ相应的解空间树称为子集树，例如个物品的0/1背包问题 这类子集树通常有2n个叶结点 解空间树的结点总数为2n+1-1 遍历子集树的算法需2(2)计算时间 @R 第二类解空间树：排列树 ⊕ 当问题是：确定个元素满足某种性质的排列时 Φ相应的解空间树称为排列树，例如旅行商问题 排列树通常有n!个叶结点 因此遍历排列树需要2(n!)计算时间
两类常见的解空间树 用回溯法解题时常用到两种典型的解空间树：子集树与排列树 第一类解空间树：子集树 当问题是：从n个元素的集合S中找出满足某种性质的子集时 相应的解空间树称为子集树，例如n个物品的0/1背包问题 ⚫ 这类子集树通常有2n个叶结点 ⚫ 解空间树的结点总数为2n+1-1 ⚫ 遍历子集树的算法需Ω(2n)计算时间 第二类解空间树：排列树 当问题是：确定n个元素满足某种性质的排列时 相应的解空间树称为排列树，例如旅行商问题 ⚫ 排列树通常有n！个叶结点 ⚫ 因此遍历排列树需要Ω(n!)计算时间
子集树标例：0/1背包问题 3 设：n=3,W=(16,15,15),V=(45,25,25),c=30 1.定义解空间：X={0,0,0),(0,0,1),(0,1,0),（1,1,0),（1,1,1)} 2.构造解空间树如图 3.从A出发按DFS搜索 1 K (1,1,1)（1,1,0)（1,0,1)（1,0,0)(0,1,1)0,1,0) (0,0,1)(0,0,0) 可行解的值：45 50 25 25 最优解：x=(0,1,1) 最优值：m=50
子集树示例： 0/1背包问题 设：n=3, w=( 16, 15, 15), v=( 45, 25, 25), c=30 1. 定义解空间：X={(0,0,0), (0,0,1), (0,1,0),…, (1,1,0), (1, 1, 1) } 2. 构造解空间树如图 3. 从A出发按DFS搜索 可行解的值： 45 50 25 25 0 最优解： x = (0, 1, 1) 最优值：m = 50 C 1 B D H I E J K F L M G N O A 0 1 0 1 0 1 0 1 0 1 0 1 0 (1,1,1) (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0)
子集树回溯算法框架 void backtrack (int t){ if (t n) output(x); } else /对当前扩展结点的所有可能取值进行枚举 for (inti=O;i<=1;i++ x[t]i; if (constraint(t)&&bound(t))backtrack(t+1); } 遍历子集树：O(2n) } }/执行时，从Backtrack(1)开始
子集树回溯算法框架 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); } } } 1 0 1 0 1 0 1 0 1 0 1 0 1 0 遍历子集树：O(2n) // 对当前扩展结点的所有可能取值进行枚举 // 执行时，从Backtrack(1)开始
排列生成问题 RR 通过排列生成问题帮助理解排列树回溯算法框架 @3 问题定义：给定正整数n,要求生成1,2，，n的所有排列 3 示例：n=3,解空间树如下图所示 2 4 8 11 12 13 14 15 16
排列生成问题 通过排列生成问题帮助理解排列树回溯算法框架 问题定义：给定正整数n，要求生成1, 2, …, n的所有排列 示例：n=3，解空间树如下图所示 2 3 4 1 2 3 1 3 2 1 3 1 2 5 11 3 12 6 2 13 7 3 14 8 1 10 16 1 15 9 2