回溯和深度优先遍历(一)

2021-12-30 本文已影响0人东方胖

本文谈谈回溯算法和深度优先搜索。

回溯法可以看成是一种暴力搜索，穷举。看起来“暴力”给人的印象似乎都是比较简单，而效率很慢的，效率慢确实是事实，但简单则不然。

回溯穷举的复杂性本质是因为问题本身具有迅速增长的规模。

典型的回溯穷举问题是求组合排列。

对于正整数 m, n 求其组合数 Combination(m, n)和排列数 Permutation(m, n）

假设 $m \leq n$ , 排列组合公式如此计算。

$\mathrm{C}_n^m = \frac{n!} {m!(n-m)!}$
$\mathrm{A}_n^m = \frac{(n - m)!} {n!}$

这个公式说明了穷尽排列和组合的计算规模，简单举一个例子， $\mathrm{C}_{10}^{5} = 252$ , 将 m, n 增加一倍到 20 , 10, $\mathrm{C}_{20}^{10} = 30240$ 增长非常迅速。

回溯法求排列

数字 “123” 的全排列如何穷举。我们知道它所有的排列是

123, 132, 213, 231, 312, 321

一个包含 n 个不同字符的串有 $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 ( $m \leq n$ ) 个元素的所有组合。
组合的情况和排列是类似的，差别之一就是组合数是无序的，比如 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组

终止条件是一样的。区别是如何做“剪枝”。

思考：

1. 第一个槽位，无重复元素，可选的成员是 9, 8, 8 , 由于两个 8 实际上长出的树是一模一样的，所以我们这里去掉一个 8，所以第一个槽位的分岔是9 和 8，
1. 9往下，第二个槽位，可选的元素是 8 和 8，去重一个，只有一个元素 8
1. 继续第三个槽位，可选元素只有 8，得到第一个排列 988；
1. 对于第一步里的 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; // 回溯时要同步改一下标记
           }
        }
    }

续篇

接下来会讨论八皇后和数独，幂集问题