一、知识铺垫
- 约束条件
分为显式约束和隐式约束
显式：规定了问题的解的分量的取值范围。如求n的全排列每个位置只能取1~n
隐式：用于判定候选解是否为可行解。如全排列的每个数字不允许重复。 - 问题状态和状态空间树
状态空间树是描述问题解空间的树形结构，每个结点称为一个问题状态。树的每条分支代表一次决策，从根结点到叶结点的路径就代表了一个候选解，称该叶结点所代表的状态为解状态。如果候选解是可行解则称之为答案状态。 - 剪枝函数
剪枝函数分为约束函数和限界函数
约束函数：避免无所谓的搜索那些已知不含答案状态的子树。
限界函数：用于最优化问题，剪去那些不可能含有最优答案结点的子树。
二者的区别在于：约束函数是对约束条件的实现，剪去不带答案结点的子树。而限界函数常用于求解最优化问题，它剪去的子树可能带答案结点，但不会是最优答案结点。
二、什么是回溯法
回溯法是一种更为一般的解题方法。回溯法是通过搜索状态空间树来求问题的可行解或最优解的方法。本质就是dfs + 剪枝。
三、回溯法的使用场景
如果问题的解可表示成一个n元组 ( x 1 , x 2 , . . . , x n ) (x_1,x_2,...,x_n) (x1,x2,...,xn)，我们就可以通过枚举所有的可能排列来搜索答案。比如求全排列、迷宫问题、n皇后、子集和数、图的着色问题等。
四、回溯法的解题步骤
void BackTrack(int k){
if k == n { 输出答案 }
else{
for 所有可能的x[k]取值
if x[k] 满足约束条件
BackTrack(k+1)
}
}
五、典例
- n皇后问题
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 15;
int g[N], ans[N];
int n;
LL cnt;
bool vis[N];
bool check(int k, int j){
for(int i = 1; i < k; i ++){
if(ans[i] == j || abs(i - k) == abs(ans[i] - j))
return false;
}
return true;
}
void nQueens(int d){
if(d == n + 1){
for(int i = 1; i <= n; i ++)
cout << ans[i] << ' ';
cout << endl;
cnt ++;
return;
}
for(int i = 1; i <= n; i ++){ // 显式约束
if(!vis[i] && check(d,i)){ // 隐式约束
ans[d] = i;
vis[i] = 1;
nQueens(d + 1);
vis[i] = 0;
}
}
}
int main(){
cin >> n;
nQueens(1);
cout << cnt;
return 0;
}
- 子集和数问题
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[N], x[N], tmp[N];
int idx[100*N];
int n, m;
bool f;
void dfs(int s, int k, int r){
x[k] = 1;
if(s + w[k] == m){
for(int i = k + 1; i < n; i ++)
x[i] = 0;
for(int i = 0; i < n; i ++)
cout << x[idx[tmp[i]]] << ' ';
cout << endl;
f = 1;
}
else if(s + w[k] + w[k + 1] <= m){ //选 k可以
dfs(s + w[k], k + 1, r - w[k]);
}
if(s + r - w[k] >= m && s + w[k+1] <= m){ //不选 k
x[k] = 0;
dfs(s, k + 1, r - w[k]);
}
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++)
cin >> w[i], tmp[i] = w[i]; // tmp copy w for print
int r = 0, s = 0;
for(int i = 0; i < n; i ++)
r += w[i];
sort(w, w + n);
for(int i = 0; i < n; i ++)
idx[w[i]] = i;
if(r >= m && w[0] <= m)
dfs(s,0,r);
if(!f) cout << "no solution!" << endl;
return 0;
}
