广搜(bfs)

定义

广度优先算法,简称BFS.是一种图形搜索演算法,简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点,如果发现目标,终止.

与dfs的相似之处与不同

结合深搜理解

相同点:都是将所有的情况遍历

不同之处:dfs是一条路走到死,但是bfs则是放眼所有能到达的地方

bfs的特点也决定了bfs的使用范围

往往bfs比dfs更加高效

比如

我们从左上角遍历到右上角,最少需要多少步（上下左右）?

比较dfs bfs

dfs:所有的路径都要尝试一遍,效率极其低

bfs:我们将所有能到达的地方都存入队列,发现只要4就可以找出答案,相对于dfs效率大大提升

所以

如果将路径列为树的话,那么答案相对深度较小,就适合使用bfs

例题

电路维修

思路:

最短路

明显的最短路

很显然,对于

/

我们从左上到右下耗费的代价是1

否则为0

\

我们从右上到左下耗费的代价是1

否则为0

我们是一定不会利用一个导线1次以上的

那么我们只要建,左上到右下,右上到左下的边,利用最短路就行了

bfs

bfs也差不多

我们以代价为树的深度

我们将对应的代价能到达的区域存入队列,当然,如果之前走过就没有必要再走一遍了

如果搜到了终点就是最优解

#include<bits/stdc++.h>

using namespace std;

struct Jack{

	int next,last,ans,x,y,c;

}f[5000000];

bool vis[5000000];

int n,m,tot=0,ed;

inline void put(int x,int y,int c){

	f[++tot].x=x;

	f[tot].y=y;

	f[tot].c=c;

	f[tot].next=f[x].last;

	f[x].last=tot;

}

inline void search( ){

	int i,j,x,y,c;

	for(i=1;i<=ed;i++)f[i].ans=0xffffff;

	deque<int>q;

	q.push_front(1);

	vis[1]=0;

	f[1].ans=0;

	while(!q.empty( )){

		x=q.front( );q.pop_front( );

		for(i=f[x].last;i>=1;i=f[i].next){

			y=f[i].y;c=f[i].c;

			if(f[x].ans+c<f[y].ans){

				f[y].ans=f[x].ans+c;

				if(!vis[y]){

					vis[y]=1;

					if(c==1)q.push_back(y);

					else q.push_front(y);

				}

			}

		}

		vis[x]=0;

	}

}

int main( ){

	std::ios::sync_with_stdio(false);

	cin>>n>>m;

	char s[510];

	int i,j,x1,x2,x3,x4;

	ed=(n+1)*(m+1);

	for(i=1;i<=n;i++){

		cin>>s+1;

		for(j=1;j<=m;j++){

			x1=(m+1)*(i-1)+j;x2=(m+1)*i+j+1;x3=x1+1;x4=x2-1;

			if(s[j]=='\\'){

				put(x1,x2,0);

				put(x2,x1,0);

				put(x3,x4,1);

				put(x4,x3,1);

			}else{

				put(x1,x2,1);

				put(x2,x1,1);

				put(x3,x4,0);

				put(x4,x3,0);

			}

		}

	}

	search( );

	if(f[ed].ans==0xffffff)cout<<"NO SOLUTION"<<endl;

	else cout<<f[ed].ans<<endl;

}

魔板

思路:

我们以次数为树的深度,建立一颗树,进行bfs遍历即可

#include<bits/stdc++.h>

using namespace std;

string want;

map<string,string>m;

queue<string>q;

inline void A(string a){

	string s=a;

	int i;

	for(i=0;i<4;i++)swap(s[i],s[7-i]);

	if(!m.count(s)){

		m[s]=m[a]+'A';

		q.push(s);

	}

}

inline void B(string a){

	string s=a;

	s[0]=a[3],s[1]=a[0],s[2]=a[1],s[3]=a[2],s[4]=a[5],s[5]=a[6],s[6]=a[7],s[7]=a[4];

	if(!m.count(s)){

		m[s]=m[a]+'B';

		q.push(s);

	}

}

inline void C(string a){

	string s=a;

	s[1]=a[6];s[2]=a[1];s[5]=a[2];s[6]=a[5];

	if(!m.count(s)){

		m[s]=m[a]+'C';

		q.push(s);

	}

}

inline void bfs(){

	q.push("12345678");

	m["12345678"]="";

	while(!q.empty( )){

		A(q.front( ));

		B(q.front( ));

		C(q.front( ));

		if(m.count(want)!=0){

			cout<<m[want].size( )<<endl<<m[want];

			return;

		}

		q.pop( );

	}

}

int main( ){

	char a1;

	for(int i=0;i<8;i++)cin>>a1,want+=a1,getchar();

	bfs( );

}

走马

思路:

和平时的走马差不多

但是数据庞大,怎么办呢?

这时就引入双端队列,从终点和起点同时进行bfs遍历,如果重复到达一个点,就返回值

#include <bits/stdc++.h>

using namespace std;

struct node{

	int x,y,s;

};

queue<node>q;

int T,n,sx,sy,ex,ey;

int b[111][111];

int dx[8] = {1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};

int main( ){

	cin>>T;

	while(T--){

		while(!q.empty( ))q.pop( );

		q.pop( );

		cin>>n>>sx>>sy>>ex>>ey;

		memset(b,0,sizeof(b));

		node a;

		a.x=sx,a.y=sy,a.s=0;

		q.push(a);

		b[sx][sy]=1;

		do{

			int f=0;

			a=q.front( );

			if(a.x==ex&&a.y==ey){

				cout<<a.s<<endl;

				f = 1;

			}

			if(f) break;

			for(int v = 0; v < 8; v++){

				int nx = a.x + dx[v] , ny = a.y + dy[v];

				if(!b[nx][ny] && nx < n && nx >= 0 && ny < n && ny >= 0){

					node c;

					c.x = nx , c.y = ny , c.s = a.s + 1;

					q.push(c);

					b[nx][ny] = 1;

				}

			}

			q.pop();

		}while(!q.empty());

	}

}

总结

bfs常规思路:

我们通常是通过答案建树,然后bfs遍历这棵树,找到目标就输出,根据bfs的性质,此时一定是最优的

双端队列剪枝:

双端队列,很显然,深度越深状态越多,状态越多时间复杂度越大,双端队列也是靠这个实现的

如果我们同时知道目标和起点,那我们可以通过分别对目标,起点进行bfs遍历,找到共同点就返回答案,达到剪枝效果

巴特西

浅谈bfs

广搜(bfs)

定义

与dfs的相似之处与不同

如果将路径列为树的话,那么答案相对深度较小,就适合使用bfs

例题

最短路

bfs

总结

最新文章

热门文章