本文谈谈回溯算法和深度优先搜索。
回溯法可以看成是一种暴力搜索，穷举。看起来“暴力”给人的印象似乎都是比较简单，而效率很慢的，效率慢确实是事实，但简单则不然。
回溯穷举的复杂性本质是因为问题本身具有迅速增长的规模。
典型的回溯穷举问题是求组合排列。
对于正整数 m, n 求其组合数 Combination(m, n)和排列数 Permutation(m, n）
假设 , 排列组合公式如此计算。
这个公式说明了穷尽排列和组合的计算规模，简单举一个例子， , 将 m, n 增加一倍到 20 , 10,
增长非常迅速。
回溯法求排列
数字 “123” 的全排列如何穷举。我们知道它所有的排列是
123, 132, 213, 231, 312, 321
一个 包含 n 个不同字符的串有 个排列，怎么将它们数出来
- 假设备好了 n 个槽，我们依次填充这个槽
- 第一个槽位，有 n 中选择，画一棵树表示 n 个选择分叉；
- 从每个分叉进入第二个槽位，这时候有 n - 1个选择
- 如此循环，直到填满这 n 个槽就得到一个排列， 然后回到上一个分叉处
以上分析大致上可以画出一个分叉树结构如下：
遍历树
比如最左边的一条路径是 123， 到了叶节点填满 3个槽位，然后回溯到上一层节点 2， 在 2 这个地方已无其他选择，然后继续上溯到 1 那里， 发现有一个分叉是 3，顺着 3这条路径又找到一个路径是 132； 继续回溯到 1处，没有其它分叉，然后到了根节点，从根节点处发现了其它两个分叉 2和3 ，...
这是一种深度优先搜索的穷举法。在二叉树或多叉树的遍历中经常看到它的身影。
vector<vector<int>> result;
bool isRepeat(const vector<int> & nums, int num) {
for (int i = 0; i < nums.size(); ++i) {
if (num == nums[i])
return true;
}
return false;
}
vector<vector<int>> permute(vector<int>& nums) {
std::vector<int> ans;
backtracking(nums, ans);
return result;
}
void backtracking(vector<int> &nums, vector<int> &ans) {
if (ans.size() == nums.size()) {
result.push_back(ans);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (!isRepeat(ans, nums[i])) {
ans.push_back(nums[i]);
backtracking(nums, ans);
ans.pop_back();
}
}
}
代码解析：
- 这段穷举组合数的算法，基本部分包含了 终止条件，回溯，获取可选项三个部分
- 终止条件即需要回溯到什么程度得到一个排列。我们这里是，定义的ans变量，它的长度达到预设的长度，就说明新的排列产生了
- 回溯： 回溯是相对终止而言的，如果到了没有选择的地步，又没有产生新排列，就要回溯，表现在代码中就是ans长度要往回缩，选择下一个（由循环子 i 来迭代控制）可选项。
- 获取可选项，这里的代码不是太明显，只是用了一个 isRepeat 函数来判断新的循环子进来的项是否和已选的重复，如果不是，就可以加进去。
考虑变体问题 如果求的是 Permutation(m, n）如何处理
我们只需要稍微改一下代码就可以：
- 把终止条件是 ans的长度设置成到达 m 就可以。
代码
std::vector<std::string> result;
std::vector<char> available_number(const std::string& answer, int n)
{
std::vector<int> table(n + 1);
for (char c: answer) {
table[c - '0'] = 1;
}
std::vector<char> res;
for (auto i = 1; i <= n; ++i) {
if (table[i] != 1) {
res.push_back('0' + i);
}
}
return res;
}
void backtrack(std::string &ans, int n, int m) {
if (ans.length() == m) {
result.push_back(ans);
return;
}
std::vector<char> numbers = available_number(ans, n);
for (char c: numbers) {
ans.push_back(c);
backtrack(ans, n, m);
ans.pop_back();
}
}
std::vector<std::string> perm(int n, int m)
{
if (n == 0) {
return std::vector<std::string>();
}
std::string ans;
backtrack(ans, n, m);
return result;
}
这里稍微把 isRepeat 函数换成了一个可选项列表的函数，解决的问题是 ，数字字符串的排列问题。
计算组合数
问题： 计算一个包含 1~n n个元素的数组选取 m () 个元素的所有组合。
组合的情况和排列是类似的，差别之一就是组合数是无序的，比如 1234, 1243 是 两个不同的排列，对于组合而言，它们没有不同。
那么穷举的时候，需要注意的是，为了排除序意义上的重复，需要把序关系界定好。在上面的代码中，
终止条件是一样的，只要凑够 m 个成员就“收走”，不够的话，在可选的列表里选，但是，区别在这里，组合数的可选项算法不同，我们不仅仅是区分新元素是否和已有的“半组合”重复，而且要跑排除元素一样，序不同的情况。做到这一点，可以用这个方法： 当前槽位以后的元素才有资格被选入。
数组[1,2,3] 3选2组合的枝叶图，每次我们只能从当前元素的后面的元素选取，对于 3，其后无任何元素，所以没得选
代码修改如下：
// 组合穷举
vector<vector<int>> result;
bool in(const vector<int>& answer, int num) {
for (auto n : answer) {
if (num == n) {
return true;
}
}
return false;
}
void backtracking(int start, int n, int k, vector<int> & ans) {
/*
用start 标记当前的槽位，以遍在搜索过程中，列举某个“分岔”下可以选择的对象可以根据槽位来去重
*/
if (ans.size() == k) {
result.push_back(ans);
return;
}
for (auto i = start; i <= n; ++i) {
if (!in(ans, i)) {
ans.push_back(i);
backtracking(i + 1, n, k, ans);
ans.pop_back();
}
}
}
vector<vector<int>> combine(int n, int k) {
if (n < k || n <= 0 || k <= 0)
return result;
std::vector<int> ans;
backtracking(1, n, k, ans);
return result;
}
回溯+剪枝的基本技巧
以上通过组合数的穷举，大概可以看到回溯搜索的基本方法
- 确定终止条件。对于全排列，就是当一个“答案”长度增长到和可选数组的长度一样时；
- 剪枝。每次选择时，遍历所有可选项，也意味着你去掉了不可选的项。 回溯中最困难的部分也是在这里，千万不要 copy 例子中的方法，对于一些更复杂的问题，需要通过各种手段来缩短搜索路径。下面还有例子说明这一点。
对比组合和排列的剪枝方法：
求排列时，因为序的不同也是一种可能，所以在获得可选项时，只要与当前凑成的半成品排列的每个元素都不一样，就是可以选择的，同时，这么搞也不会出现一模一样的两个排列被加到结果里面（为什么？）
组合项则通过标记槽位的方式来去重。（在一些回溯问题中，有可能还会使用哈希表之类的结构来做去重） - 回溯。 当条件到最后也无法满足时，需要退回到某个“岔路口”。这就是回溯。
计算可能包含重复元素的数组的全排列
设 数组 A 是有自然数组成的数组，其中有可能包含重复元素，列举所有的排列，要求不能重复。
例子:
计算不重复的全排列，但是数组有重复元素。例如数组 [9,8,8] 的全排列是:
[8, 8, 9], [ 8, 9, 8], [9, 8, 8]
我们当做 A 是一个没有重复元素的全排列，使用计算无重复元素数组的全排列的方法穷举，然后考虑去重，这样就可以得到答案。当然，这是可以的，但是实际上更优的方案是，在穷举的过程中就做到“去重”。
数组 [9, 8, 8] 的全排列，不考虑重复，有
988, 988, 898, 898, 889, 889 6组
终止条件是一样的。区别是如何做“剪枝”。
思考：
- 第一个槽位，无重复元素，可选的成员是 9, 8, 8 , 由于两个 8 实际上长出的树是一模一样的，所以我们这里去掉一个 8， 所以第一个槽位的分岔是9 和 8，
- 9往下，第二个槽位，可选的元素是 8 和 8，去重一个，只有一个元素 8
- 继续第三个槽位， 可选元素只有 8，得到第一个排列 988；
- 对于第一步里的 8 分岔可以得到两个排列 889, 898。
算法要点： 每次根据已有的"半排列"计算可选列表时，进行去重即可。
代码：
vector<vector<int>> result;
vector<int> getAvailNumber(const vector<int>& ans, const vector<int>& nums) {
vector<int> res;
std::unordered_map<int, int> hash_table;
std::unordered_map<int, int> res_hash;
for (auto a: ans) {
hash_table[a] += 1;
}
for (auto num: nums) {
if (hash_table.find(num) == hash_table.end()) {
if (res_hash.find(num) == res_hash.end()) {
res.push_back(num);
res_hash[num] = 1;
}
} else {
hash_table[num] -= 1;
if (hash_table[num] == 0) {
hash_table.erase(num);
}
}
}
return res;
}
void backtrack(const vector<int>& nums, vector<int>& ans) {
if (ans.size() == nums.size()) {
result.push_back(ans);
return;
}
vector<int> avail_numbers = getAvailNumber(ans, nums);
for (int i = 0; i < avail_numbers.size(); ++i) {
ans.push_back(avail_numbers[i]);
backtrack(nums, ans);
ans.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> ans;
backtrack(nums, ans);
return result;
}
注意这里面的 getAvailNumbers 函数，虽然使用hash表，因为每次回溯都要运算，它还是比较低效的。在小规模的求解中无伤大雅，这个方法只是看起来比较“直观”，对于可选项的运算有没有更好的办法？
附录和总结
回溯搜索的效率和回溯函数的定义以及回溯过程密切相关，比如求全排列的回溯函数，被定义成
void backtracking(vector<int> &nums, vector<int> &ans)
每次有一个 isRepeat函数，显得非常低效。实际上候选数组可以在全局动态维护一个哈希表来实现，做到每步无须进入到 isRepeat 里面来搜寻答案
回溯函数可以修改成如下
std::unordered_map<int, int> hash_table; // 定义全局哈希表
void backtracking(vector<int> &nums, vector<int> &ans) {
if (ans.size() == nums.size()) {
result.push_back(ans);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (table[nums[i]] == 0) { // 直接使用全局哈希表效率大幅提升
ans.push_back(nums[i]);
table[nums[i]] = 1; // 动态维护
backtracking(nums, ans);
ans.pop_back();
table[nums[i]] = 0; // 回溯时要同步改一下标记
}
}
}
续篇
接下来会讨论八皇后和数独，幂集问题
网友评论