回溯算法的本质是暴力穷举,即使用递归控制for循环嵌套的数量,本身不是一个高效的算法。尽管可以使用剪枝来提高效率,但是还是改不了穷举的本质。回溯法,一般用来解决组合,排列,切割,子集,棋盘等问题。
理论基础
回溯法也就是使用递归函数进行解决问题,精髓是使用递归控制for循环嵌套的数量。
解决问题的过程可以抽象为树形结构,即一颗高度有限的树(N叉树)。从根节点一直走到叶子节点。叶子节点为满足条件的一个解决方案。
因为回溯法解决的都是在集合中递归查找子集,所以集合的大小就构成了树的宽度,递归的深度就构成树的深度。下图为回溯法解决问题所产生的树,也是回溯法解决问题的思路和过程。
模板框架
回溯算法模板框架如下:
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表);
回溯,撤销处理结果
}
}
使用回溯法要明白问题的终止条件,和如何构建循环。
终止条件:什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。
循环:for循环横向遍历,递归纵向遍历,回溯不断调整结果集
大家可以从图中看出「for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历」,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。
实例
leetcode: 第77题. 组合
题目链接:https://leetcode-cn.com/problems/combinations/
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出: [ [2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ]
思路
本题最开始的想法就是使用for进行遍历,k=2时可以使用两层for循环,k=3时可以使用3层for循环进行嵌套,但是当k=50时就要使用50个for循环进行嵌套,这显然是不可能的,这是无法写出的。
进而我们想到使用递归,每一个递归都是一个for循环,到达终止条件即到达最后一个循环结束递归。
终止条件:每一次backtracking都是将从根节点到叶子节点的数据依次存入path,程序走到叶子节点,即path.size() == k,将符合条件结果保存,并结束递归。
循环:使用for循环横向遍历,递归纵向遍历
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
剪枝
回溯算法虽然是暴力穷举算法,但是也能使用剪枝来进行优化。当n=4,k=4时,由下图可看出第一层for循环的时候,从元素2开始的遍历都没有意义了。在第二层for循环,从元素3开始的遍历都没有意义了。我们可以使用剪枝不进行这些搜索
剪枝精髓是:for循环在寻找起点的时候要有一个范围,如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了,就没有必要搜索了。
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
接下来看一下优化过程如下:
已经选择的元素个数:path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历
为什么有个+1呢,因为包括起始位置,我们要是一个左闭的集合。
举个例子,n = 4,k = 3, 目前已经选取的元素为0(path.size为0),n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的,可以是组合[2, 3, 4]。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)