回溯算法 --- 算法思想介绍

一.回溯算法的基本概念

回溯法有“通用的解题法”之称。
用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法，它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则进入该子树，继续按深度优先策略搜索。回溯算法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯算法，它适用于解组合较大的问题。

二.回溯法的算法框架

1.问题的解空间

用回溯法求解问题时,应明确定义问题的解空间.问题的解空间至少应包含问题的一个(最优)解.例如,对于有n中可选择物品的0-1背包问题,其解空间由长度为n的0-1向量组成.该解空间包含对变量的所有可能的0-1赋值.当n=3时,其解空间如下:
{(0,0,0), (0,0,1), {0,1,0}, {1,0,0}, {0,1,1}, {1,1,0}, {1,0,1}, {1,1,1}}.
定义了问题的解空间之后,还应将解空间很好地组织起来,使得能够用回溯法方便地搜索整个解空间.通常将解空间组织成树或图的形式.
例如,对于n=3时的0-1背包问题,可用一棵完全二叉树表示其解空间.如下图所示:

解空间树的第i层到第i+1层边上的标号给出了变量的值.从树根到叶子结点的任意路径表示解空间中的一个元素.例如,从根节点到结点H的路径相应于解空间中的元素(1,1,1).

2.回溯法的基本思想

确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

3.回溯法的基本步骤

• (1)针对所给问题，定义问题的解空间
• (2)确定易于搜索的解空间结构；
• (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

剪枝函数:
回溯法在搜索解空间树时,通常采用两种策略来避免无效搜索,提高回溯法的搜索效率.
其一是用约束函数在扩展结点处减去不满足约束的子树.
其二是用限界函数减去得不到最优解的子树.
这两类函数统称为剪枝函数.

4.子集树和排列树

子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间称为子集树。例如，那个物品的0-1背包问题所相应的解空间树就是一颗子集树。这类子集问题通常有2^{n个叶节点，其节点总个数为2}(n+1)-1。遍历子集树的任何算法均需要O(2^n)的计算时间.
如下图:

用回溯法搜索子集树的一般算法可描述为:

void Backtrack(int t)
{
	if(t>n)
		Output(x);
	else
	{
		for(int i=0; i<=1; i++)
		{
			s[t] = i;
			if(Constraint(t) && Bound(t))
				Backtrack(t+1);
		}
	}
}

排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子节点。因此遍历排列树需要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]);
		}
	}
}

在调用Backtrack(1)执行回溯搜索前,现将变量数组x初始化为单位排列(1,2,...,n).

三.回溯算法总结

回溯法核心：找出解决问题的组织结构，是采用子集树解决，还是采用排列树解决；
回溯法重点：根据问题，找出剪枝函数，避免无效的搜索，导致性能降低；
回溯法缺点：比较慢，递归求解，排列树思想要搜索出所有的解，类似于暴力求解，时间复杂度高。

参考毕方明老师《算法设计与分析》课件.

欢迎大家访问个人博客网站---乔治的编程小屋,和我一起加油吧!