回溯法(backtracking)是解决问题的一种策略,是穷举法的一种推广,一种搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树,利用试探和回溯的搜索技术求得问题的解。 回溯法也是设计递归过程的一种重要方法。它求解过程实际是先序遍历一棵“状态树”的过程,只是这个树是在遍历过程中动态生成的

集合的幂集

问题:求含有n个元素的集合A的幂集。

当然这个问题也可以用暴力搜索或者分治法求得问题的解,在这里我们从另一个角度来解决这个问题,作为引子,理解回溯,以及回溯过程中伴随的状态树。 幂集的每个元素是一个集合,它或是空集、或含集合A中的一个元素、或含集合A中的两个元素、或等于集合A。也就是说,集合A中的元素x,对于幂集的每一个元素S而言,要么x属于S,要么x不属于S。所以,求幂集的元素的过程可看成是依次对集合A中的元素进行取舍的过程。 并且可以用一棵二叉树来表示过程中幂集元素的变化状况,求幂集的元素的过程即为先序遍历这棵状态树的过程。如下图所示: 树中的根节点表示幂集元素的初始状态(为空集);叶子结点表示它的终结状态,而第i(i=2, 3, ... , n-1)层的分支结点,则表示已对集合A中前i-1个元素进行了取/舍处理的当前状态(左分支表示取,右分支表示舍)。

求幂集元素的过程即为先序遍历这棵状态树的过程,算法伪代码描述如下:

void PowerSet( int i, int n)
{	// 求含n个元素的集合A的幂集,进入函数时	
	// 已对A中前i-1个元素作了取舍处理,现从第i个元素起	
	// 进行取舍处理,若i>n则求得幂集的一个元素,	
	// 并输出之。	
	// 初始调用:PowerSet(1,n)	
	if( i>n) 输出幂集的一个元素	
	else{		
	    取第i个元素,PowSet(i+1,n)		
	    舍第i个元素,PowSet(i+1,n)	
	}
} // PowerSet

算法求精(用线性表表示集合)如下:

void GetPowerSet( int i, List A, List &B)
{	// 线性表A表示集合A,线性表B表示集合幂集的一个元素	
	// 局部变量k为进入函数时表B的当前长度,	
	// 第一次调用本函数时,B为空表,i=1
	if( i>ListLength(A)) Output(B);	  //输出当前B值,即幂集的一个元素
	else {		
	    GetElem(A, i, x); //线性表的一个操作,取出A中的第i个元素存到x中
	    k = ListLength( B);
	    ListInsert(B, k+1, x);  //把x添加到B的第k+1之前的位置
	    GetPowSet(i+1,A, B);
	    ListDelete(B, k+1, x);    //把B的第k+1个元素删除并把长度减一,用x返回删除的元素值
	    GetPowSet(i+1,A, B);
	}
} // GetPowerSet

以上算法描述的有点不清楚需要好好琢磨琢磨(反正我是一开始没有看懂,到后来看完文字描述后才懂,这段代码也是写的含糊不清)

上面这个例子求解过程中状态树是满树,然而大多数情况下的问题求解过程中的状态树不是一棵满的多叉树,需要依靠约束剪去不满足条件的分支。

4皇后问题

问题:求4皇后的所有合法布局,由此引出8皇后的问题。四皇后问题是4x4的棋盘上放置4个皇后,任何两个都满足不占据棋盘上的同一行同一列或者同一对角线。

其遍历的状态树如下图所示: 求解该问题就是依次先根遍历满足约束条件的各棵子树,判断棋盘上是否已经得到一个完整的布局(即是否摆满了4颗棋子)若是输出结果。否则剪枝。

其伪代码算法如下:

void Trial (int i, int n) {
//进入本函数时,在nxn棋盘前i-1行已经放置了满足约束的i-1个棋子
//现在从第i行起继续为后续棋子选择合适位置
//当i>n时,求得一个合法布局,并输出之
    if(i>n)    输出棋盘的当前布局;    //n为4时,即为4皇后问题
    else for(j=1; j<=n; ++j) {
        在第i行第j列放置一颗棋子;
        if(当前布局合法)    Trial(i+1, n);
        移走第i行第j列的棋子;
    }
}

上面这个算法可以作为回溯法求解的一般模式,类似的还有骑士游历、迷宫问题、选最优解问题等等。

从求解过程不难看出,4皇后问题遍历的是一棵具有普遍性的状态树,则类似问题都可用遍历这棵状态树的方法解决即:回溯法。

8皇后问题

问题:在国际象棋中,皇后可以向八个方向伸展去吃,问题是如何把八个皇后同时放在棋盘上,互相不被吃。

解决方法是同4皇后问题一样的,只不过8皇后的规模更大些。不是一般性n皇后问题都能解决。至于求精的算法不再给出,具体依赖存储结构等信息。

总结

回溯法一般都有递归的特性:所解决问题可以用数学归纳建模,最关键的也是建立问题的抽象递推模型。 回溯法效率一般不高,需要结合剪枝、动态规划等手段优化程序执行效率。


总结自:《数据结构(C语言版)》 清华大学出版社 严蔚敏、吴伟民编著