回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走，能进则进，不能进则退回来，换一条路再试
1、有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法
2、回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题
3、回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索
1、定义一个解空间，它包含问题的解
2、利用适于搜索的方法组织解空间
3、利用深度优先法搜索解空间
4、利用限界函数避免移动到不可能产生解的子空间
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性
•问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式
•显约束：对分量xi的取值限定
•隐约束：为满足问题的解而对不同分量之间施加的约束
•解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间
注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）
n=3时的0-1背包问题用完全二叉树表示的解空间：
n=3时的0-1背包问题用完全二叉树（子集树）表示的解空间
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法
(1)针对所给问题，定义问题的解空间
(2)确定易于搜索的解空间结构
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
常用剪枝函数：
约束函数：在扩展结点处剪去不满足约束的子树
限界函数：剪去得不到最优解的子树。
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间
回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法
// 针对N叉树的递归回溯方法 void backtrack (int t) { if (t > n) { output (x);//到达叶子节点，输出结果 } else { // 遍历结点t的所有子结点 for (int i = f (n, t); i <= g (n, t); i++) { x[t] = h (i);//每个子节点的值赋值给x //满足约束条件和限界条件 if (constraint (t) && bound (t)) { backtrack (t + 1);//递归下一层 } } } }采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程
// 针对N叉树的迭代回溯方法 void iterativeBacktrack () { int t=1; while (t>0) { if (f(n,t)<=g(n,t)) { // 遍历结点t的所有子结点 for (int i = f (n, t); i <= g (n, t); i++) { x[t] = h (i); // 剪枝 if (constraint (t) && bound (t)) { // 找到问题的解，输出结果 if (solution (t)) { output (x); } else t++;// 未找到，向更深层次遍历 } } } else t--; } }回溯发解决问题的关键在于如何定义问题的解空间，转化成树（即解空间树），解空间树分为两种：子集树和排列树
遍历子集树需O(2n)计算时间
void backtrack (int t) { if (t>n) { // 到达叶子结点 output(x); } else { for (int i = 0; i <= 1; i++) { x[t] = i; // 约束函数 if (legal (t)) { backtrack (t + 1); } } } }遍历排列树需要O(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]); } }
