dfs 和 bfs
dfs
dfs，是英文名 deep-first-search 的缩写，它的思想是一搜到底，撞墙回头。这一种思想是基于递归和栈实现的，打个比方，你在迷宫里面，发现有岔路口，先向左走，走了一段时间发现是死路，退回去之后走右边。
基于 dfs，有一种术语叫做：回溯。回溯的思想是如果要走这一条路，那么就踩上去脚印，如果撞墙，回退的过程就把脚印擦掉。这一种思想避免了很多情况：比如重复走，不走可以走的路，记录答案错误等。
下面，给出 dfs 的伪代码：
void dfs(node dep){//node 为深度的类型
if(check(dep)){//答案撞墙了
change(ans);//更新答案
return;
}
for(auto i:plan[dep]){//枚举每一种扩展方法
if(check(i)){//下一个节点撞墙了
continue;
}
moveplan(GO_TO,i);//去下一个节点
dfs(i);//下一个节点
moveplan(COME_BACK,i);//从下一个节点回溯
}
}
例题
这一道题目要求我们输出全排列。考虑使用 dfs。定义深度 $dep$ 为填到第几个数，那么则有 $dep=n+1$ 的时候结束。结束的时候，我们需要输出，于是使用 $ans$ 数组记录答案。当然，重复的数字不能出现，所以还需要使用 $vis$ 来记录是否出现过。
#include<bits/stdc++.h>
#define MAXN 11
using namespace std;
int n,ans[MAXN];
bool vis[MAXN];
void dfs(int dep){
if(dep==n+1){
for(int i=1;i<=n;++i){
printf("%5d ",ans[i]);
}
putchar('\n');
return;
}
for(int i=1;i<=n;++i){
if(!vis[i]){
vis[i]=true;
ans[dep]=i;
dfs(dep+1);
vis[i]=false;
}
}
}
int main(){
scanf("%d",&n);
dfs(1);
return 0;
}
bfs
bfs 是英文名 breath-first-search 的缩写，它的思想是逐步扩展，搜到即停。也就是 bfs 是把每一个深度的所有节点扩展出来，一旦出现了答案，并且答案要最优且深度最浅，那么这个就是答案，可以停止搜索了。
这么来讲，你需要找到一棵树上最靠前的一个权值为 $2$ 的节点，那么可以用 bfs 来实现。bfs 将每一个节点的下表压入队列，然后逐步弹出队头。如果看到了 $2$，那就是最靠前的。
下面，给出 bfs 的伪代码：
inline void bfs(node st,node en){//node 为扩展答案的类型
queue<node> q;
q.push(st);
moveplan(GO_TO,st);//去下一个节点
while(!q.empty()){
node front=q.front();
q.pop();
if(front==en){
ans=front;//找到答案
return;
}
moveplan(COME_BACK,front);//从下一个节点回溯
for(auto i:plan[front]){//枚举每一种扩展方法
if(check(i)){//下一个节点撞墙了
continue;
}
q.push(i);
moveplan(GO_TO,i);//去下一个节点
}
}
ans=unfound();//无解
}
例题
这一道题目可以看作最优性答案，所以用 bfs 实现。考虑加一个偏移数组 $d$，来表示向上走还是向下走。然后枚举向上走还是向下走，压入队列。
#include<bits/stdc++.h>
#define MAXN 202
using namespace std;
struct node{
int pos,step;
};
int n,ans,a[MAXN],vis[MAXN];
int d[2]={-1,1};
queue<node>q;
inline void bfs(int st,int en){
queue<node> q;
q.push((node){st,0});
vis[st]=true;
while(!q.empty()){
node front=q.front();
q.pop();
if(front.pos==en) {
ans=front.step;
return;
}
for(int i=0;i<2;++i){
int nxt=front.pos+d[i]*a[front.pos];
if(nxt>=1&&nxt<=n&&!vis[nxt]){
q.push((node){nxt,front.step+1});
vis[nxt]=true;
}
}
}
ans=-1;
}
int main(){
int st,en;
scanf("%d %d %d",&n,&st,&en);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
bfs(st,en);
printf("%d",ans);
return 0;
}
总结
来分析一下，dfs 适用于统计答案个数的题目，优点是空间最大是 $\operatorname{O}(n)$，但是时间可能是指数级别的。bfs 适用于求最优性答案的题目，优点是较快，但是由于 queue 耗用空间很大，空间最坏能够达到指数级大小。
剪枝
剪枝的思想是把搜索树的一部分一定不满足答案的部分剪掉，如果剪枝精妙，再加上一些小优化或者玄学优化，可以把指数级别的搜索优化到多项式级别，甚至获得高分乃至 $100$ 分。
剪枝分为以下几个：
正确性剪枝
这个通常来讲是优化正确性的，比如 dfs 例题，里面使用了 $vis$ 数组进行剪枝，减去了 ${1,1,1}$ 的不合法情况。
最优性剪枝
这个是 bfs 能够很快的思想之一，就是如果当前答案没有已经求出的答案那么优，就不扩展。bfs 就是证明了搜到深度最小的答案，不可能有答案比它再优了才退出的。
记忆化搜索
有时候，dfs 会多次访问同一个节点。比如 $dfs(3,3)$ 可以扩展成 $dfs(2,2)$，而你又在此之前查询了 $dfs(2,2)$，这明显可以用一个数组 $f$ 来存储。在此之前，有 $dfs(2,2)$ 的存在，那么设 $cnt$ 为访问 $dfs(2,2)$ 的次数，$t$ 为 $dfs(2,2)$ 的时间，那么可以优化 $(cnt-1)\times (t-1)$ 的时间。
例题1
这一道题目在 dfs 的基础上需要有剪枝。很明显，$dep$ 曾的 $i$ 必须从上一个 $i$ 枚举到之前的答案加上 $(k-dep)\times i$，这是一个剪枝。
#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
void dfs(int dep,int sum,int last){
if(dep==k){
ans+=(sum==n);
return;
}
for(int i=last;sum+(k-dep)*i<=n;++i){
dfs(dep+1,sum+i,i);
}
}
int main(){
scanf("%d %d",&n,&k);
dfs(0,0,1);
printf("%d",ans);
return 0;
}
例题2
这一道题目需要使用最优性剪枝，即如果拼出的目标长度大于了目标长度，那就跳过，因为这样肯定有一个更优的答案小于目标长度。
#include<bits/stdc++.h>
#define MAXN 101
using namespace std;
int n,cnt,maxi=INT_MIN,mini=INT_MAX;
int a[MAXN],ans[MAXN];
void dfs(int dep,int now,int len,int pos){
if(!dep){
printf("%d",len);
exit(0);
}
if(now==len){
dfs(dep-1,0,len,maxi);
return;
}
for(int i=pos;i>=mini;--i){
if(ans[i]&&i+now<=len){
--ans[i];
dfs(dep,i+now,len,i);
++ans[i];
if(!now||now+i==len){
break;
}
}
}
}
int main(){
scanf("%d",&n);
int len,sum=0;
while(n--){
scanf("%d",&len);
if(len<=50){
a[++cnt]=len;
maxi=max(maxi,len);
mini=min(mini,len);
++ans[len];
sum+=len;
}
}
len=sum>>1;
for(int i=maxi;i<=len;++i){
if(sum%i==0){
dfs(sum/i,0,i,maxi);
}
}
printf("%d",sum);
return 0;
}
例题3
这一道题目是求 $w(x,y,z)$，很明显满足 dfs。考虑记忆化搜索，这样，就可以避免大量的无意义运算。最多 $20^3$ 次的不同的运算求出 $ans$，那么之后就只需要求 $w(x,y,z)=ans_{x,y,z}$ 了。
#include<bits/stdc++.h>
#define MAXN 22
using namespace std;
typedef long long ll;
ll ans[22][22][22];
inline ll dfs(int x,int y,int z){
if(x<=0||y<=0||z<=0){
return ans[0][0][0]=1;
}
if(x>20||y>20||z>20){
return dfs(20,20,20);
}
if(ans[x][y][z]){
return ans[x][y][z];
}
if(x<y&&y<z){
return ans[x][y][z]=dfs(x,y,z-1)+dfs(x,y-1,z-1)-dfs(x,y-1,z);
}
return ans[x][y][z]=dfs(x-1,y,z)+dfs(x-1,y-1,z)+dfs(x-1,y,z-1)-dfs(x-1,y-1,z-1);
}
int main(){
while(true){
ll x,y,z;
scanf("%lld %lld %lld",&x,&y,&z);
if(x==-1&&y==-1&&z==-1){
return 0;
}
printf("w(%lld, %lld, %lld) = %lld\n",x,y,z,dfs(x,y,z));
}
return 0;
}
折半搜索
折半搜索是可以将指数折半的一种搜索，它的思想就是确定某一种意义下的 $head1$ 和 $head2$，然后往后搜索。有些情况，搜索出来会使得 $tail1=tail2$，而有些情况，会使得 $tail1+1=head2$。不管怎么样，如果最开始是 $k^n$ 会爆，那么折半搜索能优化到 $k^{\lfloor\frac{n}{2}\rfloor+1}$ 的复杂度。
例题
这一道题目可以枚举每一种状态选或者不选，复杂度 $2^n$。但是 $n$ 可以达到 $40$，所以考虑折半。折半搜索的结果是可以拼凑出多少种不同的方案，用 dfs 实现。一半枚举 $2^{(1,\lfloor\frac{n}{2}\rfloor)}$，一半枚举 $2^{(\lfloor\frac{n}{2}\rfloor+1,n)}$，然后二分查找出耗费了前半段那么多钱，后半段能够耗费多少钱，然后统计即可。
#include<bits/stdc++.h>
#define MAXN 41
#define MAXM 1<<20|1
using namespace std;
typedef long long ll;
int n,cnta,cntb;
ll m,w[MAXN],suma[MAXM],sumb[MAXM],ans;
void dfs(int l,int r,ll sum,ll a[],int &cnt){
if(sum>m){
return;
}
if(l>r){
a[++cnt]=sum;
return;
}
dfs(l+1,r,sum+w[l],a,cnt);
dfs(l+1,r,sum,a,cnt);
}
int main(){
scanf("%d %lld",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld",&w[i]);
}
int mid=n>>1;
dfs(1,mid,0,suma,cnta);
dfs(mid+1,n,0,sumb,cntb);
sort(suma+1,suma+1+cnta);
for(int i=1;i<=cntb;++i){
ans+=upper_bound(suma+1,suma+1+cnta,m-sumb[i])-suma-1;
}
printf("%lld",ans);
return 0;
}
A-star
A-star 属于半玄学算法。它的思想是对于每一个点 $p$，都有从 $head$ 到 $p$ 的函数 $pre(p)$，也有从 $p$ 到 $tail$ 的函数 $nxt(p)$，还有估价函数 $goal(p)=pre(p)+nxt(p)$，然后以估价函数的值来搜索。在此之前，我们还需要引入一个定理：优先队列优化 bfs。
优先队列优化 bfs 在一次性扩展深度不一定加一的 bfs 中用于规划最小值，每一次取出的是最优的，那就满足了 bfs 的自带的最优性剪枝。优先队列优化本质上也是贪心加上最优性剪枝。
这些函数满足三角形不等式，所以 bfs 的证明是正确的。事实上，A-star 还可以变式成堆优化的 Dijiestra。
例题
这道题目就是求 K 短路径。可以考虑设置 $pre$ 函数为当前距离，这个可以用 Dijiestra 预处理。之后的 $nxt$ 可以考虑用当前路径的长度，这样还是满足三角形不等式的，所以，之后用 A-star 跑。
#include<bits/stdc++.h>
#define MAXN 1001
#define MAXM 10001
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
struct node{
int next,to;
ll dis;
}edge[MAXM][2];
struct cmp{
int pos;
ll dis;
};
int n,m,k,cnt[2],head[MAXN][2];
ll dis[MAXN];
bool vis[MAXN];
inline bool operator<(const cmp &x,const cmp &y){
return x.dis+dis[x.pos]>y.dis+dis[y.pos];
}
inline void addedge(int x,int from,int to,ll dis){
edge[++cnt[x]][x].to=to;
edge[cnt[x]][x].dis=dis;
edge[cnt[x]][x].next=head[from][x];
head[from][x]=cnt[x];
}
inline void dijiestra(){
priority_queue<pli,vector<pli>,greater<pli> > q;
q.push(make_pair(0ll,1));
memset(dis,0x7f,sizeof(dis));
dis[1]=0;
vis[1]=true;
while(!q.empty()){
int front=q.top().second;
q.pop();
vis[front]=false;
for(int i=head[front][1];i;i=edge[i][1].next){
int to=edge[i][1].to;
if(dis[to]>dis[front]+edge[i][1].dis){
dis[to]=dis[front]+edge[i][1].dis;
if(!vis[to]){
q.push(make_pair(dis[to],to));
vis[to]=true;
}
}
}
}
}
inline void A_star(){
priority_queue<cmp> q;
q.push((cmp){n,0ll});
while(!q.empty()){
cmp front=q.top();
q.pop();
if(front.pos==1){
printf("%lld\n",front.dis);
if((--k)==0){
return;
}
continue;
}
int from=front.pos;
for(int i=head[from][0];i;i=edge[i][0].next){
int to=edge[i][0].to;
q.push((cmp){to,front.dis+edge[i][0].dis});
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
if(!k){
return 0;
}
while(m--){
int from,to;
ll dis;
scanf("%d %d %lld",&from,&to,&dis);
addedge(0,from,to,dis);
addedge(1,to,from,dis);
}
dijiestra();
A_star();
while(k--){
puts("-1");
}
return 0;
}
ID
ID 是 iterate-deepning 的缩写，中翻迭代加深搜索。主要思想是结合了 dfs 和 bfs 的思想，每一次设置一个深度 $dep$，如果深度超过 $dep$，那就再把 $dep+1$，如果搜到了最佳答案，那就结束。ID 优化了 bfs 的空间不足和 dfs 的时间不足。
例题
这一道题目可以考虑枚举个数，用 ID 来搜。然后要搜分母，统计答案。此外，还需要正确性剪枝。每一次如果 $x\times nxt\ge y\times(maxdep-dep+1)$，那么一定不合法。
#include<bits/stdc++.h>
#define MAXN 202
#define MAXM 1001
using namespace std;
typedef long long ll;
int maxdep;
ll n,m,zip[MAXN],ans[MAXN];
bool f=true;
inline bool check(){
for(int i=maxdep;i>=1;--i){
if(!ans[i]){
return true;
}else if(ans[i]!=zip[i]){
return zip[i]<ans[i];
}
}
return false;
}
void iddfs(int dep,ll x,ll y,ll last){
if(dep==maxdep){
if(y%x){
return;
}
zip[maxdep]=y/x;
if(check()){
for(int i=1;i<=maxdep;++i){
ans[i]=zip[i];
}
}
f=false;
return;
}
for(ll i=max(last,y/x+1);x*i<y*(maxdep-dep+1);++i){
ll nxtx=x*i-y;
ll nxty=y*i;
zip[dep]=i;
ll g=__gcd(nxtx,nxty);
iddfs(dep+1,nxtx/g,nxty/g,i+1);
}
}
int main(){
scanf("%lld %lld",&n,&m);
f=true;
for(maxdep=2;f;++maxdep){
memset(zip,0,sizeof(zip));
iddfs(1,n,m,n/m+1);
}
--maxdep;
for(int i=1;i<=maxdep;++i){
printf("%lld ",ans[i]);
}
}
IDA-star
IDA-star 是结合了 A-star 和 ID 的算法，它的具体实现是 dfs，只不过是每次需要 $goal$ 进行扩展。A-star 优化的是 bfs，ID 优化的是所有广搜，那么正好 ID 可以优化 A-star。相较于 A-star，IDA-star 的优势是空间。
例题
这一道题目，需要在 $15$ 步内走完，很像 ID 的 $maxdep$ 限制条件，然后可以考虑 $goal$ 函数定义成至少要多少步，典型的 A-star，之后，再加上一些剪枝优化即可。
#include<bits/stdc++.h>
#define MAXN 6
using namespace std;
char a[MAXN][MAXN];
char mp[MAXN][MAXN]={
{'0','0','0','0','0','0'},
{'0','1','1','1','1','1'},
{'0','0','1','1','1','1'},
{'0','0','0','*','1','1'},
{'0','0','0','0','0','1'},
{'0','0','0','0','0','0'}
};
int dx[9]={0,-2,-2,-1,-1,1,1,2,2};
int dy[9]={0,-1,1,-2,2,-2,2,-1,1},ans;
inline int goal(){
int val=0;
for(int i=1;i<=5;++i){
for(int j=1;j<=5;++j){
if(a[i][j]!=mp[i][j]){
++val;
}
}
}
return val;
}
void dfs(int x,int y,int dep,int last){
int val=goal();
if(dep+val>16||dep>=ans){
return;
}
if(val==0){
ans=dep;
return;
}
for(int i=1;i<=8;++i){
if(x+dx[i]<1||x+dx[i]>5||y+dy[i]<1||y+dy[i]>5){
continue;
}
if(last+i!=9){
swap(a[x][y],a[x+dx[i]][y+dy[i]]);
dfs(x+dx[i],y+dy[i],dep+1,i);
swap(a[x][y],a[x+dx[i]][y+dy[i]]);
}
}
return;
}
inline void work(void){
for(int i=1;i<=5;++i){
scanf("%s",a[i]+1);
}
int sx,sy;
for(int i=1;i<=5;++i){
for(int j=1;j<=5;++j){
if(a[i][j]=='*'){
sx=i;
sy=j;
}
}
}
ans=INT_MAX;
dfs(sx,sy,0,0);
printf("%d\n",ans==INT_MAX?-1:ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
work();
}
return 0;
}