Complete Search (a.k.a Brute Force)

在学习递归之后，我们就学会了遍历问题状态空间的一种方式方法。这样我们就可以去尝试搜索这个问题的状态空间。这里，我们先来接触Complete search（也可以理解为暴力搜索）

Complete search is a general method that can be used to solve almost any algorithm problem. The idea is to generate all possible solutions to the problem using brute force, and then select the best solution or count the number of solutions, depending on the problem.

Complete search is a good technique if there is enough time to go through all the solutions, because the search is usually easy to implement and it always gives the correct answer. If complete search is too slow, other techniques, such as greedy algorithms or dynamic programming, may be needed.

例题:生成子集

For example, the subsets of {0,1,2} are 空集, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} and {0,1,2}.

  1. //An elegant way to go through all subsets of a set is to use recursion
  2. void search(int k) {
  3.     if (k == n) {
  4.        // 问题的边界
  5.        // process subset
  7.        return ;
  8.     } 
  10.     //不选
  11.     search(k+1);
  13.     //选
  14.     subset.push_back(k);
  15.     search(k+1);
  16.     subset.pop_back(); 
  17. }
  19. search(0); //调用
  20. //这个就是递归枚举子集

The following tree illustrates the function calls when n = 3. We can always choose either the left branch (k is not included in the subset) or the right branch (k is included in the subset).
（注意反复学习这个搜索树的执行过程）
image.png

  1. // 位运算枚举子集
  3. // Each subset of a set of n elements can be represented as a sequence of n bits, 
  4. // which corresponds to an integer between 0...2n −1. 
  5. // The ones in the bit sequence indicate which elements are included in the subset.
  7. //上面的程序，我们使用了一个vector来存储选了什么数字
  8. //这里，我们来学习一下位运算的枚举子集
  9. //这是一个拓展
  11. for (int b = 0; b < (1<<n); b++) {
  12.     vector<int> subset;
  13.     for (int i = 0; i < n; i++) {
  14.        if (b&(1<<i)) subset.push_back(i);
  15.     }
  16. }