回溯法.cpp

算法分析中

/*
以深度优先的方式系统地搜索问题的解的算法称为回溯法
它适用于解一些组合数较大的问题
*/
/*
在用回溯法搜索解空间树的时候，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率
。其一是用约束函数在扩展结点处剪去不满足约束的子树，其二是用限界函数剪去不能得到最
优解的子树。这两类函数统称为剪枝函数。
运用回溯法的三个步骤：
（1）针对所给问题，定义问题的解空间
（2）确定易于搜索的解空间结构，子集树还是排列树
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索

当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，
相应的解空间树称为子集树。这类子集树通常有2^n个叶结点，其结点总个数为
2^(n+1)-1。遍历子集树的任何算法均需要2^n计算时间。

当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为
排列树。排列树通常有n!个叶结点。因此遍历排列树需要n!的计算时间。
*/

/*
回溯法搜集子集树的一般算法可描述如下：
*/
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);
			}
		}
	}
}

/*
用回溯法搜索排列树的算法框架如下：
*/
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]);
		}
	}
}