浅谈迷宫搜索类的双向bfs问题(例题解析)

举报
bigsai 发表于 2021/02/02 22:32:31 2021/02/02
【摘要】 文章目录 前言bfs类问题双向bfs例题实战 前言 文章若有疏忽还请指正,更多精彩还请关注公众号:bigsai 在搜索问题中,以迷宫问题最具有代表性,无论是八皇后的回溯问题,还是dfs找出口,bfs找最短次数等等题目的问题。在我们刚开始ac的时候、可能有着很多满足感!感觉是个迷宫问题咱么都可以给他这么搜出来 !! 然而,当数据达到一定...

前言

文章若有疏忽还请指正,更多精彩还请关注公众号:bigsai
在这里插入图片描述

在搜索问题中,以迷宫问题最具有代表性,无论是八皇后的回溯问题,还是dfs找出口,bfs找最短次数等等题目的问题。在我们刚开始ac的时候、可能有着很多满足感!感觉是个迷宫问题咱么都可以给他这么搜出来 !!
各种TLE(超时),不分析原因还会一直提交一直TLE
然而,当数据达到一定程度,我们使用简单的方法肯定会爆炸的,****。就可能需要一些特殊的巧妙方法处理,比如各种剪枝优先队列A*dfs套bfs,又或者利用一些非常厉害的数学方法比如康托展开(逆展开)等等。而今天,我们谈谈双向bfs
在这里插入图片描述

bfs类问题

bfs又称广度优先搜索

  • 估计大部分人第一次接触bfs的时候是在学习数据结构的二叉树的层序遍历!借助一个队列一层一层遍历。
  • 第二次估计就是在学习图论的时候,给你一个图,让你写出一个bfs遍历的顺序。

此后再无bfs…

而很多笔试面试还是其他机试其实对bfs的要求远远不止那么低的,需要能够处理一些小问题、写出对应代码。而事bfs可以处理很多问题,很多dfs搜索能够解决的问题bfs也能解决很多(相反也成立),并且很多跟状态有些关系的用bfs更好控制,因为bfs借助的是一个队列实现,队列中储存节点就可以保存一些节点的状态。

不过bfs并不是万能的,具体问题要看迷宫的大小的,迷宫长宽没增加一个数,那么这个数量级增加是非常大的,因为搜索次数大概和边长的指数级别有关系。当然这里不详细介绍bfs了,大家可以看以前的一篇文章。数据结构与算法—图论之dfs、bfs(深度优先搜索、宽度优先搜索)

双向bfs

什么样的情况可以使用双向bfs来优化呢?其实双向bfs的主要思想是问题的拆分吧,比如在一个迷宫中可以往下往右行走,问你有多少种方式从左上到右下。

  • 正常情况下,我们就是搜索遍历,如果迷宫边长为n,那么这个复杂度大概是2n级别.
  • 但是实际上我们可以将迷宫拆分一下,比如根据对角线(比较多),将迷宫一分为二。其实你的结果肯定必然经过对角线的这些点对吧!我们只要分别计算出各个对角线各个点的次数然后相加就可以了!
  • 怎么算? 就是从(0,0)到中间这个点mid的总次数为n1,然后这个mid到(n,n)点的总次数为n2,然后根据排列组合总次数就是n1*n2(n1和n2正常差不多大)这样就可以通过乘法减少加法的运算次数啦!
  • 简单的说,从数据次数来看如果直接搜索全图经过下图的那个点的次数为n1*n2次,如果分成两个部分相乘那就是n1+n2次。两者差距如果n1,n2=1000左右,那么这么一次差距是平方(根号)级别的。从搜索图形来看其实这么一次搜索是本来一个n*n大小的搜索转变成n次(每次大概是(n/2)*(n/2)大小的迷宫搜索两次)。也就是如果18*18的迷宫如果使用直接搜索,那么大概2^18次方量级,而如果采用双向bfs,那么就是2^9这个量级。

在这里插入图片描述

例题实战

题目链接:http://oj.hzjingma.com/contest/problem?id=20&pid=8#problem-anchor

在这里插入图片描述

在这里插入图片描述
分析:对于题目的要求还是很容易理解的,就是找到所有的路径种类,再判断其中是对称路径的有几个输出即可!

对于一个普通思考是这样的,首先是进行dfs,然后动态维护一个字符串,每次跑到最后判断这个路径字符串是否满足对称要求,如果满足那么就添加到容器中进行判断。可惜很遗憾这样是超时的,仅能通过40%的样例。

接着用普通bfs进行尝试,维护一个node节点,每次走的时候路径储存起来其实这个效率跟dfs差不多依然超时。只能通过40%数据。

接下来就开始双向bfs进行分析

  • 既然只能右下,那么对角线的那个位置的肯定是中间的那个字符串的!它的存在不影响是否对称的(n*n的迷宫路径长度为n-1 + n为奇数).
  • 我们判断路径是否对称,只需要判断从(1,1)到对角节点k(设为k节点)的路径有没有和(n,n)到k相同的。如果有路径相同的那么就说明这一对构成对称路径
  • 在具体实现上,我们对每个对角线节点可以进行两次bfs(一次左上到(1,1),一次右下到(n,n)).并且将路径放到两个hashset(set1,set2)中,跑完之后用遍历其中一个hashset中的路径,看看另一个set是否存在该路径,如果存在就说明这个是对称路径放到 总的hashset(set) 中。对角线每个位置都这样判断完最后只需要输出总的hashset(set)的集合大小即可!

ac代码如下:

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class test2 {	
	static class node{ int x; int y;
		String path="";
		public node() {}
		public node(int x,int y,String team)
		{ this.x=x; this.y=y; this.path=team;
		}
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		Set<String>set=new HashSet<String>();//储存最终结果
		int n=Integer.parseInt(sc.nextLine());
		char map[][]=new char[n][n];
		for(int i=0;i<n;i++)
		{ String string=sc.nextLine(); map[i]=string.toCharArray();
		}
		Queue<node>q1=new ArrayDeque<node>();//左上的队列
		Queue<node>q2=new ArrayDeque<node>();//右下的队列
		for(int i=0;i<n;i++)
		{ q1.clear();q2.clear(); Set<String>set1=new HashSet<String>();//储存zuoshang Set<String>set2=new HashSet<String>();//储右下 q1.add(new node(i,n-1-i,""+map[i][n-1-i])); q2.add(new node(i,n-1-i,""+map[i][n-1-i])); while(!q1.isEmpty()&&!q2.isEmpty()) { node team=q1.poll(); node team2=q2.poll(); if(team.x==n-1&&team.y==n-1)//到终点,将路径储存 { //System.out.println(team2.path);	 set1.add(team.path); set2.add(team2.path); } else { if(team.x<n-1)//可以向下 { q1.add(new node(team.x+1, team.y, team.path+map[team.x+1][team.y])); } if(team.y<n-1)//可以向右 { q1.add(new node(team.x, team.y+1, team.path+map[team.x][team.y+1])); } if(team2.x>0)//上 { q2.add(new node(team2.x-1, team2.y, team2.path+map[team2.x-1][team2.y])); } if(team2.y>0)//左 { q2.add(new node(team2.x, team2.y-1, team2.path+map[team2.x][team2.y-1])); } } } for(String va:set1) { if(set2.contains(va)) { set.add(va); } } }
		System.out.println(set.size()); }
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81

在这里插入图片描述
在这里插入图片描述

文章来源: bigsai.blog.csdn.net,作者:Big sai,版权归原作者所有,如需转载,请联系作者。

原文链接:bigsai.blog.csdn.net/article/details/104295835

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。