回溯法

搜索法

有目的地枚举一个问题的部分或所有可能的情况，从而找到解决问题的一种方法

确定解空间，有效地搜索这个确定的解空间，从中找出问题的真正解

穷举搜索

针对问题的可能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解

问题规模很大时存在解空间状态爆炸问题

深度优先搜索

所有顶点均未被访问过，任选一个顶点v作为源点。

先访问源点v并将其标记为已访问

然后从v出发，选择v的一个邻接点（子结点）w

如果w已访问过，则选择v的另外一个邻接点；

如w未被访问过，则标记w为已访问过，并以w为新的出发点，继续进行深度优先搜索

如果w及其子结点均已搜索完毕，则返回到v，再选择它的另外一个未曾访问过的邻接点继续搜索

直到图中所有和源点v有路径相通的顶点均已访问过为止

若此时图G中仍然存在未被访问过的顶点，则另选一个尚未访问过的顶点作为新的源点重复上述过程，直到图中所有顶点均已访问过为止

宽度优先搜索

给定图G=(V，E)，它的初始状态是所有顶点均未被访问过，在图G中任选一个顶点v作为源点

先访问顶点v，并将其标记为已访问过

然后从v出发，依次访问v的邻接点（孩子结点），将其插入到队列中

然后再依次从队列中取出w1, w2, …,wt，访问它们的邻接点

依此类推

若此时图G中仍然存在未被访问过的顶点，则另选一个尚未访问过的顶点作为新的源点

重复上述过程，直到图中所有顶点均已访问过为止

回溯法算法框架

算法思想

从根开始，以DFS的方式进行搜索。根结点是活结点并且是当前的扩展结点。

在搜索的过程中，当前的扩展结点向纵深方向移向一个新结点，判断该新结点是否满足隐约束：

如满足，则新结点成为活结点且成为当前的扩展结点，继续深一层的搜索；

如不满足，则换该新结点的兄弟结点（扩展结点的其它分支）继续搜索。

如新结点没有兄弟结点，或其兄弟结点已全部搜索完毕，则扩展结点成为死结点，搜索回溯到其父结点处继续进行

直到找到问题的解或根结点变成死结点为止。

回溯法解题步骤

(1) 针对所给问题，定义问题的解空间

(2) 确定易于搜索的解空间结构

(3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
约束函数：在扩展结点处剪去不满足约束的子树
限界函数：剪去得不到最优解的子树

递归回溯通用伪代码

BACKTRACK(t) //t为扩展结点在树中所处的层次
	if t > n //已到叶子结点，输出结果
		OUTPUT(x)
	else
		for i  s(n,t) to e(n,t)
		{
			x[t] = h(i) //在当前扩展结点处 x[t]的第i个可选值
			if CONSTRAINT(t) && BOUND(t) //约束函数与限界函数
				BACKTRACK(t+1) //进入t+1层搜索
		}

迭代回溯通用伪代码

BACKTRACK()
t = 1 //t为扩展结点在树中所处的层次
while t > 0
{
if s(n,t) <= e(n,t)
	for i s(n,t) to e(n,t)
	{
		    x[t] = h(i) //h[i]: 在当前扩展结点处x[t]的第i个可选值
			if CONSTRINT(t) && BOUND(t)
				if t > n //已到叶子结点，输出结果
					OUTPUT(x);
			else
				t ++ //前进到更深层搜索
	}
else
	t -- //回溯到上一层的活结点
}

子集树

当待求解问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树为子集树

整体与部分的关系。

此类问题解的形式为n元组(x1,x2,…,xn)，分量xi(i=1,2,…, n)表示第i个元素是否在待找的子集中

xi的取值为0或1（约定左分支为1，右分支为0）

xi=0表示第i个元素不在子集中，xi=1表示第i个元素在子集中

树中从根到叶子的路径描述了一个n元0-1向量，该n元0-1向量表示集合S的一个子集，这个子集由对应分量为1的元素组成

递归式回溯伪代码

BACKTRACK(t) / /t为扩展结点在树中所处的层次
	if t > n OUTPUT(x) //已到叶子结点，输出结果
		output(x) 
	else
		for(int i = 0; i<=1; i++)
		{
			x[t]=i
			if CONSTRAINT(t) &&BOUND(t)
				BACKTRACK(t+1)
		}

最多有2^n个叶子结点, 树的结点总数为2n+1-1

该算法的时复杂性为O(n*2^n)
空间复杂度：O(n)，即递归深度
剪枝会大大降低其复杂性

排列树

当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树

排列树通常有n!个叶子结点

递归式回溯伪代码

BACKTRACK(t) / /t为扩展结点在树中所处的层次
		if t > n OUTPUT(x) //已到叶子结点，输出结果
			output(x) //x[1..n]: 为解向量
		else
			for(int i = 0; i<=n; i++)
			{
				swap(x[t], x[i])
				if CONSTRAINT(t) &&BOUND(t)
					BACKTRACK-PT-REC(t+1)
				swap(x[t], x[i])
			}

时复杂性为O(n*n!)