回溯法(Backtracking)

2024年4月12日 互联网

回溯法
回溯法概念
回溯算法有“通用的解题法”之称。用它可以系统地搜索一个问题的所在解或任一解。回溯法是一个即带有系统性又带有跳跃性的所搜算法。

回溯法思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法解题步骤
用回溯法解题通常包含以下3个步骤：
1. 针对所给问题，定义问题的解空间
2. 确定易于搜索的解空间结构
3. 以深度优先方式所搜解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯算法一般框架

int solution[MAX_DIMENSION];    //多维度解
void backtrack(int dimension)
{/*检验当前维度数组是否是一个解*/if ( solution[] is well-generated ){check and record solution;return;}/* 列举当前维度的所有取值的情况，并且进入到下一维度*/for ( x = each value of current dimension ){solution[dimension] = x;backtrack( dimension + 1 );}
}
backtrack( [v1,...,vn] )    // [v1,...,vn]是多维度数值
{/*检验当前多维度数值是不是一个解*/if ( [v1,...,vn] is well-generated ){if ( [v1,...,vn] is a solution ) process solution;return;}/* 列举当前维度的所有取值的情况，并且进入到下一维度*/for ( x = possible values of vn+1 )backtrack( [v1,...,vn, x] );
}

使用回溯法解决排列问题
Question: 列出 {0,1,2,3,4} 所有的排列

int solution[5];
bool use[5] = {false};void backtrack(int n) {if (n == 5) {//processing solutionfor(int i = 0; i < n; ++i)cout << solution[i] << " ";cout << endl;return;} else{//列举{0,1,2,3,4}所有可能的值for (int i = 0; i < 5; ++i) {if (!use[i]) {use[i] = true;solution[n] = i;backtrack(n+1); //进入到下一个维度use[i] = false;}}}
}int main()
{backtrack(0);return 0;
}

Question: 列举abb所有不相同的排列
首相我们先来写abc所有的排列算法。而abc的排列算法与上面的问题是一样的，稍微进行修改就可。这里我们将不再使用全局数组solution来保存结果。

void backtrack(const vector<char> &num, vector<bool> use,vector<char> solution)
{if (solution.size() == 3) {  //注意本列中abb排列的结果维度为3for(const auto e : solution)cout << e << " ";cout << endl;return;}else {for(int i = 0; i < num.size(); ++i) {if (!use[i]) {use[i] = true;solution.push_back(num[i]);backtrack(num, use, solution);solution.pop_back();use[i] = false;}}}
}

如果直接使用上面的程序进行abb排列，则输出结果为

a b c
a c b
b a c
b c a
c a b
c b a

会出现这个情况，是因为上面的程序中认为输入的字符数组中没有相同的字符，即使有相同的字符也会当成不同对待。因此才会出现相同的排列的情况。为了避免重复的排列，我们首先对输入的字符进行排序，使得相同的字符连续出现。然后使用一个标记位来标记上一次出现的字符。

void backtrack(const vector<char> &num, vector<bool> use,vector<char> solution)
{if (solution.size() == 3) { for(const auto e : solution)cout << e << " ";cout << endl;return;}else {char prevChar = '\0';for(int i = 0; i < num.size(); ++i) {if (!use[i] && prevChar != num[i]) {prevChar = num[i];use[i] = true;solution.push_back(num[i]);backtrack(num, use, solution);solution.pop_back();use[i] = false;}}}
}

使用回溯法解决子集合问题
Question : 给定一个没有重复元素的数组nums，求它所有的子集合.
LeetCode Subsets
例如 nums = [1,2,3]的子集合为：
 

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> solution;vector<int> subset;backtrack(nums, 0, subset, solution);return solution;}
private:void backtrack(vector<int> &nums, int start, vector<int> &subset, vector<vector<int>> &solution) {solution.push_back(subset);for (int i = start; i < nums.size(); ++i) {subset.push_back(nums[i]);backtrack(nums, i+1, subset, solution);subset.pop_back();}}
};

Question : 接着上一个问题，如果输入数组中可能有重复的元素，求所有不相同的子集合
LeetCode Subsets II
与上面求abb所有的排列类似，在有相同元素时，首先对元素进行排序，然后使用标志位来记录上一次的取值。

class Solution {
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end()); //首先对数组进行排序vector<vector<int>> solution;vector<int> subset;backtrack(nums, 0, subset, solution);return solution;}
private:void backtrack(vector<int> &nums, int start, vector<int> &subset, vector<vector<int>> &solution) {solution.push_back(subset);int prevNum = INT_MAX;for (int i = start; i < nums.size(); ++i) {if (nums[i] != prevNum) {prevNum = nums[i];subset.push_back(nums[i]);backtrack(nums, i+1, subset, solution);subset.pop_back();}}}
};

reference
计算机算法设计与分析(第三版) 王晓东 编著
回溯法笔记
五大常用算法之四：回溯法
————————————————
版权声明：本文为CSDN博主「Kavin_Liang」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/shinanhualiu/article/details/52016481

最新文章