(紫书,感谢作者)第7章暴力求解法
今天,我们谈一谈紫书上面的内容——暴力求解法
对于一道问题来说,我们是可以借助计算机运算快的特点,将所有可能的情况全部(不一定是全部)列出来,然后去寻找我们想要的答案,这就是暴力求解了,但暴力求解绝对不是“完全的暴力”,并不能够完全的将所有的情况列出来,有些情况我们可以排除的,主要的思想还是将所有的可能找出来,在细节上我们需要提前排除不可能的情况,这样才使得既“暴力”又“高效”,下面说一说几个经典的类型与所需要的知识吧!
一、简单枚举
就是将所有的情况枚举出来,可能是无数个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的题太坑了),从不同的角度思考问题,敢于实现(敢于写代码,不知道自己的搜索等等能不能成功),如果需要优化那就需要彻底的优化下去,对问题有所总结,然后再说一说如何确定这类问题,我们可以通过数据范围进行判断,一般搜索题的范围不会特别大(我不确定),写的时候想清楚,我还发现即使一道题做对了也要看题解(有的大神写的程序简单又快)尽量让练习的题发挥最大的作用,坚持不懈,努力下去,我相信终究会成功的。
转载于//www.cnblogs.com/yifeiWa/p/11176792.html
还没有评论,来说两句吧...