一、回溯介绍
1、概念
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯法适用于复杂的，规模较大的问题有“通用解题方法”的美称。
有许多问题，当需要找出它的解集 或者 要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法
- 解向量:希望问题的解 能够表示成一个 n 元式(x1, x2, …, xn)的形式。
- 解空间:对于问题的一个实例，满足显式约束条件的所有解向量，构成了该实例的一个解空间。
- 显约束:对分量 xi 的取值限定。
- 隐约束:为满足问题的解 而对不同分量之间施加的约束。
- 扩展结点：正在产生儿子的结点
- 活结点：自身已生成，但其儿子还没有全部生成的结点
- 死结点：所有儿子 已经产生的结点
- 深度优先生成法：扩展结点1，一旦产生了它的一个儿子2，就把结点2当做新的扩展结点。在完成 以2为根的子树 的穷尽搜索之后，将结点1重新变成扩展结点，继续产生结点1的下一个儿子
- 宽度优先生成法：在一个扩展结点变成死结点之前，它一直是扩展结点
当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树
当所给问题的确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。
回溯法就是具有剪枝函数的深度优先生成法
2、基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
3、效率
子集树：结点数目 mn，计算时间 O(mn)
排列树：结点数目 n!，计算时间 O(n!)
回溯法的效率在很大程度上依赖于以下因素：
- 产生 扩展结点x[k]的时间；
- 满足显约束的扩展结点x[k]值的个数；
- 剪枝时间：计算 可行性约束函数 和 上界函数 的时间；
- 满足可行性约束函数和上界函数的 所有扩展结点x[k]的个数。
好的剪枝函数，能显著地减少所生成的结点数。但是，这样的剪枝函数往往计算量较大。因此，选择剪枝函数时，通常存在生成结点数与剪枝函数计算量之间的折衷。
4、用回溯法解题的一般步骤：
（1）针对所给问题，确定问题的解空间：
首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定易于搜索的解空间结构（排列树、子集树)
子集树：从元素中选哪几个，排列树：所需元素都要有，选一种排列
（3）从根节点以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
- 用约束函数在扩展结点处剪去不满足约束条件的子树；
- 用限界函数剪去得不到最优解的子树。
5、算法框架
（1）问题框架
设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。
