一、简述
回溯法,以穷举的形式,对问题有可能出现的解罗列出来,必要的时候会包含剪枝的操作。根据罗列的形式不一样,又有分为两种:
-
子集树 回溯
-
排列树 回溯
二、步骤
- 根据题目,找到相应解空间,即解可能的组合
- 选择相应的解空间树(子集 or 排列),这一步最好画出来,便于理解分析
- 使用深度优先搜索(dfs)搜索树(必要的时候带上剪枝)
如上,因为第 3 步可以直接套用 三、解题模型
,因此重要的一步便是 2,选择什么样的结构去解决题目,那么该如何确定选择哪种结构呢?如下分析:
-
子集树:从给出集合中,找出满足某些条件的子集。
如: 01 背包问题,就是从物品集合中,找出最大重量的子组合、 -
排列树:将集合中的元素,给出按照某些条件进行排列的子集
如:排列数字,就是将集合({1, 2, 3}
)进行排序,给出所有可能的排序。
三、解题模型
由于树的搜索(这里是 dfs)可以选用栈或者递归的方式,因此也有两种模型
1. 栈
pass,持续更新后补
2. 递归(常用)
使用递归的方式进行通解,通常要定义如下参数:
- int k - 当前层
- int n - 总层数 (如果总层数使用解的个数,则无需定义)
- vector<T>& x - 解
- vector<T>& res - 记录的结果
以及剪枝函数(有时候也叫限界函数):
- constraint(k) 即判断是否有必要进行下一次的hui's
2.1 子集树
void backtrack(int k, vector<T>& x, vector<T>& res) {
if (k >= x.size()) {
// 此处做记录
res.push_back(x);
} else {
// 继续深入
for (int i=0; i<=1; i++) {
x[t] = i; // 选 0 或者 1
if (constraint(k)) {
backtrack(k+1, x, res);
}
}
}
}
2.2 排列树
void backtrack(int k, vector<T>& x, vector<T>& res) {
if (k >= x.size()) {
// 此处做记录
res.push_back(x);
} else {
// 继续深入
for (int i=k; i<=x.size(); i++) {
swap(x[t], x[i]);
if (constraint(k)) {
backtrack(k+1, x, res);
swap(x[t], x[i]);
}
}
}
}
排列树主要是通过 swap(a: T, b: T)
方法对元素交叉排列,在结束之后再交换回来(恢复状态)。
四、案例
TODO 持续更新
网友评论