目录:

1 DFS 深度优先搜索
2 剪枝
3 BFS 广度优先搜索
4 记忆化搜索( Hash 散列算法 /状压DP)
5 IDDFS 迭代加深
6 A* 启发式搜索
7 IDA* 迭代加深与启发式搜索
8 双向广度优先搜索
9 折半暴搜

引入:

搜索是NOIP常考知识点。
在掌握搜索时,心中要有一棵搜索树的概念。这是重中之重。
搜索:简而言之,就是把问题状态空间进行搜索的算法,从中找出可行解或最优解。对问题状态空间进行遍历所形成的图,就是搜索树。
接下来,根据搜索树,来进行对搜索进行系统的整理回顾。

1 DFS 深度优先搜索

在搜索树上,按照深度优先的顺序对问题状态空间进行搜索的算法。
以一个简单的例子:
任务:遍历一棵树,找到值最大的节点
在树上递归的向下走,走到叶子之后回溯选择另一条道路。
因为相对于同层的节点,深层的节点的优先级更高,所以称为深度优先搜索。
对于一般的题目,可以把每一个状态抽象成为一个节点,我们做的事情还是类似的。

1.1 例题

小猫爬山

翰翰和达达饲养了N只小猫,这天,小猫们要去爬山。
经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为W,而N只小猫的重量分别是C1、C2……CNC1、C2……CN。当然,每辆缆车上的小猫的重量之和不能超过W。
每租用一辆缆车,翰翰和达达就要付1美元,所以他们想知道,最少需要付多少美元才能把这N只小猫都运送下山?

输入格式

第1行:包含两个用空格隔开的整数,N和W。
第2..N+1行:每行一个整数,其中第i+1行的整数表示第i只小猫的重量CiCi。

输出格式

输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。

数据范围

1≤N≤18
1≤Ci≤W≤10^8

输入样例:

5 1996
1
2
1994
12
29

输出样例:

2

用DFS,在遍历搜索树的过程中,我们可以尝试依次把每一只小猫分配到一辆已租用的揽车上,或者新租一辆缆车安置这只小猫。于是,我们实时关心的状态有:已经运送的小猫已经有多少只,已经租用的缆车有多少辆,每辆缆车上当前搭载的小猫重量之和。
编写函数dfs(cat,car)处理第cat只小猫的分配过程(前cat-1只已经装载),并且目前已经租用car辆缆车。对于已经租用的这car辆缆车的当前搭载量,我们使用一个全局数组v[]来记录。
cat,car,c数组共同标识着问题状态空间所类比的“图”中的一个“节点”。在这个“节点”上,我们至多有car+1个可能的分支:
1.尝试把第cat只小猫分配到已经租用的第i(1<=i<=car)辆缆车上。如果第i辆缆车还装的下,我们就在v[i]中累加c[cat],然后递归dfs(cat+1,car);
2.尝试新租一辆缆车来安置这只小猫,也就是令v[car+1]=c[cat],然后递归dfs(cat+1,car+1);
当now=n+1时,说明搜索到了递归边界,此时就可以用cnt更新答案。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define reg register
using namespace std;
const ll maxn=20;
ll n,w,ans=10e8,t_ans;
ll c[maxn],v[maxn];
void dfs(ll cat,ll car)
{
	if(cat>n)
	{
		ans=min(t_ans,ans);
		return;
	}
	for(reg ll i=1;i<=car;++i)
	if(v[i]+c[cat]<=w)
	{
		v[i]+=c[cat];
		dfs(cat+1,car);
		v[i]-=c[cat];
	}
	v[car+1]+=c[cat];t_ans++;
	if(t_ans>ans)
	{
		t_ans--;
		return;
	}
	dfs(cat+1,car+1);
	t_ans--;v[car+1]-=c[cat];
}
bool cmp(ll a,ll b) {return a>b;}
int main()
{
	scanf("%lld%lld",&n,&w);
	for(reg ll i=1;i<=n;++i) scanf("%lld",&c[i]);
	sort(c+1,c+n+1,cmp);
	dfs(1,0);
	printf("%lld",ans);
	return 0;
}

2 剪枝

剪枝,就是减小搜索树的规模、今早排除搜索树中不必要的分支的一种手段。

2.1 几种方法

1.优化搜索顺序。sort
2.排除等效冗余。不重复搜索搜索树中某个节点(具有相同意义的节点)。
3.可行性剪枝。
4.最优性剪枝。

2.2 例题

小木棍

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过5050。
现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

输入格式

共二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数,其中N≤65
第二行为N个用空个隔开的正整数,表示N根小木棍的长度。

输出格式

一个数,表示要求的原始木棍的最小可能长度

输入输出样例

输入 #1

9
5 2 1 5 2 1 5 2 1

输出 #1

6

