[TOC]
# 概念
回溯法有“通用解法”之称。
回溯法是一个既带有系统性，又带有跳跃性的搜索算法。
算法搜索至解空间树的任一节点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。|否则，进入该子树，继续按深度优先策略搜索。
回溯法问题求解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到一个解就可结束。
> 适用于解组合数较大的问题。
# 基本思想
* 约束条件
* 限界函数
# 步骤
* 针对所给的问题，定义问题的解空间；
* 确定易于搜索的解空间；
* 以深度优先方式搜索解空间，并在搜索的过程中用剪枝函数避免无效搜索。
#### 递归回溯
```
void backtracking(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)) Backtracking(t+1);
}
}
```
如上述代码：
t表示递归深度，即当前扩展结点在解空间树中的深度；
n用来控制递归的深度；
t>n表示已经搜索到叶节点；
此时，由Output(x)记录或者输出得到的可行解x；
backtracking的for循环中f(n,t)和g(n,t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号。
h(i)表示在当前扩展结点处x[t]的第i个可选值。
Constraint(t) 和 Bound(t)分别表示约束条件函数和限界函数，如果既没有违反约束条件，也没有违反越界函数，则递归下一层。
调用一次backtracking(1)即可以完成整个回溯的搜索过程。
#### 迭代回溯
```
void IterativeBacktrack(void) {
int t = 1;
while(t>0) {
if(f(n,t) <= g(n,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--;
}
}
```
> 用回溯法解题的一个显著特征是在搜索的过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。
# 子集树和排列树
* 子集树：当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。（0-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);
}
}
```
* 排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。（旅行售票员问题）
搜索排列树的一般算法：
```
void Backtrack(int t) {
if(t>n) Output(x);
else
for(int i=t;i<=n;i++) {
Swap(x[t],x[i]); //So smart
if(Constraint(t) && Bound(t)) Backtrack(t+1);
Swap(x[t],x[i]);
}
}
```
在调用backtrack(1)执行回溯搜索之前，先将变量数组x初始化为单位排列(1,2,3,...,n)。
* Swap(x[t],x[i])的含义：
如在旅行售票员问题中，假设默认x=[1,2,3,4]，其执行过程如下
backtrack(1) : t = 1;
for 中 i = 1;
swap(x[1],x[1]),即从1开始
backtrack(2) : t = 2;
for 中 i = 2,n=4;
swap(x[2],x[2])，考察2结点，如果不行，swap(x[2],x[3])，x数组变为x=[1,3,2,4],现在考察3结点。依次向下搜索。
