搜索专项复习：未来的暴力打满
本文同步发布于：学习笔记：快速精通基本搜索
在我写这个学习笔记的时候，我默认读者已经熟练掌握 C++ 的基础操作，知道基础的递归，有普及的思维能力，一定程度上能阅读他人代码并且有初中的数学理解能力。
从递归到排列
从算法思想的角度来说，递归就是把大问题分成一个个子问题进行解决，而子问题和母问题具有相似性，所有可以通过递归调用自己进行解决。他与动态规划的区别在于——这些子问题具有可加性，也就是说，他们共同组成了整体的解。这样听来，递归似乎和分治算法很相似。
「例题」P1706 全排列问题：给定一个 $n$，输出 $1,2,3,\cdots n$ 的全排列。
我们考虑递归求解，每次循环从 $1\sim n$ 选数，选好了一个就填充下一个格子，然后把这个数拿出来，换一个数填。这样的思路让我们能够不重复不遗漏的遍历所有的情况。这里给出参考代码：
#include<bits/stdc++.h>
using namespace std;
int n,vis[100],ans[100];
void print(){
//输出已经选择好的排列
for(int i=1;i<=n;i++)
printf("%5d",ans[i]);
puts("");
}void search(int k){
//搜索到了第 k 格
if(k==n){//满了，输出
print();
return;
}for(int i=1;i<=n;i++){//循环作选择
if(!vis[i]){//如果没用过
vis[i]=1;ans[k+1]=i;//用它
search(k+1);//填充下一个格子
vis[i]=0;//把他拿出来，换一个填
}
}
}int main(){
cin>>n;
search(0);//从 0 开始搜索
return 0;
}
递归搜索所有的可能情况是暴力的基础形式，而这种形式的大多数情况，是 DFS 深度优先搜索。
搜索相关的知识
康托展开 一种特殊的哈希函数。
比如我们要判断 $2143$ 是 $\{1,2,3,4\}$ 中第几大的排列，我们可以考虑以下排列的和：
- 首位小于 $2$ 的排列：$1\times 3!=6$。
- 首位为 $2$ 第二位小于 $1$ 的排列：$0\times 2!=0$。
- 前两位为 $21$ 第三位小于 $4$ 的排列：$1\times 1!=1$。
- 前三位为 $214$ 第四位小于 $3$ 的排列：$0\times 0!=0$。
那么这样一个过程怎么归纳成公式呢？我们把他们加起来，答案是 $7$，也就是在这个排列之前有 $7$ 个排列，也就是说这是排名为 $8$ 的全排列，那么我们把巨大的一个范围的全排列映射到了一个小范围，就可以用传统 $vis$ 数组解决了。
我们把一个集合产生的全排列按字典序排序，则第 $X$ 个排列的计算公式如下：
$$X=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_i(i-1)!+\cdots a_2\times 1!+a_1\times 0!$$
$$X=\sum\limits_{i=1}^{n}a_i(i-1)!$$
当然也有逆康托展开，给定集合和排名，算出对应的排列，方法类似。
DFS 深度优先搜索
DFS (Depth First Search)，常常用于遍历树或图，而往往也可以代指利用递归来实现暴力枚举。图论意义上的 DFS 基本思想是「一条路走到底」，并且在走的过程中将走过的结点做好标记，确保每个点仅访问一次，并且在「走不通」时可以返回，继续尝试下一条路径。
广义上，使用递归调用自身实现的、每个状态仅访问一次的遍历，就可以成为深度优先搜索。在递归遍历一个问题所有的可能解（此时的复杂度往往是指数级别的）、搜索所有满足题意情况时，DFS 的复杂度较高，而对于遍历一个给定的图，他的复杂度并不会难以想象（除非在遍历的过程中有特定的任务，必须多次访问同一节点，譬如最短路）。
特别地，对于一个图的深度优先遍历步骤如下：
- 确定起点 $V_0$，进行标记。
- 对于其出边，标记为「已经走过」并递归遍历该节点，之后标记归零。
- 遍历下一节点。
这样一个实现简单，思路清晰的步骤使得 DFS 被广泛地使用，尽管时间复杂度较高（当遍历某些问题解答树时），但是可以「有序且完整」地遍历所有可能的情况，不容易出错。
「例题」：P1596 [USACO10OCT]Lake Counting S
题目大意：存在一个地图，由
W和.组成，求由W组成的连通块数量，一个方块和周围八个方块均连通。
此题是经典的搜索应用，由于数据范围极小，我们可以考虑一个一个格子 DFS，然后对于查出来的连通块去重，再计算总量……这样看来，似乎代码实现很麻烦，并且还是慢了点。
所以一个不错的想法诞生了：染色。
这一题当中，染色的核心思想就是将走过的格子进行一种标记，这种标记使得我们后面不会再遍历同样的一个连通块，既可以省去去重计数的过程，连 $vis$ 数组都省了。具体的办法就是在走到一个格子之后，就把他染成正常地面的颜色（更改为 . 字符）。
这样，我们的搜索就只做了染色这一件事，但是依然能完成任务，下面给出带注释的参考代码：
#include<bits/stdc++.h>
using namespace std;
//用方向数组决定往哪一个方向走
const int dx[]={1, 1, 1, 0, 0,-1,-1,-1};
const int dy[]={1, 0,-1, 1,-1,-1, 1, 0};
char a[105][105];
int ans,n,m;
//check 函数：判断某个地点是否可以走
bool check(int x,int y){
return (x>=0&&y>=0&&x<=n&&y<m&&a[x][y]=='W');
}void dfs(int x,int y){
//染色：把走过的地方渲染成和普通地面一样
a[x][y]='.';
for(int i=0;i<8;i++){
int xx=x+dx[i],yy=y+dy[i];
//确定方向后判断能不能走
if(check(xx,yy))dfs(xx,yy);//递归调用搜索
}return;//不返回在一些题目可能会出事
}int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
scanf("%s",a[i]);//避免换行问题，整行读入
for(int i=0;i<=n;i++){
for(int j=0;j<m;j++){
if(a[i][j]=='W'){
//是一个之前没有走过的水潭，进行染色
dfs(i,j);
ans++;//可以走的地方多了一处
}
}
}printf("%d",ans);
return 0;
}
DFS 不仅能搜索一个图，还能搜索一些状态，譬如「是否选择」，这道题就是一个典型应用。对于「是否选择」形成的结果树进行深度优先遍历，找到所有的结果。对于每一个可能的结果（指数级数量的结果）进行判断。这里给出参考代码：
#include<bits/stdc++.h>
using namespace std;
int a[20],n,k;//依照题目所设
bool isp(int x){//是否是素数
if(x<=1)return 0;
if(x==2)return 1;
for(int i=2;i*i<=x;i++){
if(x%i==0)return 0;
}return 1;
}int f(int cho,int sum,int st,int ed){
//cho剩余的 k，sum累加和，st和ed为选取范围
//递归生成组合，循环累计
if(!cho)return isp(sum);
int s=0;
for(int i=st;i<=ed;i++){
s+=f(cho-1,sum+a[i],i+1,ed);
}return s;
}int main(){
cin>>n>>k;//输入
for(int i=1;i<=n;i++)cin>>a[i];
cout<<f(k,0,1,n);//调用
}
BFS 广度优先搜索
广度优先搜索，是一种效率上不错，程序也容易理解的算法。
假设现在我们在某一个状态（可能是某个格子，某个结点，某个情况），而接下来我们要搜索与之相关的所有情况，如何保证搜索顺序？这需要用到队列（queue，FIFO 先进先出表），将所有需要搜索的状态压进队列中。这样，我们只要一个 while 循环就可以按顺序遍历所有的情况了。
实现上，给出 C++ 风格的伪代码：
void BFS(){
定义队列 q;
while(队不空){
取出队头状态 x;
q 队头出队;
处理 x;
for(...){
将 x 的相关状态入队;
}
}
}
「例题」：P1443 马的遍历
题目大意：有一个 $n\times m$ 的棋盘 $(1<n,m\le 400)$，在某个点上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步？
我们发现数据范围大，如果用 DFS 可能会重复搜索到同一个方块很多遍（第一次到达的可能不是最优解），而且也不是很容易确定什么时候应该回溯，怎么办呢？
这种题目是 BFS 的典型应用，因为按照顺序向外广度遍历，第一次遇到格子就是最优的解（想一想，为什么），所以我们可以很方便地从起始点开始向外进行 BFS——你可以看做一个从起始节点向外扩散的过程，比如一滴墨水滴在清水中，向外进行流动（从二维的视角看，第一次扩散到的时候走的就是最近的路）。
每次入队的时候（而不是走到的时候）把入队的格子需要走的步数标记为“当前步数” $+1$，具体的实现参考代码：
#include<bits/stdc++.h>
using namespace std;
//方向数组
const int dx[]={2,-2, 2,-2,-1, 1,-1, 1};
const int dy[]={1, 1,-1,-1, 2, 2,-2,-2};
int n,m,x,y,mp[405][405];
struct grid{
//用于存储格子
int x,y;
};
bool check(int x,int y){
return (x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]==-1);
}void bfs(){
queue<grid>q;//开一个队列
q.push((grid){x,y});//把第一个格子压进去
while(!q.empty()){//没有遍历完
//取出当前要处理的格子
int xx=q.front().x,yy=q.front().y;
q.pop();//当前状态要处理了，不留在“待处理”中了
for(int i=0;i<8;i++){//所有方向
int xxx=xx+dx[i],yyy=yy+dy[i];
if(check(xxx,yyy)){//如果能走
q.push((grid){xxx,yyy});//放到“待处理”之中
mp[xxx][yyy]=mp[xx][yy]+1;//要处理到这里，就要多一步了
}
}
}return;
}int main(){
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!(i==x&&j==y))mp[i][j]=-1;
}
}bfs();
for(int i=1;i<=n;i++){//输出
for(int j=1;j<=m;j++){
printf("%-5d",mp[i][j]);
}puts("");//换行
}return 0;
}
还有另外一道很简单的题目 P1451 求细胞数量，可以用类似于 DFS 篇的染色方法通过，当然用简单 BFS 也可以，参考代码：
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int m,n,cnt,vis[1001][1001]={0};
char p[1001][1001];
struct grid{
int x,y;
};
queue<struct grid> q;
void BFS(){
cnt++;
while(!q.empty()){
int x=q.front().x;
int y=q.front().y;
vis[x][y]=1;
q.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(yy<m&&xx<n&&xx>=0&&yy>=0){
if(!vis[xx][yy]&&p[xx][yy]!='0'){
q.push({xx,yy});
}
}
}
}return;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
char c;
cin>>c;
if(c=='0')p[i][j]='0';
else p[i][j]='1';
}
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
if(vis[i][j]==0&&p[i][j]!='0'){
q.push({i,j});
BFS();
}
}cout<<cnt<<endl;
return 0;
}
你可以试一试 P1135 奇怪的电梯，这是一道不错的搜索练手题，有特殊条件的搜索可以看看 P3956 [NOIP2017 普及组] 棋盘。
棋盘一题的代码，我是远古时代写的，可能不是很容易理解，但是还是贴上来：
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int m,n,p[101][101];
int f[101][101];//记录最小花费
struct grid{
int x,y;
int cost,col;
bool mag;
};
void init(){
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
p[i][j]=-1;
f[i][j]=INF;
}
}
}queue<grid>q;
void BFS(){
while(!q.empty()){
//访问队头元素
int x=q.front().x,y=q.front().y;
int cs=q.front().cost,co=q.front().col;
bool ma=q.front().mag;
if(x==m&&y==m)f[m][m]=min(cs,f[m][m]);
if(cs>=f[x][y]){
q.pop();
continue;
}f[x][y]=cs;q.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(yy<=m&&xx<=m&&xx>0&&yy>0){
if(p[xx][yy]!=-1){
if(co==p[xx][yy]){
grid t={xx,yy,cs,co,true};
q.push(t);
}else{
grid t={xx,yy,cs+1,p[xx][yy],true};
q.push(t);
}
}else if(ma){
grid t={xx,yy,cs+2,co,false};
q.push(t);
}
}
}
}return;
}int main(){
cin>>m>>n;
init();
for(int i=0;i<n;i++){
int x,y,c;
cin>>x>>y>>c;
p[x][y]=c;
}q.push((grid){1,1,0,p[1][1],true});
BFS();
if(f[m][m]==INF)puts("-1");
else cout<<f[m][m]<<endl;
return 0;
}
常见的搜索剪枝
记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会大大降低算法的执行效率。
记忆化搜索：
而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算用到的时候直接取出结果，避免重复运算，因此极大的提高了算法的效率。我们可以把记忆化搜索看做是动态规划（虽然他本来就是）。
剪枝：
- 可行性剪枝
当目前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判断不可行，直接返回。
- 排除等效冗余
当几个子树具有完全相同的效果的时候，只选择其中一个搜索。
- 最优性剪枝
在我们用搜索方法解决最优化问题的时候的一种常用剪枝。当搜索还未结束时，记录的状态已经比当前保存的最优解更劣，那么此方案一定无效，停止搜索并回溯即可。
- 顺序剪枝
普遍来讲，搜索的顺序是不固定的，对一个问题来说，算法可以进入搜索树的任意的一个子节点。
但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。
双向搜索
我们有时候会遇到一种问题，起点和终点是已知的，需要确定从起点到终点需要多少步。这时候，如果仅仅从起点进行搜索（以 BFS 为例），那么搜索树是巨大的，对于一个 $m$ 叉的搜索树，有 $m^n$ 中可能性。
但是，如果我们从起点和终点一起搜索呢？
这样的话，搜索的可能性一下子降到了 $2\times m^{n\div 2}$，相当于直接开方，复杂度的优化极其优秀。具体到算法上，有两种类型：双向 BFS 和双向迭代加深，这里主要介绍双向 BFS。
至于迭代加深和相关的搜索，会在之后的章节和大家探讨。
与朴素的 BFS 不同，双向广搜同时维护两个队列，轮流（或者说依次）入队。由于实现多线程不是很现实，单线程的交替也能起到类似的效果，每次拓展我们都可以用 hash 的思想对搜索的结果进行标记，当一个状态被两个队列的搜索过程标记时，就可以结束搜索、得出结果。
双向 BFS 可以使用的条件是知道起点和终点，并且双向移动不会影响答案，譬如 「例题」HDU 1401 Solitaire。这是一个双向搜索的标准题型，考虑分别从起点和终点进行搜索，各自走 $4$ 步，如果有交点则说明可以到达，由于这道题细节巨多，所以给出参考代码（参考代码是同学编写、依照标程修改风格、LOJ 格式化后压行的结果）：
#include <bits/stdc++.h>
using namespace std;
struct grid {
int x, y;
bool check() {return (x < 8 && x >= 0 && y >= 0 && y < 8);}
};
struct node {
grid p[4];
int step;
} s, e;
char vis[8][8][8][8][8][8][8][8];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int mat[10][10];
bool cmp(grid a, grid b) { //排序
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}void make_map(node a) { //标记4个点的位置
mat[a.p[0].x][a.p[0].y] = 1;
mat[a.p[1].x][a.p[1].y] = 1;
mat[a.p[2].x][a.p[2].y] = 1;
mat[a.p[3].x][a.p[3].y] = 1;
}int judge(grid a) {
return (mat[a.x][a.y]);
}void make_vis(node a, char w){ //标记状态
vis[a.p[0].x][a.p[0].y][a.p[1].x][a.p[1].y][a.p[2].x][a.p[2].y][a.p[3].x][a.p[3].y] = w;
}char get_vis(node a) { //获得状态
return vis[a.p[0].x][a.p[0].y][a.p[1].x][a.p[1].y][a.p[2].x][a.p[2].y][a.p[3].x][a.p[3].y];
}bool bfs() {
node u, v;
memset(vis, 0, sizeof(vis));
make_vis(s, '1');make_vis(e, '2');
s.step = 0;e.step = 0;
queue<node>q, t;
q.push(s);t.push(e);
while (!q.empty() || !t.empty()) {
if (!q.empty()) {
u = q.front();q.pop();
memset(mat, 0, sizeof(mat));
make_map(u);
if (u.step >= 4)continue;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
v = u;v.step++;
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
if (judge(v.p[j])) { //跳步
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
}sort(v.p, v.p + 4, cmp);
if (get_vis(v) == '1')continue;
else if (get_vis(v) == '2')return 1;//可以到达终点
make_vis(v, '1');
q.push(v);
}
}
}if (!t.empty()) {
u = t.front();t.pop();
memset(mat, 0, sizeof(mat));
make_map(u);
if (u.step >= 4)continue;
if (get_vis(u) == '1')return 1;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
v = u;v.step++;
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
if (judge(v.p[j])) {
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
}sort(v.p, v.p + 4, cmp);
if (get_vis(v) == '1')return 1;
else if (get_vis(v) == '2')continue;
make_vis(v, '2');
t.push(v);
}
}
}
}return 0;
}int main() {
while (~scanf("%d%d", &s.p[0].x, &s.p[0].y)) {
for (int i = 1; i < 4; i++)scanf("%d%d", &s.p[i].x, &s.p[i].y);
for (int i = 0; i < 4; i++)scanf("%d%d", &e.p[i].x, &e.p[i].y);
for (int i = 0; i < 4; i++) {
s.p[i].x--;s.p[i].y--;
e.p[i].x--;e.p[i].y--;
}sort(s.p, s.p + 4, cmp);
sort(e.p, e.p + 4, cmp);
bfs() ? puts("YES") : puts("NO");
}return 0;
}
迭代加深搜索
有这样的一种搜索树，它几乎无限宽也几乎无限深，对于这种情况怎么办呢？单纯的 DFS 可能会陷入无限的递归无法得出结果，BFS 的话队列空间是无法承受的，而你不知道具体的终点所在所以也不能用双向 BFS，这时候我们可以采用迭代加深搜索：IDDFS。
是的，这是一种以 BFS 为核心思想，以 DFS 为实现手段的算法，具体过程如下：
- 设定深度为 $1$，如果深搜到答案则结束。
- 如果没搜到答案，更改深度为 $2$，搜索前两层。
- 如果没搜到答案，更改深度为 $3$，重复此过程。
在每一层的迭代看起来特别像 BFS，而实现则是用 DFS。这种算法的前提是必须有解，再进一步，我们确定最优解在浅层的时候，应该使用 IDDFS。
剪枝可以使用乐观估计函数，估计从当前深度到找到最终的解「至少」还需要多少步，或者距离找到最终的解还需要扩展多少层，如果超过了设定的最大深度，就不可能再当前深度找到解了，可以退出这一轮搜索。
关于例题的内容，洛谷似乎没有足够板子的练迭代加深搜索的题目，那就看看这个吧 hzaukotete：搜索进阶-迭代加深搜索。
A* 启发式搜索和 IDA* 迭代加深启发式搜索
我们会发现，单纯的 BFS 要找到一个目的地，几乎要走遍所有的结点，比如从 $(1,1)\to (n,n)$ 类型的题目。而启发式搜索很好的解决了这种「盲目」引起的问题，换言之，启发式搜索引入了一个「方向感」的概念。
我们知道有一种搜索叫做 GFS（真的有吗），全程是 Greedy First Search 即贪心最优搜索，只前往当前距离终点最优的节点，这样子在开阔的图中可以很快获得答案（因为贪心搜索的收敛速度很快），但是往往不能得到正确答案，在特殊情况下甚至不能得到答案，譬如：
...........
.########..
........#..
S.......#.E
........#..
.########..
...........
显然，对于这种图，从 $s$ 出发的贪心搜索会卡在这个凹槽之中不能出来。那怎么解决呢？只要使用正确的估价函数，我们就可以避免这种误区——估价函数是 A* 算法的核心。引入一个概念叫做曼哈顿距离，具体请见 Heartlessly 的博客 - 常用距离算法详解.
设 $x$ 是现在的状态，那么 $f(x)$ 就是他的评估函数，存在：
$$f(x)=g(x)+h(x)$$
其中 $g(x)$ 是从起点到当前状态的代价（譬如走过的步数），而 $h(x)$ 则是预估的到终点的代价。可以发现，$h(x)$ 决定了 A* 算法的优劣，我们需要一种不能漏掉最优解的 $h(x)$。同时，存在两条重要的性质：
- 若 $h(x)=0$ 那么该算法就是朴素 BFS。
- 若 $g(x)=0$ 那么该算法就是朴素贪心搜索。
这样我们可以避开很多不必要搜到的点，大大优化我们的搜索过程。
将 A* 套入迭代加深的思想，就是 IDA*，这两种算法解决的问题较难（说人话就是作者菜），这里有例题但没有代码。
IDA* 例题：P2324 [SCOI2005]骑士精神
发现“在 $15$ 步以内”这一限制条件，绝佳的迭代加深。而估价函数则考虑“每次空白格子和黑白棋子交换，最优的情况就是每次都把黑白棋子移动到目标格子。”进行一些优化可以通过此题，具体参考题解区。
后话
这就是基础搜索的内容了。
感谢阅读，写的挺累的，那我就求个赞吧。