hello算法之回溯
回溯
回溯算法(backtracking algorithm)是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,当遇到正确的解则将其记录,自到找到解或尝试了所有的可能都无法找到解为止。
回溯算法通常采用“深度优先搜索”来遍历空间。在“二叉树”章节中,我们提到前序、中序和后序遍历都属于深度优先搜索。接下来我们利用前序遍历构造一个回溯问题,逐步了解回溯算法的工作原理。
对于此题,我们前序遍历这颗树,并判断当前节点的值是否为7,若是,则将该节点的值加入结果列表res之中。相关过程如下代码所示
void preOrder(TreeNode *root) {
if(root == nullptr) {
return;
}
if(root->val == 7) {
res.push_back(root);
}
preOrder(root->left);
preOrder(root->right);
}
尝试与回退
之所以称之为回溯算法,是因为该算法在搜索解时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法前进或无法得到满足条件的解时,它会撤销上一步的选择,回到之前的状态,并尝试其他可能的选择。
void preOrder(TreeNode *root) {
if(root == nullptr) {
return;
}
path.push_back(root);
if(root->val == 7) {
res.push_back(root);
}
preOrder(root->left);
preOrder(root->right);
path.pop_back();
}
上述代码执行过程
1
/ \
2 3
/ \
4 7
1. path = [1]
2. path = [1, 2]
3. path = [1, 2, 4]
4. path = [1, 2, 7] # 找到目标节点,将其加入结果列表,有目标结果的路径
5. path = [1, 2]
6. path = [1, 3]
剪枝
复杂的回溯问题通常包含一个或多个约束条件,约束条件通常用于“剪枝”。
为了路径不能包含有3,因此我们需要添加一个条件来进行剪枝的操作。
void preOrder(TreeNode *root) {
if(root == nullptr || root->val == 3) {
return;
}
path.push_back(root);
if(root->val == 7) {
res.push_back(root);
}
preOrder(root->left);
preOrder(root->right);
path.pop_back();
}
框架代码
接下来,我们尝试将回溯算法的“尝试”、“回退”、“剪枝”的主体框架提炼出来,提升代码通用性。
void backtrack(State *state, vector<Choice*> &choices, vector<State*> &res) {
// 判断是否为解
if(isSolution(state)) {
// 记录解
recordSolution(state, res);
return;
}
for(Choice choice : choice) {
// 剪枝: 判断选择是否合法
if (isValid(state, choice)) {
// 尝试:做出选择,更新状态
makeChoice(state, choice);
backtrack(state, choices, res);
// 回退:撤销选择,恢复到之前的状态
unmakeChoice(state, choice);
}
}
}
// 判断当前状态是否为解
bool isSolution(State *state) {
return !state.empty() && state.back()->val == 7;
}
// 记录解
void recordSolution(State *state, vector<State*> &res) {
res.push_back(state);
}
// 判断选择是否合法
bool isValid(State *state, Choice choice) {
return choice != nullptr || choice->val != 3;
}
// 尝试:做出选择,更新状态
void makeChoice(State *state, Choice choice) {
state.push_back(choice);
}
// 回退:撤销选择,恢复到之前的状态
void unmakeChoice(State *state, Choice choice) {
state.pop_back();
}
void backtrack(vector<TreeNode*> &state, vector<TreeNode*> &choices, vector<vector<TreeNode*>> &res) {
if(isSolution(state)) {
recordSolution(state, res);
}
if(TreeNode *choice : choices) {
if(isValid(state, choice)) {
makeChoice(state, choice);
vector<TreeNode*> nextChoices = nextChoices{choice->left, choice->right};
backtrack(state, choices, res);
unmakeChoice(state, choice)
}
}
}
常用术语
| 名词 | 定义 | 例题三 |
|---|---|---|
| 解(solution) | 解是满足问题特定条件的答案,可能有一个或多个 | 根节点到节点7的满足约束条件的所有路径 |
| 约束条件(constraint) | 约束条件是问题中限制解的可行性的条件,通常用于剪枝 | 路径中不包含节点3 |
| 状态(state) | 状态表示某个问题在某一时刻的情况,包括已经做出选择 | 当前已访问的节点路径,即path节点列表 |
| 尝试(attempt) | 尝试是根据可用选择来探索空间的过程,包括做出选择,更新状态,检查是否为解 | 递归访问左(右)子节点,将节点添加进path,判断节点的值是否为7 |
| 回退(backtracking) | 回退指遇到不满足条件的状态时撤销前面一个选择,回到上一个状态 | 当越过叶子节点、结束节点访问、遇到值为3的节点时终止搜索,函数返回 |
| 剪枝(pruning) | 剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法,可提高搜索效率 | 当遇到值为3的节点时,则不再继续搜索 |
优点与局限性
回溯算法本质上是一种深度优先搜索算法,它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有的解决方案,并且在合理的剪枝操作下,具有很高的效率。
然而,在处理大规模或者复杂问题时,回溯算法的运行效率可能难以接受。
- 时间:回溯算法通常需要遍历状态空间的所有可能,时间复杂度可以达到指数阶或阶乘阶。
- 空间:在递归调用中需要保存当前的状态(例如路径、用于剪枝的辅助变量等),当深度很大时,空间需求可能会变得很大。
即便如此,回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题,由于无法预测那些选择可生成有效的解,因此我们必须对所有可能的选择进行遍历。在这种情况下,关键是如何优化效率,常见的方法有两种。
- 剪枝:避免搜索那些肯定不会产生解的路径,从而减少时间和空间
- 启发式搜索:在搜索过程中引入一些策略或者估计值,从而优先搜索最有可能产生有效解的路径。
全排列问题
全排列问题是回溯算法的一个经典应用。它的定义是在一个集合(如一个数组或字符串)的情况下,找出其中元素的所有可能的排列。
全排列实例如下所示:
| 输入数组 | 所有排列 |
|---|---|
| [1] | [1] |
| [1, 2] | [1, 2], [2, 1] |
| [1, 2, 3] | [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] |
无相等元素的情况
从回溯算法的角度看,我们可以把生成排列的过程想象成一系列选择的结果。假设输入数组为[1, 2, 3],如果我们先选择1,再选择3,最后选择2,则获得排列[1, 3, 2]。回退一个表示撤销选择,之后继续尝试其他选择。
从回溯代码的角度看,候选集合choices是输入数组中的所有元素,状态state是直至目前唯一被选择的元素。请注意,每个元素只允许被选择一次,因此state中的所有元素都应该是唯一的。
重复选择剪枝
为了实现每个元素只被选择一次,我们考虑引入一个布尔型数组selected,其中selected[i]表示choices[i]是否已被选择,并基于它实现以下剪枝操作。
- 在做出选择
choices[i]后,我们就将selected[i]赋值为true,代表它已经被选择。 - 遍历选择列表
choices时,跳过所有已被选择的节点,即剪枝。
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
if(state.size() == choices.size()) {
res.push_back(state);
return;
}
for(int i = 0; i < choices.size(); i++) {
int choice = choices[i];
if(selected[i]) {
selected[i] = true;
state.push_back(choice);
backtrack(state, choices, selected, res);
selected[i] = false;
state.pop_back();
}
}
}
vector<vector<int>> permutationsI(vector<int> nums) {
vector<int> state;
vector<bool> selected(nums.size(), false);
vector<vector<int>> res;
backtrack(state, nums, selected, res);
return res;
}
考虑相等元素情况
假设输入数组为[1, 1, 2]。为了方便区分两个重复元素1,我们将第二个1记为¹。那么如何去除重复的排列呢?最直接地,考虑借助一个哈希集合,直接对排序结果进行去重。然而这样做不够优雅,因为生成重复的排列的搜索分支没有必要,应当提前识别并剪枝,这样可以进一步提升算法效率。
相等元素剪枝
在第一轮中,选择1或选择¹是等价的,在这两个选择之下生成的所有排列都是重复的。因此应该把¹剪枝。
同理,在第二轮选择2之后,第二轮选择中的1和¹也会产生重复分支,因此也要将第二轮的¹剪枝。
从本质上看,我们的目标是在某一轮选择中,保证多个相等的元素仅被选择一次。
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
if(state.size() == choices.size()) {
res.push_back(state);
return;
}
unordered_set<int> duplicated;
for(int i = 0; i < choices.size(); i++) {
int choice = choices[i];
if(!selected[i] && duplicated.find(choice) == duplicated.end()) {
duplicated.emplace(choice);
selected[i] = true;
state.push_back(choice);
backtrack(state, choices, selected, res);
selected[i] = false;
state.pop_back();
}
}
}
vector<vector<int>> permutationsII(vector<int> nums) {
vector<int> state;
vector<bool> selected(nums.size(), false);
vector<vector<int>> res;
backtrack(state, nums, selected, res);
return res;
}
子集和问题
无重复元素的情况
例如,输入集合{3, 4, 5}和目标整数9,解为{3, 3, 3},{4, 5}。需要注意以下情况。
- 输入集合中的元素可以被无限使用。
- 子集不区分元素顺序,比如{4, 5}和{5, 4}是同一个子集。
参考全排列解法
类似于全排列问题,我们可以把子集的生成过程想象成一系列选择的结果,并在选择过程中实时更新“元素和”,当元素和等于target时,就将子集记录至结果列表。
而与全排列问题不同的是,本题集合中的元素可以被选取无数次,因此无需借助selected布列列表来记录元素是否被选择。我们可以对全排列代码进行小幅修改,初步得到如下解法。
void backtrack(vector<int> &state, int target, int total, vector<int> &choices, vector<vector<int>> &res) {
// 子集和等于target时,记录解
if(total == target) {
res.push_back(state);
return;
}
for(int i = 0; i < choices.size(); i++) {
if(total + choices[i] > target) {
continue;
}
state.push_back(choices[i]);
backtrack(state, target, total + choices[i], choices, res);
state.pop_back();
}
}
vector<vector<int>> subsetSumINaive(vector<int> &nums, int target) {
vector<int> state;
int total = 0;
vector<vector<int>> res;
backtrack(state, target, total, nums, res);
return res;
}
向以上代码输入数组[3, 4, 5]和目标元素9,输出结果为[3, 3, 3], [4, 5], [5, 4]。 虽然成功找出了所有和为9的子集,但其中存在重复的子集[4, 5]和[5, 4]。
这是因为搜索过程是区分选择顺序的,然而子集不区分选择顺序。
为了去除重复的子集,一种直接的思路是对结果列表进行去重。但这个方法效率很低,有两个方面的原因。
- 当数组元素较多时,尤其当
target较大时,搜索过程会产生大量重复的子集。 - 比较子集的异同非常耗时,需要先排序数组,再比较数组中每个元素的异同。
重复子集剪枝
我们考虑在搜索过程中通过剪枝进行去重。重复子集是在以不同的顺序选择数组元素时产生的,例如一下情况。
- 当第一轮和第二轮分别选择3和4时,会生成包含这两个元素的所有子集,记为[3, 4, ...]。
- 之后,当第一轮选择4时,则第二轮应该跳过3,因为该选择产生的子集[4, 3, ...]和第1步中生成的子集完全重复。
在搜索过程中,每一层的选择都是从左到右被逐个尝试的,因此越靠右的分支被剪掉的越多。
- 前两轮选择3和5, 生成子集[3, 5, ...]。
- 前两轮选择4和5,生成子集[4, 5, ...]。
- 若第一轮选择5, 则第二轮应该跳过3和4, 因为子集[5, 3, ...]和[5, 4, ...]与第1步和第二步中描述的子集完全重复。
总结来看,给定输入数组[x1, x2, ..., xn],设搜索过程中的选择序列为[x1, xi2, ..., xin],则该选择序列需要满足i1 <= i2 <= ... <= im, 不满足该条件的选择序列都会造成重复,应当被剪枝。
代码实现
为了实现该剪枝,我们初始化变量start,用于指示遍历起始点。当做出选择xi后,设定下一轮从索引i开始遍历。这样做就可以让选择序列满足i1 <= i2 <= ... <= im。从而保证子集唯一。
除此之外,我们还对代码进行了以下两项优化。
- 在开启搜索前,先将数组
nums排序。在遍历所有选择时,当子集和超过target时直接结束循环,因为后边的元素更大,其子集和一定超过target。 - 省去元素和变量
total,通过在target上执行减法来统计元素和,当target等于0时记录解。
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
if(target == 0) {
res.push_back(state);
return;
}
for(int i = start; i < choices.size(); i++){
if(target - choices[i] < 0) {
break;
}
state.push_back(choices[i]);
backtrack(state, target - choices[i], choices, i, res);
state.pop_back();
}
}
vector<vector<int>> subsetSumI(vector<int> &nums, int target) {
vector<int> state;
sort(nums.begin(), nums.end());
vector<vector<int>> res;
backtrack(state, target, nums, 0, res);
return res;
}
考虑重复元素的情况
上对于上诉情况,下面引入新的问题,例如,给定数组[4, 4, 5]和目标元素9,则现有代码的输出结果为[4, 5], [4, 5], 出现了重复子集。
造成这种重复的原因是相等的元素在某轮中多次被选择。第一轮共有三个选择,其中两个都为4,会产生两个重复的搜索分支,从而输出重复子集;同理,第二轮的两个4也会参数重复的子集。
相等元素剪枝
为了解决此问题,我们需要限制相等元素在每一轮中只能被选择一次。实现方式比较巧妙:由于数组已排序的,因此相等元素都是相邻的。这意味着在某轮选择中,若当前元素与其左边元素相等,则说明它已经被选择过,因此直接跳过当前元素。
于此同时,本题规定每个数组的元素只能被选择一次。幸运的是,我们也可以利用变量start来满足该约束:当做出选择xi后,设定下一轮索引i+1开始向后遍历。这样既能去除重复子集,也能避免重复选择元素。
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
if(target == 0) {
res.push_back(state);
return;
}
for(int i = start; i < choices.size(); i++) {
if(target - choices[i] < 0){
break;
}
if(i > start && choices[i] == choices[i - 1]) {
continue;
}
state.push_back(choices[i]);
backtrack(state, target - choices[i], choices, i + 1, res);
state.pop_back();
}
}
vector<vector<int>> subsetSumII(vector<int> &nums, int target) {
vector<int> state;
sort(nums.begin(), nums.end());
vector<vector<int>> res;
backtrack(state, target, nums, 0, res);
return res;
}
N皇后问题
根据国际象棋的规则,皇后可以攻击与同处一行、一列或一条斜线上的棋子。给定n个皇后和一个n*n大小的棋盘,寻找使得所有皇后之间无法互相攻击的摆放方案。
当n=4时,共可以找到两个解。从回溯算法的角度来看,n*n大小的棋盘共有n^2个格子,给出了所有选择choices。在逐个放置在皇后的过程中,棋盘状态在不断变化,每个时刻的棋盘状态就是state。
展示了本题的三个约束条件:多个皇后不能在同一行、同一列、同一对角线上。值得注意的是,对角线分为主对角线\和次对角线/两种
逐行放置策略
皇后的数量和棋盘的行数都为n,因此我们容易得到一个推论:棋盘每行都允许且只允许放置一个皇后。
也就是说,我们可以采取逐行放置策略:从第一行开始,在每行放置一个皇后,直至最后一行结束。
从本质上看,逐行放置策略起到了剪枝的作用,它避免了同一行出现多个皇后的所有分支。
列与对角线剪枝
为了满足列约束,我们可以利用一个长度为n的布尔型数组cols记录每一列是否有皇后。在每次决定放置前,我们通过cols将已有皇后的列进行剪枝,并在回溯中动态更新cols的状态
那么,如何处置对角线约束呢?设棋盘中某个格子的行列索引为(row, col),选定矩阵中的某条主对角线,我们发现该对角线上所有格子的行索引都相等,即主对角线上所有格子的row-col为恒定值。
也就是说,如果两个格子满足row1-col1 = row2 - col2,则他们一定处在同一条主对角线上。利用该规律,我们可以通过一个数组diags1记录每条主对角线上是否有皇后。
同理,次对角线上的所有格子的row + col是恒定值。我们同样也可以借助数组diags2来处理次对角线约束。
void backtrack(int row, int n, vector<vector<string>> &state, vector<vector<vector<string>>> &res, vector<bool> &cols, vector<bool> &diags1, vector<bool> &diags2) {
if(row == n) {
res.push_back(state);
return;
}
for(int col = 0; col < n; col++) {
int diag1 = row - col + n - 1;
int diag2 = row + col;
if(!cols[col] && !diags1[diag1] && !diags2[diag2]) {
state[row][col] = "Q";
cols[col] = diags1[diag1] = diags2[diag2] = true;
backtrack(row + 1, n, state, res, cols, diags1, diags2);
state[row][col] = "#";
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
vector<vector<vector<string>>> nQueens(int n) {
vector<vector<string>> state(n, vector<string>(n, "#"));
vector<bool> cols(n, false);
vector<bool> diags1(2 * n - 1, false);
vector<bool> diags2(2 * n - 1, false);
vector<vector<vector<string>>> res;
backtrack(0, n, state, res, cols, diags1, diags2);
return res;
}
