排列树回溯算法框架 void backtrack (int t){ if (t n) output(x); } 11 15 16 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]); } 遍历排列树：O(n) } }//调用Backtrack(1)前，首先将数组x初始化为单位排列[1,2，，n]
排列树回溯算法框架 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]); } } } // 调用Backtrack(1)前，首先将数组x初始化为单位排列[1,2, ..., n] 遍历排列树：O(n!) 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
排列生成问题的回溯算法 void backtrack (int t){ 算法输出： 123 if (t n)output(x); else 132 for (int i=t;i<=n;i++) 213 swap(x[t],x[i]) 231 backtrack(t+1); 312 swap(x[t],x[i]); 321 X main(int n){ for (int i=1;i <n;i++)x[i]i backtrack(1; }
排列生成问题的回溯算法 void backtrack (int t) { if (t > n) output(x); else{ for (int i = t; i <= n; i++) { swap(x[t], x[i]); backtrack(t+1); swap(x[t], x[i]); } } } main(int n){ for (int i=1; i <= n; i++) x[i] = i; backtrack(1); } 123 132 213 231 312 321 算法输出：
回溯法的特点 @R 回溯法解题思路小结 Φ该方法的显著特征是在搜索过程中动态产生问题的解空间 Φ在任何时刻，算法只保存从根结点到当前扩展结点的路径 Φ如果解空间树中从根结点到叶结点的最长路径的长度为h(n) 则回溯法所需的内存空间通常为：O(h(n) 而显式地存储整个解空间侧需要：O(2h(n)或0(h(n))
回溯法的特点 回溯法解题思路小结 该方法的显著特征是在搜索过程中动态产生问题的解空间 在任何时刻，算法只保存从根结点到当前扩展结点的路径 如果解空间树中从根结点到叶结点的最长路径的长度为h(n) ⚫ 则回溯法所需的内存空间通常为：O(h(n)) ⚫ 而显式地存储整个解空间则需要：O(2h(n))或O(h(n)!)
回溯法的特点 @R 常用剪枝函数 约束函数：在扩展结点处剪去不满足约束的子树 Φ 限界函数：剪去得不到最优解的子树 @3 约束函数 ⊕ 回溯法要求问题的解能够表示成一个元向量形式(X1X2…,X) 显式约束：对分量X的取值范围限制 ⊕ 隐式约束：为满足问题的解而对不同分量之间施加的约束 3 限界函数(bounding function) Φ为了避免生成那些不可能产生最佳解的问题状态 要不断地利用限界函数来剔除那些不能产生所需解的活结点 具有限界函数的深度优先生成法就称为回溯法
回溯法的特点 常用剪枝函数 约束函数：在扩展结点处剪去不满足约束的子树 限界函数：剪去得不到最优解的子树 约束函数 回溯法要求问题的解能够表示成一个n元向量形式(x1 ,x2 ,…,xn ) 显式约束：对分量 xi 的取值范围限制 隐式约束：为满足问题的解而对不同分量之间施加的约束 限界函数（bounding function） 为了避免生成那些不可能产生最佳解的问题状态 要不断地利用限界函数来剔除那些不能产生所需解的活结点 具有限界函数的深度优先生成法就称为回溯法
5.2NP完全性问题简介 Introduction to NP-Complete)
5.2 NP完全性问题简介 （ Introduction to NP-Complete）