搜索一

dolires / 2023-08-03 / 原文

复健\(Day 6\)

搜索一

一.基础的\(DFS\)和\(BFS\)

宽搜我不是很常写，这里给出模板

void BFS()
{
	queue<int> q;
	int vis[maxn];
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		各种操作
		for(int y:e[x])
		{
			if(vis[y]) continue;
			vis[y]=1;
			q.push(y);
		}
	}
}

\(1.\)\([SHOI2002]\)滑雪

https://www.luogu.com.cn/problem/P1434

我首先想到的方法其实是\(dp\)，很显然可以得到一个状态方程\(dp[i][j]=max(dp[i][j],dp[i+1][j]+1,dp[i-1][j]+1,dp[i][j+1]+1,dp[i][j-1]+1)\)（更新的都是满足高度条件的）

但是你在做状态方程转移的时候会发现一个问题，就是若出现\(1\) \(2\) \(3\) \(4\) \(5\)的这样的情况，我们从左到右，从上到小更新的话，\(dp[1][1]\)最后还是\(1\)，而不是我们的\(5\)，说明我们的状态方程存在后效性，即某点的更新顺序会影响到后面的状态值，我们要怎样消除这一后效性呢？采用一个优先队列\(priority_queue\)，我们先更新高度值更大的那些点，这样就不会再出现上面的情况了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 110
using namespace std;

int dp[maxn][maxn];
int H[maxn][maxn];
int dirx[4]={0,1,-1,0};
int diry[4]={1,0,0,-1};

struct Node
{
	int x,y,h;
	bool operator < (const Node &rhs) const
	{
		return h>rhs.h;
	}
}node[maxn*maxn];

int main()
{
	int n,m;
	cin>>n>>m;
	int M=0;
	int tot=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			node[++tot].x=i,node[tot].y=j;
			cin>>node[tot].h;
			dp[i][j]=1;
			H[i][j]=node[tot].h;
		}
	}
	sort(node+1,node+tot+1);
	for(int i=1;i<=tot;i++)
	{
		int x=node[i].x,y=node[i].y,h=node[i].h;
		for(int k=0;k<4;k++)
		{
			int fx=x+dirx[k],fy=y+diry[k];
			if(fx>n||fy>m||fx<=0||fy<=0) continue;
			if(h>H[fx][fy]) dp[fx][fy]=max(dp[fx][fy],dp[x][y]+1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) M=max(M,dp[i][j]);
	}
	printf("%d\n",M);
	return 0;
}

二.迭代加深\((ID)\)

有时候某个问题状态没办法存（\(BFS\)不可行)，深度又不知道有多深(\(DFS\)不可行)，我们就采用迭代加深的办法

首先它是逐层搜索（我们可以设置一个深度，搜索到这个深度就不继续了，有时候状态数随层数的深入呈指数爆炸趋势，上下两层之间状态数差距非常大），避免了更深层的深入

其次它的遍历方式仍然是\(DFS\)，这样方便回溯，不必存储状态

基本框架如下

int dit=0;//1.规定搜索深度

bool dfs(int x)//如果搜索深度超过规定就停止
{
	if(x>idt) return false;
	if(check()) return true;
	...
	return false;
}

for(;;)//每次搜索失败之后就让搜索深度加深一层
{
	++idt;
	if(dfs(0)) break;
}
cout<<idt<<endl;//第一次找到答案时其深度即为最优值

\(1.\)埃及分数

https://www.luogu.com.cn/problem/P1763

对于这道题，深搜层数的意义就是分数的个数，枚举分数的个数之后就是简单的搜索了

然后要进行一些可行性剪枝

由于用浮点数计算会导致误差，所以我们直接模拟分数的计算

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 1010
using namespace std;

int a,b;
int idt;

int ans[maxn];

int gcd(int x,int y)
{
	if(!y) return x;
	return gcd(y,x%y);
}

bool dfs(int ansx,int ansy,int last,int x)//还需要答案的分子ansx,分母ansy，上一个分母last,已枚举深度x
{
	int c=gcd(ansx,ansy);
	ansx/=c,ansy/=c;
	if(last) ans[x]=last;
	if(x>idt)
	{
		if(ansx==0) return true;
		return false;
	}
	for(int i=(idt-x+1)*ansy/ansx;i>=max(ansy/ansx,last);i--)
	{
		if(i>0&&i>last)
		{
			if((ansx*i-ansy)*(ansy*i)>=0)
			{
				int c=gcd(ansx*i-ansy,ansy*i);
				int m=(ansx*i-ansy)/c,n=(ansy*i)/c;
				if(dfs(abs(m),abs(n),i,x+1)) return true;
			}
		}
	}
	return false;
}

