（紫书，感谢作者）第7章暴力求解法

今天药忘吃喽~ 2021-12-09 07:51 211阅读 0赞

今天，我们谈一谈紫书上面的内容——暴力求解法

对于一道问题来说，我们是可以借助计算机运算快的特点，将所有可能的情况全部（不一定是全部）列出来，然后去寻找我们想要的答案，这就是暴力求解了，但暴力求解绝对不是“完全的暴力”，并不能够完全的将所有的情况列出来，有些情况我们可以排除的，主要的思想还是将所有的可能找出来，在细节上我们需要提前排除不可能的情况，这样才使得既“暴力”又“高效”，下面说一说几个经典的类型与所需要的知识吧！

一、简单枚举

就是将所有的情况枚举出来，可能是无数个for循环叠加形成的，由于这种枚举没有太多知识要求，这里就不说了。

二、枚举排列

1、生成1-n的排列

我们采用递归的方法，将所有可能的排列求出来，下面是代码：

void print_permutation(int n, int* A, int cur) {
      if (cur == n) { 
        for (int i = 0; i < n; ++i) printf("%d ", A[i]);
        return; 
      }
      for (int i = 1; i <= n; ++i) {
        int ok = 1; 
        for (int j = 0; j < cur; ++j) 
          if (A[j] == i) ok = 0; 
        if (ok) {
          A[cur] = i; 
          print_permutation(n, A, cur+1); 
        }
      }
    }

2、生成可重集的排列

我们生成了1-n的排列，那么生成可重集的排列行吗？当然可以。

我们在1-n的排列的基础上加上修改就能够得到了，我们首先对数组P进行排序，我们把之前代码中的A\[cur\]=i改成A\[cur\]=P\[i\]然后调用print\_permutation(n, P, A, 0)，

通过测试，我们发现输入1 1 1后程序什么也不输出，由于我们修改后的程序仍然有禁止A数组中出现重复的作用，所以我们需要计算相同元素的数量，

就是统计A\[0\]~A\[cur-1\]中P\[i\]出现的次数c1, 然后与P数组出现P\[i\]的次数c2进行比较，当c1 < c2时就能够递归调用，下面是填改后的部分：

else for (int i = 0; i < n; ++i) {
      int c1 = 0, c2 = 0; 
      for (int j = 0; j < cur; ++j) if (A[j] == P[i]) c1++; 
      for (int j = 0; j < n; ++j) if (P[j] == P[i]) c2++; 
      if (c1 < c2) {
        A[cur] = P[i];
        print_permutation(n, P, A, cur+1); 
      }
    }

修改后我们又进行了测试，发现程序能够输出了，但是1 1 1输出了很多遍，为什么？这三个1其实是相同的，但程序先尝试了第一个1进行递归，又尝试了第二个1进行

递归，然后又尝试了第三个1进行了递归，所以才会输出很多个相同的结果，我们可以在for(int i = 0; i < n; ++i) 下面加上if(!i || P\[i\]!=P\[i-1\])就行了。

程序终于正确了。

3、解答树

我们了解了生成1-n的排列以及可重集的排列，我们是时候了解一下解答树了，解答树，顾名思义就是"解答”的树，它来帮助我们了解程序是如何一步步从“一步都没做”

到“逐步生成完整解”的过程。如果某个问题可以由许多个步骤得到，而每个步骤有若干种选择，且可以使用递归枚举法进行实现，它的工作方式可以用解答树来描述，

对于解答树，我们可以在后面试着画解答树，它能够帮助我们分析规模，还可以帮助我们提高程序效率（剪枝），这个我在后面会说。

4、下一个排列

我们可以采用上面生成可重集的排列来生成下一排列，同时，我们也要发挥c++的作用，我们使用algorithm中的next\_permutation(p,p+n)就可以了（要提前排序哦），下面是演示代码：

#include <cstdio>
    #include <algorithm> 
    using namespace std; 
    int main() { 
      int n, p[10]; 
      scanf("%d", &n); 
      for(int i = 0; i < n; ++i) scanf("%d", &p[i]); 
      sort(p, p+n); 
      do {
        for (int i = 0; i < n; ++i) printf("%d ", p[i]);
        printf("\n"); 
      } while (next_permutation(p, p+n)); 
      return 0; 
    }

大家可以去试一下。

三、子集生成

之前介绍了排列生成的算法，接下来给大家介绍子集生成的方法，为了简单起见，本节讨论的子集中没有重复的元素。

1、增量构造法

下面是代码：

void print_subset(int n, int* A, int cur) {
      for (int i = 0; i < cur; ++i) printf("%d ", A[i]); // 打印当前集合 
      printf("\n"); 
      int s = cur ? A[cur-1]+1 : 0; // 确定当前元素的最小可能值 
      for (int i = s; i < n; ++i) {
        A[cur] = i; 
        print_subset(n, A, cur+1);  // 递归构造子集 
      }
    }