剪枝:
1.优化搜索顺序
把木棍长度从大到小排序,优先尝试较长的木棍。
2.排除等效冗余
(1)可以限制先后加入一根原始的木棍长度是递减的。这是因为拼上一根长度为x的木棍,再拼上一根长度为y的木棍(x<y),与先拼上y再拼上x显然是等效的,只要搜索其中一种。
(2)对于当前原始木棍,记录最近一次尝试拼接的木棍长度。如果分支搜索失败回溯,不再尝试向该木棍中拼接其他相同的木棍(必定也会失败)。
(3)如果在当前原始木棍中“尝试拼入的第一跟木棍”的递归分支就返回失败,那么直接判断当前分支失败,立即回溯。这是因为在拼入这跟木棍前,面对的原始木棍都是“空”的(还没有进行拼接),这些木棍是等效的。木棍拼在当前的木棍中失败,拼在其他木棍中一样会失败。
(4)如果在当前原始木棍中拼入一根木棍后,木棍恰好被拼接完整,并且“接下来拼接剩余原始木棍”的递归分支返回失败,那么直接判定当前分支失败,立即回溯。该剪枝可以用贪心来解释,“在用1根木棍恰好拼完当前原始木棍”必然比“在用若干根木棍拼完当前原始木棍”更好。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define reg register
using namespace std;
int a[70],v[70];
int n,sum,val,cnt,len,m;
bool cmp(int a,int b) {return a>b;}
bool dfs(int stick,int cab,int last)
{
	if(stick>cnt) return true;
	if(cab==len) return dfs(stick+1,0,1);
	int fail=0;
	for(reg int i=last;i<=m;++i)
	if(!v[i]&&a[i]+cab<=len&&fail!=a[i])
	{
		v[i]=1;
		if(dfs(stick,cab+a[i],i+1)) return true;
		v[i]=0;fail=a[i];
		if(cab==0||cab+a[i]==len) return false;
	}
	return false;
}
int main()
{
	scanf("%d",&n);int temp;
	for(reg int i=1;i<=n;++i)
	{
		scanf("%d",&temp);
		if(temp>50) continue;
		a[++m]=temp;
		sum+=a[m];val=max(val,temp);
	}
	sort(a+1,a+m+1,cmp);
	for(len=val;len<=sum;++len)
	{
		if(sum%len) continue;
		cnt=sum/len;
		if(dfs(1,0,1))
		{
			printf("%d",len);
			break;
		}
	}
	return 0;
}

3 BFS 广度优先搜索

对于搜索树,按照广度优先的顺序对问题状态空间进行搜索的算法。

3.1 例题

马的遍历

题目描述

有一个n*m的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入格式

一行四个数据,棋盘的大小和马的坐标

输出格式

一个n*m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)

输入输出样例

输入

3 3 1 1

输出

0    3    2    
3    -1   1    
2    1    4  

经典广搜例题
核心思想:从初始状态开始,应用某种函数进行状态转移,将转移后的状态入队,作为新的状态,一直进行这样的转移,直到没有状态可更新。
对此题讲,将起点作为初始状态入队,用移动函数进行状态转移,将扩展出来的状态入队,直到队列为空。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define reg register int
using namespace std;
int n,m,sx,sy;
int ans[410][410];
int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={-1,-2,-2,-1,1,2,2,1};
struct node{
	int x,y,tot;
};
queue<node> q;
inline void bfs(int sx,int sy)
{
	node s;s.x=sx;s.y=sy;s.tot=0;q.push(s);
	ans[sx][sy]=0;
	while(!q.empty())
	{
		node u=q.front();q.pop();
		int x=u.x,y=u.y,tot=u.tot;
		for(reg i=0;i<=7;++i)
		{
			int x1=x+dx[i],y1=y+dy[i];
			if(x1<1||y1<1||x1>n||y1>m) continue;
			if(ans[x1][y1]==-1)
			{
				ans[x1][y1]=tot+1;
				u.x=x1;u.y=y1;u.tot=tot+1;
				q.push(u);
			}
		}
	}
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&sx,&sy);
	memset(ans,-1,sizeof(ans));
	bfs(sx,sy);
	for(reg i=1;i<=n;++i)
	{
		for(reg j=1;j<=m;++j)
		printf("%-5d",ans[i][j]);printf("\n");
	}
	return 0;
}

矩阵距离

给定一个N行M列的01矩阵A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:

输出一个N行M列的整数矩阵B,其中:

输入格式

第一行两个整数n,m。
接下来一个N行M列的01矩阵,数字之间没有空格。

输出格式

一个N行M列的矩阵B,相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤1000

输入样例:

3 4
0001
0011
0110

输出样例:

3 2 1 0
2 1 0 0
1 0 0 1

先来思考这样一个问题,给定一个N*M的01矩阵和一个起点(0表示可通行点,1表示禁止点),每一步可以向上、下、左、右四个方向之一移动1个单位距离,求从起点出发能够到达哪些位置,以及到达每个位置的最小步数。这是广搜的最基本应用,

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define reg register int
using namespace std;
int n,m;
int a[1010][1010],b[1010][1010];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
char c[1010];
struct node{
	int x,y,tot;
}temp;
queue<node> q;
inline void bfs()
{
	while(!q.empty())
	{
		temp=q.front();q.pop();
		int x=temp.x,y=temp.y,tot=temp.tot;
		for(reg i=0;i<4;++i)
		{
			int x0=x+dx[i],y0=y+dy[i];
			if(b[x0][y0]==-1)
			{
				b[x0][y0]=tot+1;
				temp.tot=tot+1;temp.x=x0;temp.y=y0;
				q.push(temp);
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(reg i=1;i<=n;++i)
	{
		scanf("%s",c);
		for(reg j=0;j<m;++j)
		{
			a[i][j+1]=c[j]-'0';
			b[i][j+1]=-1;
			if(a[i][j+1]==1)
			{
				temp.tot=0;temp.x=i;temp.y=j+1;
				b[i][j+1]=0;
				q.push(temp);
			}
		}
	}
	bfs();
	for(reg i=1;i<=n;++i)
	for(reg j=1;j<=m;++j)
	{
		printf("%d ",b[i][j]);
	}printf("\n");
	return 0;
}

发表评论

电子邮件地址不会被公开。