(紫书,感谢作者)第7章暴力求解法

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

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

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

一、简单枚举

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

二、枚举排列

1、生成1-n的排列

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

  1. void print_permutation(int n, int* A, int cur) {
  2. if (cur == n) {
  3. for (int i = 0; i < n; ++i) printf("%d ", A[i]);
  4. return;
  5. }
  6. for (int i = 1; i <= n; ++i) {
  7. int ok = 1;
  8. for (int j = 0; j < cur; ++j)
  9. if (A[j] == i) ok = 0;
  10. if (ok) {
  11. A[cur] = i;
  12. print_permutation(n, A, cur+1);
  13. }
  14. }
  15. }

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时就能够递归调用,下面是填改后的部分:

  1. else for (int i = 0; i < n; ++i) {
  2. int c1 = 0, c2 = 0;
  3. for (int j = 0; j < cur; ++j) if (A[j] == P[i]) c1++;
  4. for (int j = 0; j < n; ++j) if (P[j] == P[i]) c2++;
  5. if (c1 < c2) {
  6. A[cur] = P[i];
  7. print_permutation(n, P, A, cur+1);
  8. }
  9. }

修改后我们又进行了测试,发现程序能够输出了,但是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)就可以了(要提前排序哦),下面是演示代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. int main() {
  5. int n, p[10];
  6. scanf("%d", &n);
  7. for(int i = 0; i < n; ++i) scanf("%d", &p[i]);
  8. sort(p, p+n);
  9. do {
  10. for (int i = 0; i < n; ++i) printf("%d ", p[i]);
  11. printf("\n");
  12. } while (next_permutation(p, p+n));
  13. return 0;
  14. }

大家可以去试一下。

三、子集生成

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

1、增量构造法

下面是代码:

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

2、位向量法

  1. void print_subset(int n, int* B, int cur) {
  2. if (cur == n) {
  3. for (int i = 0; i < n; ++i)
  4. if (B[i]) printf("%d ", i);
  5. printf("\n");
  6. return;
  7. }
  8. B[cur] = 1;
  9. print_subset(n, B, cur+1);
  10. B[cur] = 0;
  11. print_subset(n, B, cur+1);
  12. }

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

3、二进制法

二进制的有便是1,无便是0(按位运算符的使用大家自行百度)

下面是代码

  1. void print_subset(int n, int s) {
  2. for (int i = 0; i < n; ++i)
  3. if (s&(1<<i)) printf("%d ", i);
  4. printf("\n");
  5. }
  6. for (int i = 0; i < (1<<n); ++i)
  7. print_subset(n, i);

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

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

是否使用集合中的元素(1代表使用0代表不使用),下面是代码。

  1. // LUOGU P1219
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. int main() {
  6. int n;
  7. scanf("%d", &n); // 假设n展开成二进制是集合里有的东西;
  8. for (int i = 4; i >= 0; --i) // n 的 二进制
  9. if (n&(1<<i)) printf("1");
  10. else printf("0");
  11. printf("\n");
  12. for (int left = n; left; left = (left-1)&n) { // 子集生成
  13. for (int i = 4; i >= 0; --i)
  14. if (left&(1<<i)) printf("1");
  15. else printf("0");
  16. printf("\n");
  17. }
  18. return 0;
  19. }

输入: 31(二进制11111)

输出:大家自行去测试

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

四、回溯法

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

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

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

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

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

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

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

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

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

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

下面是八皇后的代码:

  1. #include <cstdio>
  2. #include <cstring>
  3. using namespace std;
  4. const int maxn = 30;
  5. int C[maxn];
  6. int vis[3][maxn];
  7. int n, tot;
  8. void search(int cur) {
  9. if (cur == n) {
  10. if (tot < 3) {
  11. for (int i = 0; i < n; ++i) printf("%d ", C[i]+1);
  12. printf("\n");
  13. }
  14. tot++;
  15. }
  16. else for (int i = 0; i < n; ++i)
  17. if (!vis[0][i] && !vis[1][cur+i] && !vis[2][i-cur+n]) {
  18. C[cur] = i;
  19. vis[0][i] = vis[1][cur+i] = vis[2][i-cur+n] = 1;
  20. search(cur+1);
  21. vis[0][i] = vis[1][cur+i] = vis[2][i-cur+n] = 0;
  22. }
  23. }
  24. int main() {
  25. scanf("%d", &n);
  26. search(0);
  27. printf("%d\n", tot);
  28. return 0;
  29. }

这里就不给注释了,大家自行理解(锻炼读代码的能力)。

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

五、路径寻找问题

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

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

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

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

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

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

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

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

hash:

  1. const int hashsize = 1000003;
  2. int head[hashsize], next[maxstate];
  3. void init_lookup_table() { memset(head, 0, sizeof(head)); }
  4. int hash(State& s) {
  5. int v = 0;
  6. for (int i = 0; i < 9; ++i) v = v * 10 + s[i];
  7. return v % hashsize;
  8. }
  9. int try_to_insert(int s) {
  10. int h = hash(st[s]);
  11. int u = head[h];
  12. while (u) {
  13. if (memcpy(st[u], st[s], sizeof(st[s])==0) return 0;
  14. u = next[u];
  15. }
  16. next[s] = head[h];
  17. head[h] = s;
  18. return 1;
  19. }

STL(set):

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

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

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

状态图来描述。

六、迭代加深搜索

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

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

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

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

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

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

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

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

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

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

发表评论

表情:
评论列表 (有 0 条评论,327人围观)

还没有评论,来说两句吧...

相关阅读

    相关 《以为友

    如果实在不知道要干吗,不如投身热门行业,参与大城市的竞争,并且让自己获胜,让自己赚钱。所谓成熟,就是理解了世界的复杂性,不再要求一味走直线。在路线问题上,拥抱折射,在最终...

    相关 《以为友

    带着上一个领域的知识积木进入下一个、再下一个领域时,这些知识汇聚到一起,形成了一个可怕的复杂系统——大师思想从中诞生。不能解决当下问题的,降低关注度。并不是否认这个知识好...

    相关 《以为友

    知识源头,就像河流的源头一样,是知识发源的地方,是知识刚刚被创造出来的地方。但是在今天知识爆炸、终身学习的时代,“为什么”(why)、“学什么”(what)、“如何学”(...

    相关 《以为友

    好的战略就是达成“投入和产出的非线性”,用80%的时间学习20%的精华,快速占领赛道的头部,吸引最好的资源,互联最好的人才,共同成为第一名。世界已经从过去的高理性时代,进...

    相关 算法之暴力求解

    算法之暴力求解 暴力求解的简单解释: 很多问题都可以”暴力解决”——不用太动脑筋,把所有的可能性都列举出来,然后一一实验。尽管