前言
搜索包含宽度优先搜索(以下简称宽搜)与深度优先搜索(以下简称深搜)。他们也各有优点。但是在处理问题时,自己怎么好打代码,就选择哪一种搜索方式,结合题目灵活选择。洛谷同步更新中
搜索本章本身难度不是很大,其难度主要集中在于例如双向搜索,$ A^*(A_{star}) $、$IDA^*$估值函数的编写以及深搜剪枝上,但其意义重大,可以帮助我们锻炼暴力解题的思维,在考试中不挂零,同时也可以实现对拍。那么,让我们一同来看下面的内容吧。
目录
$1.1\ $ 更新日志
$2.1\ BFS $
-
$2.1.1$ $ Flood \ Fill $
-
$2.1.2$ 最短路模型
-
$2.1.3$ 多源$BFS$
-
$2.1.4$ 最小步数模型
-
$2.1.5$ 双端队列广搜
-
$2.1.6$ 双向广搜
-
$2.1.7$ $A^* (A_{star})$
$2.2\ DFS $
-
$2.2.1$ 连通性模型
-
$2.2.2$ 搜索顺序
-
$2.2.3$ 剪枝与优化
-
$2.2.4$ 迭代加深
-
$2.2.5$ 双向$DFS$
-
$2.2.6$ $IDA^*$
$1.1\ $更新日志
- $2021.10.6$ 进行了校正以及补充。
$2.1.1\ Flood\ Fill$
$Flood\ Fill$算法(又称洪水灌注算法)是一个很简单的算法,也是最基础的宽搜算法。以下用$AcWing$上的三道例题来展示本算法。
由于每个题目思路略有差异,但大体相同,且$Flood\ Fill$算法本身极其简单,所以不过多讲解这三道例题。总体而言,技巧在于使用类似于
int dx[8]={-1,-1,-1,0,0,1,1,1} , dy[8]={-1,0,1,-1,1,-1,0,1};
的代码(上述代码源自$T3$),进行不同方向的搜索。而$dx$数组和$dy$数组也都要因题而异。比如要模拟中国象棋中的“马”,就要用到如下代码
int dx[8]={-2,-2,-1,-1,1,1,2,2} , dy[8]={-1,1,-2,2,-2,2,-1,1};
而这,也是贯穿搜索这一整章的基本搜索顺序。
$2.1.2$ 最短路模型
关于最短路模型,有多种解法,如$Dijkstra$及其堆优化版,$SPFA$等等,而实际上它们也都是源自宽搜。以下同样用$AcWing$上的三道例题来展示本模型。
其中$T1$ 迷宫问题 和$T2$ 武士风度的牛 很简单,不作解释。$T3$中,关于数组范围,由于本题中明显在接近极限距离 $1e5$ 时,$x*2$方案一定不如$x+1$或$x-1$的用时少,因而数组仅需开到稍大于$1e5$即可。
其中使用稍大于$1e5$的数组是因为保证在$50000$左右数据中保证方案最优。
$2.1.3$ 多源 $BFS$
多源$BFS$解决的关键在于将这多个源点先入队,在进行正常的宽搜操作。如在上述例题中,需要先把所有的”$1$”先入队,然后再进行操作,如此可以保证所有点在遍历时,最终都是由距离它最近的 “$1$” 点所扩展到的,从而实现的整体最优。
另外,在本例题中,出现的 曼哈顿距离 也是在$A^*$与$IDA^*$中经常出现的估值函数写法(关于估值函数会具体在对应小节中讲解)。
$A[i][j]$ 与 $A[k][l]$ 之间的 曼哈顿距离 可理解为由点 $(i,j)$ 到点 $(k,l)$ 水平或垂直方向运动的最小距离(记为$dist(A[i][j],A[k][l])$),则
$ dist(A[i][j],A[k][l])=|i-k|+|j-l| $
曼哈顿距离 也是在$ A^*(A_{star}) $、$IDA^*$ 中编写估值函数的一种方式。
同样地,欧几里得距离也是需要在题目中注意的一种距离。
$2.1.4$ 最小步数模型
这个例题作为模拟题,极度恶心,代码很长。最小步数模型也主要是搜索的大模拟,当遇到这种题目时,要耐下心来,去慢慢读懂题意,去清楚每一步操作以及其顺序。在记录遍历顺序时,可以使用一个数组(本处使用 $pre$ 数组)
char g[2][4];
map<string,pair<char,string>> pre;
map<string,int> dist;
void set(string state)
{
for(int i=0;i<4;i++) g[0][i]=state[i];
for(int i=7,j=0;j<4;i--,j++) g[1][j]=state[i];
}
string get()
{
string res;
for(int i=0;i< 4;i++) res+=g[0][i];
for(int i=3;i>=0;i--) res+=g[1][i];
return res;
}
string move0(string state)//对应操作A
{
set(state);
for(int i=0;i<4;i++) swap(g[0][i],g[1][i]);
return get();
}
string move1(string state)//对应操作B
{
set(state);
int v0=g[0][3],v1=g[1][3];
for(int i=3;i>=0;i--)
{
g[0][i]=g[0][i-1];
g[1][i]=g[1][i-1];
}
g[0][0]=v0,g[1][0]=v1;
return get();
}
string move2(string state)//对应操作B
{
set(state);
int v=g[0][1];
g[0][1]=g[1][1];
g[1][1]=g[1][2];
g[1][2]=g[0][2];
g[0][2]=v;
return get();
}
int bfs(string start,string end)
{
if(start==end) return 0;
queue<string> q;
q.push(start);
dist[start]=0;
while(!q.empty())
{
auto t=q.front();
q.pop();
string m[3];
m[0]=move0(t);
m[1]=move1(t);
m[2]=move2(t);
for(int i=0;i<3;i++)
if(!dist.count(m[i]))
{
dist[m[i]]=dist[t]+1;
pre[m[i]]={'A'+i,t};
q.push(m[i]);
if(m[i]==end) return dist[end];
}
}
return -1;
}
int main()
{
int x;
string start,end;
for(int i=0;i<8;i++)
{
cin>>x;
end+=char(x+'0');
}
for(int i=1;i<=8;i++) start+=char('0'+i);
int step=bfs(start,end);
cout<<step<<endl;
string res;
while(end!=start)
{
res+=pre[end].first;
end =pre[end].second;
}
reverse(res.begin(),res.end());
if(step>0) cout<<res<<endl;
return 0;
}
$2.1.5$ 双端队列广搜
本题解法比较巧妙,我们需要首先把电路板上每一个格子点(交叉点)看作无向图中的节点,我们认为两个节点 $x$ 和 $y$ 是某个小方格的两个对角,那么如果说 $x$ 和 $y$ 的线段无需旋转即可通过 ,那么我们可以认为边权为 $0$ ;反之,如果 $x$ 和 $y$ 线段需要旋转才可通过,那么我们可以认为边权为 $1$ ,即要旋转一次才能够连上。
所以,我们便可以得到一张完美的边权 $0$ 或 $1$ 的无向图,那么和普通广搜一样,我们唯一的改变就是,如果说当前新状态的边权为 $0$ ,那么我们就放到队头先走,因为我们要 同时 满足 两端性和单调性 ,而为了这个单调性,如果说当前新状态边权为 $1$ ,那么我们就只能压入队尾。
因而我们可以得到,解决双端队列宽搜,我们要不仅要保证队列的双端性,更要在入队时保证其单调性。
$2.1.6$ 双向广搜
双向广搜适用与已知起点和目标点的 方案过多 的搜索题。其核心思想在于 用空间换时间 。
例如本题,如果直接进行 $BFS$ ,则方案数会高达 $K^{10}$ ,会 $TLE$ 或 $MLE$ ,采用双向$BFS$则可以将需要枚举的方案数降至 $2K^5$ ,寻找两次搜索的交集中的最优解。如下图所示:
)
因为图没了,所以放个链接
$2.1.7\ \ \ $ $A^*$ $(A_{star})$
本题使用$AcWing$上的两道例题来展示本算法。
由于原题题意很容易理解,题目也很容易想到方法去解,所以这里就不再赘述,仅在本节最后放上两题的无注释代码(后续有时间会跟进注释),直接介绍 $A^*$算法的关键。
$A^*$ 算法的关键在于估值函数(以下使用 $f()\ $ )的编写。在$A^*$算法中,估计值必须要低于实际值,具体原因有兴趣的小伙伴可以去各大网站寻找答案,本处也不作赘述。
$AcWing\ 178.$ 第K短路
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define PII pair<int,int>
#define PIII pair<int,PII>
#define x first
#define y second
const int N=1e3+10,M=1e5+10;
int n,m;
int h[N],rh[N],w[M],e[M],ne[M],idx=0;
int dist[N];
bool st[N];
int S,T,K,cnt[N];
void add(int h[],int a,int b,int c)
{
e[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
void dijkstra()
{
priority_queue<PII,vector<PII>,greater<PII> > heap;
heap.push({0,T});
memset(dist,0x3f,sizeof dist);
dist[T]=0;
while(heap.size())
{
PII t=heap.top();
heap.pop();
int b=t.y;
if(st[b]) continue;
st[b]=true;
for(int i=rh[b];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[b]+w[i])
{
dist[j]=dist[b]+w[i];
heap.push({dist[j],j});
}
}
}
}
int astar()
{
priority_queue<PIII,vector<PIII>,greater<PIII> > heap;
heap.push({dist[S],{0,S}});
while(heap.size())
{
PIII t=heap.top();
heap.pop();
int ver=t.y.y,distance=t.y.x;
cnt[ver]++;
if(cnt[T]==K) return distance;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(cnt[j]<K)
heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
}
}
return -1;
}
int main()
{
memset(h,-1,sizeof h);
memset(rh,-1,sizeof rh);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
add(h,a,b,w);
add(rh,b,a,w);
}
scanf("%d%d%d",&S,&T,&K);
if(S==T) K++;
dijkstra();
printf("%d\n",astar());
return 0;
}
$AcWing\ 179.$ 八数码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<queue>
using namespace std;
#define PIS pair<int,string>
int f(string str)
{
int res=0;
for(int i=0;i<str.size();i++)
if(str[i]!='x')
{
int t=str[i]-'1';
res+=abs(i/3-t/3)+abs(i%3-t%3);
}
return res;
}
string bfs(string start)
{
map<string,int> dist;
map<string,pair<string,char> > prev;
priority_queue<PIS,vector<PIS>,greater<PIS> > heap;
string end="12345678x";
dist[start]=0;
heap.push({f(start),start});
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char op[4]={'u','r','d','l'};
while(heap.size())
{
PIS t=heap.top();
heap.pop();
string state=t.second;
if(state==end) break;
int x,y,step=dist[state];
for(int i=0;i<state.size();i++)
if(state[i]=='x')
{
x=i/3,y=i%3;
break;
}
string source=state;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0&&xx<3&&yy>=0&&yy<3)
{
swap(state[x*3+y],state[xx*3+yy]);
if(!dist.count(state)||dist[state]>step+1)
{
dist[state]=dist[source]+1;
prev[state]={source,op[i]};
heap.push({dist[state]+f(state),state});
}
swap(state[x*3+y],state[xx*3+yy]);
}
}
}
string res;
while(end!=start)
{
res+=prev[end].second;
end=prev[end].first;
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
string start,seq;
char c;
while(cin>>c)
{
start+=c;
if(c!='x') seq+=c;
}
int cnt=0;
for(int i=0;i<8;i++)
for(int j=i;j<8;j++)
if(seq[i]>seq[j]) cnt++;
if(cnt&1) printf("unsolvable\n");
else cout<<bfs(start)<<endl;
return 0;
}
综合来讲,估值函数可以计算最理想的花费,从而达到上述估计值低于实际值的目的。
$2.2.1$ 连通性模型
连通性模型 与 Flood Fill 可以用相同的思路来解决,仅仅是用深搜或用宽搜的差距,都可以用作搜索的入门题目,因而此处也仅贴出$AcWing$上的两道例题,以供读者练习。
对于搜索初学者而言,要注意什么时候需要回复现场,而什么时候又不需要回复现场,这会影响到搜索的正确性。
接下来的$2.2.2$ 搜索顺序、$2.2.3$ 剪枝与优化、$2.2.4$ 迭代加深、$2.2.5$ 双向$DFS$ 都是搜索中优化时间复杂度的常见方法。它们也是搜索的核心内容,并且可以帮助我们更深刻地理解题目,从而尽可能地接近正解。
$2.2.2$ 搜索顺序
搜索顺序的优化可以帮助我们的深搜更先找到目标状态。就比如状态较大,那么我们由大到小遍历就比由小到大遍历快,从而达到了优化时间复杂度的目的。下面是来自$AcWing$的三道例题。
上面三道例题中,$ T2\ \ AcWing\ 1117.$ 单词接龙 便是一个披着字符串外衣的搜索题。而很多的搜索题,图论题,也都是披着字符串外衣的。因而在读题时也要注意看透表面,深入本质当中。
话题回到搜索顺序,不同题目中,我们应该根据不同题目的性质,去选择搜索顺序。尤其在数据很大的情况下,搜索顺序的优化总会有意想不到的效果。
如果无法判断选何种搜索顺序更优,则可以都写一遍,然后进行两个搜索的对拍(尽管时间很长)。(但是都用到搜索了,那多得一个点不都是成功嘛)
$2.2.3$ 剪枝与优化
剪枝是深搜中优化时间复杂度的最常见方式,如下是剪枝的几种方法:
-
排除等效冗余
-
可行性剪枝
-
最优性剪枝
$AcWing$中以四道例题来讲解剪枝与优化,我们也同样以这四道例题来解释上述三种剪枝方法。
-
1、排除等效冗余,顾名思义就是排除相同状态。就比如在 $ T3 $ 中,只要某种长度的小木棍拼接失败,就用 $while$ 循环跳过其余相同长度的小木棍。
-
2、可行性剪枝,即如果由这个点向下的这棵搜索树全部都是不合法的,我们就提前将其剪枝掉。就比如 $T3$ 中如果这根大木棒的第一个小木棍就无法拼接成功,则这个节点向下的搜索树都是不合法的(本处不予证明)。
-
3、最优性剪枝,即如果由这个点向下的这棵搜索树全部都不是最优的,我们就提前将其剪枝掉。就比如 $T1$ 中如果已经用的缆车大于已搜索到的最小答案,那么这一个节点向下的一整棵树都不是最优解,于是我们就提前剪枝掉。
$2.2.4$ 迭代加深
在搜索过程中,可能会出现答案所在层数很低,但是搜索程序却在更深的层数中无法自拔的现象。对此我们可以采用迭代加深的方法来依次增加搜索层数。
在代码中我们可以
bool dfs(int depth,int max_depth);
while(!dfs(1,depth))//主函数中调用
{
depth++;
}
来维护一个最大只有 $depth$ 层的搜索树。尽管一次一次递增会浪费掉搜索前几层搜索的时间,但是与搜索树的叶子节点随着层数的增加而指数级增长的状态数相比,采用迭代加深的方法可以很大程度上减少搜索时间。
$2.2.5$ 双向$DFS$
如同 $BFS$ 有双向,$DFS$也有双向。两者在本质上是相同的。都是同样地进行两次搜索,一次从起点开始,另一次从终点逆向开始,最终在两次搜索的交集中寻找最终答案。
对于本题,秦淮岸灯火阑珊 大佬的题解很详细,我也仍只是一知半解,因而不多做解释。
$2.2.6$ $IDA^*$
$IDA^*$ 同样与 $A^*$ 算法相差无几,都是添加了一个估值函数的搜索。
由于这类算法主要核心在于估值函数的编写,因而本处不对两题的题意以及思路进行过多解释,仅对估值函数做少量描述。
$ T1\ \ AcWing\ 180. $ 排书
int f()//q数组表示书的数量
{
int cnt=0;
for(int i=0;i+1<n;i++)
{
if(q[i+1]!=q[i]+1) cnt++;//计数仍未排成规则数列的数字
}//因而在理想状态下,即每次操作都可以把数列调成规则数列
return (cnt+2)/3;
}
$ T2\ \ AcWing\ 181. $ 回转游戏
int center[8]={6,7,8,11,12,15,16,17},q[N];
int f()
{
int num[4]={0};//用来计数中间八个位置中,每个数字出现的次数
for(int i=0;i<8;i++) num[q[center[i]]]++;
int s=0;//s表示出现次数最多的次数
for(int i=1;i<4;i++) s=max(s,num[i]);
return 8-s;
//在理想状态下,每次操作可以在中间位置上让出现最多的数字多出现一次,因而最少需要8-s次操作
}
结语
在整个搜索这一章中,最重要的最核心的内容就是优化。要打好搜索也需要多加练习,才可以更好地选择优化方式,打出更好的暴力。但学习搜索,更多的是为了学习思想,考虑剪枝的同时,我们也加深了对题目的理解,从而增大了做出正解的可能性。
如果本文在语法,表述或代码上有任何问题,欢迎在评论区指正。最后祝大家一同进步呀~ $\ \ \ $另外都看到这儿了,不给点个赞嘛?
赞。
%%%,大佬