当前位置 博文首页 > m0_53521757的博客：回溯法总结
1.回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解。
2.回溯法是一种既带系统性又带有跳跃性的搜索算法。
3.回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯。
4.通常以深度优先方式系统搜索问题解
5.解空间树有两种。子集树和排列数
6.搜索解空间树时，常用的两种剪枝函数为：约束函数和限界函数
递归回溯框架
1.解空间为子集树
int x[n]; //x存放解空间，为全局变量
void backtrack(int i) //求解子集树的递归框架
{
if(i>n) //搜索到叶子结点，输出一个可行解
输出结果;
else
{
for(j=下界;j<=上界;j++) //用j枚举i所有可能的路径
{
x[i]=j; //产生一个可能的解分量
…… //其他操作
if(constraint(i)&&bound(i))
backrack(i+1); //满足约束条件和限界函数，继续下一层
}
}
}
时间复杂度为O(2^n)
2.解空间为排列树
int x[n]; //x存放解空间，并初始化
void backtrack(int i) //求解排列树的递归框架
{
if(i>n) //搜索到叶子结点，输出一个可行解
输出结果;
else
{
for(j=i;j<=n;j++) //用j枚举i所有可能的路径
{
…… //第i层的结点选择x[j]的操作
swap(x[i],x[j]); //为保证排列中的每个元素不同，通过交换来实现
if(constraint(i)&&bound(i))
backrack(i+1); //满足约束条件和限界函数，继续下一层
swap(x[i],x[j]); //恢复状态
…… //第i层的结点选择x[j]的恢复操作
}
}
}
时间复杂度为O(n!)
cs