回溯法 | Nice To Meet U

**回溯法（Backtracking）：基本做法是搜索，是一种避免不必要搜索的穷举式搜索法。

有”通用的解题法“之称
按深度优先策略，从根结点出发搜索解空间树
根据剪枝函数来避免无用搜索

回溯法设计过程：

确定问题的解空间
- 常见解空间：排列树和子集树
确定结点的扩展规则
搜索解空间

N 皇后问题

要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相攻击。皇后能吃掉同一行、同一列、同一对角线的任意棋子。

暴力法求解需遍历 $C_{n^2}^n$ 种可能，过于庞大，因此使用回溯法可以大量地剪掉那些不必要的搜索。

这里以八皇后问题为例，设八个皇后为 x_i，分别在第 i 行，因此解可以用一个 8 个单位的数组表示。

问题的解空间：(x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈)，共有 8⁸ 个可能，是一棵排列树

约束条件：可以整合成： $|x_i-x_j| \neq |i-j|$ and $x_i \neq x_j$

不在同一列： $x_i \neq x_j$ ；不在同一主对角线上： $x_i-i \neq x_j-j$ ；不在同一负对角线上： $x_i+i \neq x_j+j$

bool check(int a[], int n) {
	for (int i = 1; i <= n-1; i++)
		if abs(a[i]-a[n]) == abs(i-n) or a[i]=a[n]
			return false;
	return true;
}

使用递归的实现：

int main(){
	backtrack(1);
}
void backtrack(int k) {
	if (k > n)
		找到解，输出结果;
	else
		for (int i=1; i <= n; i++) {
			a[k] = i;
			if (check(a, k))
				backtrack(k + 1);
            // 由于先将 a[k] 赋值，因此回溯前无需清理工作
		}
}

01背包问题

解空间：x[n] 数组，表示第 i 个物品是否选择，是一棵子集树

剪枝函数：

curWeight + w[i] > W，背包装不下则剪去左子树
rest + curValue <= bestValue，剩余价值加上当前价值都小于最优解，因此剪去右子树

backtrack(int k) {
	if (k > n)
		得到一个解，输出并返回；
	rest -= values[k];
	// 左子树
	if (curWeight + weights[i] < W) {
	        curValue += values[k];
            curWeight += weights[k];
            backTrack(k+1);
            curValue -= values[k];
            curWeight -= weights[k];
	}
	// 右子树
	if (curValue + rest > curBest)
		backTrack(k+1);
	rest += values[k];
}

时间复杂度： $O(n*2^n)$

子集和

解空间：是否选择当前数字，是一棵子集树

剪枝函数：

sum + W[k] = M，则为一个解
sum + W[k] + W[k+1] <= M，进入左子树
sum + rest - W[k] >= M and sum + W[k+1] <= M，进入右子树

TSP

解空间：给出n个点，以0为起点，构造一个排列树，共有(n-1)!的叶子结点，每次选择剩下的元素中的一个，从根到叶结点表示一条可选路径

剪枝条件：

判断当前路径是否连通，连通继续，不连通剪掉
判断当前路径是否比已经求得的路径小，小于继续，大于等于剪掉

估值&检查机制

好的机制能显著地减少所生成的结点数
但往往计算量大
折衷问题：“剪枝”节约的 vs.估值检查机制消耗的

回溯算法的效率很大程度依赖于：

产生一个 x[k] 的时间
过程中经过检查的x[k]的个数
计算估值(约束)函数的时间代价

递归的算法框架

int a[n]; // 解的表达式形式
void backtrack(int k) {
	if (k > n)
		获得一个解，输出;
	else
		for (i = 下界; i <= 上界; i++) {
			if (check(i)) {
				a[k] = i;
				backtrack(k+1); // 深度搜索子树
			}
			// 回溯前的清理工作，比如将 a[k] 置为空
		}
}