2、位向量法

void print_subset(int n, int* B, int cur) {
      if (cur == n) { 
        for (int i = 0; i < n; ++i) 
          if (B[i]) printf("%d ", i); 
        printf("\n"); 
        return; 
      }
      B[cur] = 1; 
      print_subset(n, B, cur+1); 
      B[cur] = 0; 
      print_subset(n, B, cur+1); 
    }

相比于增量构造法，位构造法的速度会相对较慢（从解答树的方向去思考，试一试）

3、二进制法

二进制的有便是1，无便是0（按位运算符的使用大家自行百度）

下面是代码

void print_subset(int n, int s) {
      for (int i = 0; i < n; ++i) 
        if (s&(1<<i)) printf("%d ", i); 
      printf("\n");     
    }
    
    for (int i = 0; i < (1<<n); ++i)
      print_subset(n, i);

这种方法的代码十分好写。

通过紫书上面做的题，我认为有必要向大家介绍二进制法构造集合的方法，对于一个集合来讲，我们使用二进制来表示

是否使用集合中的元素（1代表使用0代表不使用），下面是代码。

// LUOGU P1219
    #include <cstdio> 
    #include <cstring>
    using namespace std; 
    
    int main() { 
      int n; 
      scanf("%d", &n); // 假设n展开成二进制是集合里有的东西；
      for (int i = 4; i >= 0; --i) // n 的 二进制 
        if (n&(1<<i)) printf("1"); 
        else printf("0"); 
      printf("\n"); 
      for (int left = n; left; left = (left-1)&n) { // 子集生成 
        for (int i = 4; i >= 0; --i) 
          if (left&(1<<i)) printf("1");
          else printf("0"); 
        printf("\n"); 
      }
      return 0;
    }

输入： 31（二进制11111）

输出：大家自行去测试

这就是二进制枚举子集的好处，大家可以去看看，输入17试一试......

四、回溯法

对于排列生成还是子集枚举，我们都是采用生成-检查这样的步骤来确定得到我们要的答案，这样是无法减小枚举量从而加快程序效率的，所以我们

采用回溯法，顾名思义，回溯，就是遇到不行，回去，何必撞墙呢（超时）？从解答树的角度我们也能够明白，越早回去我们走的路越少，

效率就越高，在做题时也一样，我们思路在最开始是正确的后面成功的机率越高，我们的生活与信息竞赛也许就是一棵解答树吧。

把话题转回来，我们说一说回溯的经典例题——八皇后问题

大家可以从洛谷或者其他oj看到这道题，题意我就不说了，很多人应该明白，为了让大家了解回溯的作用，我们从生成-检查与回溯对比来说明，

首先，我们可以采用生成子集的方法，64个格子中选择子集，每个子集内部有8个格子，那么子集一共有2^64个，这太大了，并不能够解决问题；

我们还可以这样想“从64个格子中选出8个”，这样通过组合数我们能够算出有4.426\*（10^9）种方案，但仍然不够好；

我们分析问题就能够得到不可能两个皇后在同一行，那我们就让每个皇后各占一行啊，这就成了全排列（1-n)生成问题，8！=40320个，这样足够好了。

然后根据列、对角线不能够重复的原则在生成全排列某一位加以运用，这样我们就能够很快的得出答案了。

通过上面的分析，我们知道了当把问题分成若干步骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象称为回溯。正是因为这个原因，递归枚举算法常被称为回溯法，应用十分普遍，它能够将解答树的枝叶剪掉，这样就节省了不必要的计算，所以回溯法对提高效率有着非常明显的作用，而如何进行“剪枝”（剪去解答树的枝叶）是十分重要的，这需要长期的练习与经验总结。

下面是八皇后的代码：

#include <cstdio> 
    #include <cstring> 
    using namespace std; 
    const int maxn = 30; 
    
    int C[maxn]; 
    int vis[3][maxn];
    int n, tot; 
     
    void search(int cur) {
      if (cur == n) {
        if (tot < 3) {
          for (int i = 0; i < n; ++i) printf("%d ", C[i]+1); 
          printf("\n"); 
        }
        tot++;
      }
      else for (int i = 0; i < n; ++i) 
        if (!vis[0][i] && !vis[1][cur+i] && !vis[2][i-cur+n]) {
          C[cur] = i;
          vis[0][i] = vis[1][cur+i] = vis[2][i-cur+n] = 1; 
          search(cur+1);
          vis[0][i] = vis[1][cur+i] = vis[2][i-cur+n] = 0;   
        }
    }
    
    int main() { 
      scanf("%d", &n); 
      search(0);
      printf("%d\n", tot); 
      return 0;
    }

