回溯法定义
回溯法是一种搜索算法, 可以系统地搜索一个问题的所有解或任一解
回溯法原理
回溯法的搜索原理是深度优先搜索策略
原理: 首先定义问题的解空间, 举个0-1背包的例子, 假设只有两个东西, 那么解空间可以这样表示{(00),(01),(10),(11)}; 其次组织解空间, 一般组织为树或者图, 所以0-1背包的解空间就变成了一棵完全二叉树; 最后是开始搜索, 过程是这样的: 从根节点出发, 以深搜方式搜索整个解空间. 根节点首先成为活节点, 并且纵向移至下一个新节点, 新节点就成为了活结点, 如果活结点无法再纵向移动, 那么就成为了死节点, 此时就应该回溯到最近一个活结点处, 继续用以上的方式进入下一个扩展.
回溯法以这种方式在解空间中搜索, 直到找到所要求的解活解空间中已经没有活结点为止
算法的步骤如下:
- 针对所给问题, 定义问题的解空间
- 确定易于搜索的解空间结构
- 以深搜方式搜索解空间, 并在搜索过程中使用剪枝函数避免无效搜索
回溯法算法框架
递归回溯
void backTrack( int t ) {
if( t > n ) {
Output( x );
} else {
for( int i = f( n, t ); i <= g( n, t ); ++i ) {
x[ t ] = h( i );
if( constraint( t ) && bound( t ) )
backTrack( t+1 );
}
}
说明:
- t 表示递归深度
- n 表示解空间树的总深度
- x 表示可行解
- f(n,t) 表示当前
活结点未搜索过的子树起始编号- g(n,t) 表示当前
活结点未搜索过的子树终止编号- constraint(t) 表示约束函数, 用于确认x[1…t]是否满足约束条件, 不满足条件可以剪枝
- bound(t) 表示限界函数, 用于确认x[1…t]是否使目标函数越界, 使目标函数越界可以剪枝
迭代回溯
void iterativeBackTrack() {
int t = 1;
while( t > 0 ) {
if( f( n, t ) <= g( n, t ) ) {
for( int i = f( n, t ); i <= g( n, t ); ++i ) {
x[ t ] = h( i );
if( constraint( t ) && bound( t ) ) {
if( solution( t ) ) //表示有可行解
Output( x );
else
++t;
}
}
} else {
--t;
}
}
}
子集树
子集树定义:当所给的问题是从n个元素的集合中找出满足某种性质的子集时, 相应的解空间树称为子集树, 其解空间大小为O(2^n)
void backTrack( int t ) {
if( t > n ) {
Output( x );
} else {
for( int i = f( n, t ); i <= g( n, t ); ++i ) {
x[ t ] = h( i );
if( constraint( t ) && bound( t ) )
backTrack( t+1 );
}
}
}
排列树
排列树定义:当所给的问题是从n个元素的集合中找出满足某种性质的排列时, 相应的解空间树称为排列树, 其解空间大小为O(n!)
void backTrack( int t ) {
if( t > n ) {
Output( x );
} else {
for( int i = f( n, t ); i <= g( n, t ); ++i ) {
// swap表示交换元素
swap( x[t], x[i] );
if( constraint( t ) && bound( t ) )
backTrack( t+1 );
swap( x[t], x[i] );
}
}
}