以深度优先的方式系统地搜索问题的解的方法称为回溯法。 可以系统地搜索一个问题的所有解或任意解。 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。 问题的解空间 应用回溯法求解时，需要明确定义问题的解空间。 问题的解空间应至少包含问题的一个（最优）解。 例如，对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成，该解空间包含了对变量的所有可能的0-1赋值。 解空间的特点： （完全）二叉树. 问题的解是一棵子树（一条路） 通过深度优先搜索获得最优解 **6.1.2 回溯法的基本思想 **在生成解空间树时，定义以下几个相关概念： 活结点： 如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。 扩展结点： 当前正在生成其儿子结点的活结点叫扩展结点（正扩展的结点）。 死结点： 不能再进一步扩展或者其儿子结点已全部生成的结点就是死结点。 回溯从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。 开始结点(根结点)成为第一个活结点，同时成为当前的扩展结点。 在当前的扩展结点，搜索向深度方向进入一个新的结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。 若在当前扩展结点处不能再向深度方向移动，则当前的扩展结点成为死结点，即该活结点成为死结点。 此时回溯到最近的一个活结点处，并使得这个活结点成为当前的扩展结点。 回溯法以这样的方式递归搜索整个解空间（树），直至满足中止条件。
在回溯法搜索解空间树时，通常采用两种策略（剪枝函数）避免无效搜索以提高回溯法的搜索效率： 用约束函数在扩展结点处剪去不满足约束条件的子树； 用限界函数剪去不能得到最优解的子树。 解0—1背包问题的回溯法用剪枝函数剪去导致不可行解的子树。 解旅行商问题的回溯算法中，如果从根结点到当前扩展结点的部分周游路线的费用已超过当前找到的最好周游路线费用，则以该结点为根的子树中不包括最优解，就可以剪枝。
例6.1 0 —1背包问题 假设背包容量C＝30，w＝{16，15，15}，v＝{45，25，25} 6.1.3 子集树与排列树 有时问题是要从一个集合的所有子集中搜索一个集合，作为问题的解。或者从一个集合的排列中搜索一个排列，作为问题的解。 回溯算法可以很方便地遍历一个集合的所有子集或者所有排列。 当问题是要计算n个元素的子集，以便达到某种优化目标时，可以把这个解空间组织成一棵子集树。 例如，n个物品的0-1背包问题相应的解空间树就是一棵子集树。 这类子集树通常有2n个叶结点，结点总数为2n +1-1。 遍历子集树的任何算法，其计算时间复杂度都是Ω(2n)。 6.2 装载问题 可行性约束函数可剪去不满足约束条件的子树：
令cw(t)表示从根结点到第t层结点为止装入轮船的重量，即部分解(x1, x2 , …, xt)的重量：
当cw(t)>c时，表示该子树中所有结点都不满足约束条件，可将该子树剪去。
#include <iostream> using namespace std; class goods{ int weight; public: goods(int w=0):weight(w) {} int get_w(){ return weight; } void set(int w){ weight=w; } }; void load(goods *g, int *x, int t, int n,int cw, int &bestcw ,int *best,int r,int c){ if(t>n) { //已经遍历的到叶子结点，得到了一个解决方案 if(cw>bestcw) { for(int i=0;i<n;i++) best[i]=x[i]; bestcw=cw; } } else{ //每个结点可以有两个分支，分别利用约束规则和限界规则进行剪枝 r=r-g[t].get_w();//剩余未处理的物品的重量和，与是否选取当前物品无关 if(cw+g[t].get_w()<=c){ // 根据题意中的约束条件进行剪枝 x[t]=1; cw=cw+g[t].get_w(); //当前装入的物品的重量和 load(g,x,t+1,n,cw,bestcw,best,r,c); cw=cw-g[t].get_w(); //回溯的需要 } if(cw+r>bestcw) { //限界规则 x[t]=0; load(g,x,t+1,n,cw,bestcw,best,r,c); } r=r+g[t].get_w(); //回溯的需要 } }6.8 子集和问题 子集和问题的一个实例为＜S，c＞。其中，S＝{w1, w2, …, wn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1的和为c。 编程任务：对于给定的正整数集合S＝{w1, w2, …, wn}和正整数c，编程计算S的一个子集S1，使得S1的和为c。 #include using namespace std; class Sum { int n; //集合中数据的个数 int *x;//解向量，当x[i]=1表示第i 个元素属于子集，否则，x[i]=0; int c;//输入的条件 int s;//正在构造的子集中元素的和 int *set;//集合 int r;//不再子集中的其他数据元素之和； int total;//记录符合条件的子集的个数 public: Sum(int n=0,int c=0); void calculate(int t); void display(); int get_T(){ return total; } }; #include using namespace std; class Sum { int n; //集合中数据的个数 int *x;//解向量，当x[i]=1表示第i 个元素属于子集，否则，x[i]=0; int c;//输入的条件 int s;//正在构造的子集中元素的和 int *set;//集合 int r;//不再子集中的其他数据元素之和； int total;//记录符合条件的子集的个数 public: Sum(int n=0,int c=0); void calculate(int t); void display(); int get_T(){ return total; } };