这里就不给注释了，大家自行理解（锻炼读代码的能力）。

这里我们回溯还要注意到：搜索对象的选取，最优性剪枝（记录当前最优值），减少无用功。（这些建议参照紫书去做题慢慢了解）。

五、路径寻找问题

隐式图：程序动态生成的。

本节与前面介绍的回溯法不同，回溯法是找到一个或所有满足约束的解，而状态空间搜索一般是找到一个从初始状态到目标状态的途径。

这里最经典的问题便是八维码问题了，与八皇后一样，大家自己去看题意，这道题我们初步判断使用dfs求解（因为是求最短最快的路径），然后我们还需要什么吗？

我们需要记录状态，由于bfs我们可能会得到重复的状态，而这些状态并不需要并且会使程序运行速度变慢，所以我们采用判重（判断重复）的方法来，怎么判断呢？

我们需要根据题来定义一个“好”状态，就是能够让我们快速知道是否重复的状态，我们可以采用STL或者hash进行判重，这里我想说STL的set要比hash慢很多，

set是基于某种排序，hash是将不同的状态与数对应起来，我前几天发了一篇博客，用了set很慢，转化成hash快了很多，所以说如果不太能够确认hash的正确性的

情况下我们可以先用STL写出正确但慢的此程序，然后以此作为“跳板”写出hash的快的程序，我们可以进行“对拍”（以后我可能会说）来测验hash的正确性，

下面我就简单给出几个hash（不包括编码解码（完美哈希），由于后面的章节未学）与STL方法的代码：

hash:

const int hashsize = 1000003; 
    int head[hashsize], next[maxstate]; 
    void init_lookup_table() { memset(head, 0, sizeof(head)); } 
    int hash(State& s) {
      int v = 0; 
      for (int i = 0; i < 9; ++i) v = v * 10 + s[i]; 
      return v % hashsize;     
    }
    int try_to_insert(int s) {
      int h = hash(st[s]); 
      int u = head[h]; 
      while (u) {
        if (memcpy(st[u], st[s], sizeof(st[s])==0) return 0; 
        u = next[u]; 
      }
      next[s] = head[h]; 
      head[h] = s; 
      return 1; 
    }

STL(set):

set<int> vis; 
    void init_lookup_table() { vis.clear(); }
    int try_to_insert(int s) {
      int v = 0;
      for (int i = 0; i < 9; ++i) v = v * 10 + st[s][i];     
      if (vis.count(v)) return 0;
      vis.insert(v); 
      return 1;
    }

完整代码还请看紫书作者刘汝佳的代码

我们说一说“状态”这个词，简单来讲，它就是“对系统当前状况的描述”，如果我们将状态想象成图中的结点，我们就可以得到状态图，对于路径寻找问题，我们使用

状态图来描述。

六、迭代加深搜索

迭代加深搜索是一种应用很广的算法，它可以像回溯法那样找一个解，也可以像状态空间搜索一样去寻找一条路径。

埃及分数问题（自行看题意），通过分析，我们发现解答树非常“恐怖”，深度确定不了，广度确定不了（想一想，为什么？）所以我们没有办法搜索，那么我们必须

要有一个“标准”，标准是什么呢？就是将深度确定下来，去搜索，我们可以将深度依次增大，去确定是否能够满足要求，而且深度上限可以进行剪枝，我们估计当前

到答案（分数）所需要最短距离，如果当前深度+最短距离>maxd那么需要剪枝了，这样的算法就是IDA\*，大家可以去查A\*算法以及去看其他博客，自然就能明白了

IDA\*，A\*就是（g(n)+h(n)>maxd)......,这里我就不说了。

其中迭代加深搜索还能够解决能够用BFS或者回溯法解决的问题。

以上就是紫书第7章的内容了（不包括例题与练习），通过第7章的学习，我们能够解决很多问题了，即使不能够得到满分（超时），由于“暴力”，所以

可以将很多不会的问题通过暴力解决出来，好的优化甚至能够AC，所以这章十分重要，另外我说一下自己的感受吧，在学习这一章的过程中，要学会对象的分析与处理

（可能是UVa的题太坑了），从不同的角度思考问题，敢于实现（敢于写代码，不知道自己的搜索等等能不能成功），如果需要优化那就需要彻底的优化下去，对问题有所总结，然后再说一说如何确定这类问题，我们可以通过数据范围进行判断，一般搜索题的范围不会特别大（我不确定），写的时候想清楚，我还发现即使一道题做对了也要看题解（有的大神写的程序简单又快）尽量让练习的题发挥最大的作用，坚持不懈，努力下去，我相信终究会成功的。

转载于:https://www.cnblogs.com/yifeiWa/p/11176792.html