int main()
{
	cin>>a>>b;
	idt=1;
	int c=gcd(a,b);
	a=a/c;b=b/c;
	for(;;)
	{
		if(dfs(a,b,0,1)) break;
		idt++;
	}
	for(int i=2;i<=idt+1;i++) printf("%d ",ans[i]);
	return 0;
}

基础的迭代搜索部分很简单，就是按照模板来就可以了，然后我们在纸上写出分数进行减法之后的分子和分母，来进行答案的对照

关于剪枝方面，我们若还需要凑出\(\frac{a}{b}\)的分数，我们考虑极端的情况，只剩下一个数可以枚举，分母就是\(\frac{b}{a}\)，若我们剩下的\(x\)个数都相同给（即都是最小的那个），那么我们的分母是\(\frac{x\times b}{a}\)，比较二者的大小，这个是上界，\(\frac{b}{a}\)是下界，然后为了不会因为少考虑情况而导致答案错误，我们上界设为\(\left \lfloor \frac{x\times b}{a}\right \rfloor+1\)，下界设为\(max(\left \lfloor \frac{b}{a} \right \rfloor,last)\)（\(last\)是上一个枚举的分母）即可

但是我做了以上的步骤之后交上去只有百分之三十的分数，答案报错告诉我我的答案比正解的优先级更低，这个时候我注意到不能简单地在每一层\(dfs\)中从大到小枚举要找的分母来得到题目要求的最大的分母最小这一条件优先级，我们必须把所有的答案都搜出来才能进行最后答案的比较，从而得出优先级最高的答案

正解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 1010
#define int long long
using namespace std;

int a,b;
int idt;

int ans[maxn];
int anstot;
int f_ans[maxn];

int gcd(int x,int y)
{
	if(!y) return x;
	return gcd(y,x%y);
}

void dfs(int ansx,int ansy,int last,int x)//还需要答案的分子ansx,分母ansy，上一个分母last,已枚举深度x
{
	int c=gcd(ansx,ansy);
	ansx/=c,ansy/=c;
	if(last) ans[x]=last;
	if(x>idt)
	{
		if(ansx==0)
		{
			anstot=idt;
			if(ans[x]<f_ans[x-1])
			{
				for(int i=1;i<=idt;i++) f_ans[i]=ans[i+1];
			}
		}
		return;
	}
	for(int i=max(ansy/ansx,last);i<=(idt-x+1)*ansy/ansx+1;i++)
	{
		if(i>0&&i>last)
		{
			if((ansx*i-ansy)*(ansy*i)>=0)
			{
				int c=gcd(ansx*i-ansy,ansy*i);
				int m=(ansx*i-ansy)/c,n=(ansy*i)/c;
				dfs(abs(m),abs(n),i,x+1);
			}
		}
	}
	return;
}

signed main()
{
	cin>>a>>b;
	idt=1;
	int c=gcd(a,b);
	a=a/c;b=b/c;
	memset(f_ans,0x3f,sizeof(f_ans));
	for(;;)
	{
		dfs(a,b,0,1);
		if(anstot) break;
		idt++;
	}
	for(int i=1;i<=idt;i++) printf("%d ",f_ans[i]);
	return 0;
}

一开始一直有一个点过不了，看了题解才发现是因为答案需要开\(long\) \(long\)，我们做题的时候应该计算一下这一点的，因为这个点我被卡了很久，以后做题的时候一定要注意

\(2.\)岳麓山上打水

https://citel.bjtu.edu.cn/acm/problem/1447

\(3.POWER\) \(CALCULUS\)

https://vjudge.net/problem/UVA-1374

可能在做的时候我们会想到二分答案，但是注意到因为当搜索层数比较大时，增加一层都会使子状态指数级增长，故我们不要用二分去做，反而会增加时间复杂度

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 2010
using namespace std;

int used[maxn];
int n;

bool dfs(int x,int num,int idt)
{
	used[x]=num;
	if(x>idt)
	{
		if(num==n) return true;
		return false;
	}
	if(num*(1<<(idt-x+1))==n) return true;
	if(num*(1<<(idt-x+1))<n) return false;
	for(int i=1;i<=x;i++)
	{
		if(dfs(x+1,abs(num-used[i]),idt)) return true;//注意用abs
		if(dfs(x+1,num+used[i],idt)) return true;
	}
	return false;
}

int main()
{
	while(cin>>n&&n)
	{
		int idt=0;
		for(;;)
		{
			if(dfs(1,1,idt)) break;
			idt++;
		}
		printf("%d\n",idt);
	}
	return 0;
}

三.剪枝

一般来说，剪枝可以分为两种：

可行性剪枝：某个状态一定达到不了目标状态；最优性剪枝：某个状态所有到达目标状态的方案一定不是最优值

一个考虑剪枝的思路：考虑极端情况下能不能满足题目要求

\(1.\)生日蛋糕

https://www.luogu.com.cn/problem/P1731

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 20010
using namespace std;

int n,m;

int ans;

inline void dfs(int r1,int h1,int layer,int lv,int s)
{
	if(lv<0) return;
	if(layer>m)
	{
		if(lv==0)
		{
			if(s<ans) ans=s;
			return;
		}
		else return;
	}
	int c=m-layer+1;
	if(layer!=1&&r1*r1*h1*(m-layer+1)<=lv) return;
	if(m-layer+1>lv) return;
	if((long long)c*c*(c+1)*(c+1)/4>lv) return;
	if(s+c*(c+1)*(2*c+1)/6>ans) return;
	if(layer!=1&&s+2*lv/r1>=ans) return;
	if(layer==1)
	{
		for(int i=m;i*i*m<=n;i++)
		{
			for(int j=m;j*m<=n;j++)
			{
				dfs(i,j,layer+1,lv-i*i*j,s+2*i*j+i*i);
			}
		}
	}
	else
	{
		for(int i=m-layer+1;i<r1;i++)
		{
			for(int j=m-layer+1;j<h1;j++)
			{
				dfs(i,j,layer+1,lv-i*i*j,s+2*i*j);
			}
		}
	}
	return;
}

inline int read()
{
	int ans=0,f=1;char i=getchar();
	while(i<'0'||i>'9'){if(i=='-') f=-1;i=getchar();}
	while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();}
	return ans*f;
}

int main()
{
	n=read();m=read();
	ans=0x3f3f3f3f;
	dfs(0,0,1,n,0);
	if(ans==0x3f3f3f3f) printf("0\n");
	else printf("%d\n",ans);
	return 0;
}

其中剪枝条件\(2\times lv/r1 \geqslant ans\)是不易被找到的一个剪枝条件，若没有这个条件，会\(T\)掉三个点

\(2.\)小木棍

https://www.luogu.com.cn/problem/P1120

四.状态压缩

状态压缩就是能让一些状态数不多的问题能够更方便地储存状态，其中用得最多的就是二进制运算压缩状态

\(1.\)种花小游戏

有一个经常用到的小技巧，一个二元组\((c,m)\)我们用一个数\(c*n+m\)来表示它，除\(n\)得到\(c\)，模\(n\)得到\(m\)

\(2.\)光棍组织

用位运算快速枚举子集操作

for(int i=s;i;i=(i-1)&s)

五.双向\(BFS\)

就是再起点和终点都很清楚的情况下，把起点和终点同时入队，或者进两个队，共同进行\(BFS\)，当两者相遇时为最优解

通常情况下，搜索树越往下分叉越大，子节点呈指数级暴增，所以让两头共同搜索不仅是让时间减半，搜索树高度减半的结果可能时显著的

\(1.\)交换

\(2.\)八数码问题

https://www.luogu.com.cn/problem/P1379

\(3.\)骑士精神

https://www.luogu.com.cn/problem/P2324

六.\(A*\)算法

\(dfs\)、\(bfs\)和迭代加深都是盲目的搜索，剪枝排序随机化，而我们的\(A*\)算法则是一种启发式搜索

启发式搜索利用已有知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的

启发式搜索的核心是启发函数和评价函数：\(f(n)=g(n)+h(n)\)，这里的\(n\)是一个状态，\(f\)就是评价函数，\(g(n)\)表示从起点到该状态的花销，\(h(n)\)则是一个启发函数，表示从\(n\)到终点的花销的一个估计值（当\(h(n)=0\)时，这就是一个简单的\(bfs\)）

\(g*(n)\)表示从起点到该状态的花销的最小代价的实际值（与\(g(n)\)其实是完全相同的，但是我们为了定义的对称性，雇佣两个函数分别表示它们）

\(h*(n)\)表示从该状态到终点的花销的最小代价的实际值

\(f*(n)=g*(n)+f*(n)\)表示从起点到终点的最小代价

实际上\(f(n),g(n),h(n)\)分别是\(f*(n),g*(n),h*(n)\)的估计值

当我们的\(h(n)\leqslant h*(n)\)时，我们必定能保证能得到最优解，而且当我们构造的\(h(n)\)越接近实际值\(h*(n)\)时，算法就会跑得越快