兼职做网站平台,个人网页参考,哈尔滨网站建设排,wordpress查看访问量一、BFS搜索的原理BFS搜索的原理#xff1a;“逐层扩散”#xff0c;从起点出发#xff0c;按层次从近到远#xff0c;逐层先后搜索。编码#xff1a;用队列实现。应用#xff1a;BFS一般用于求最短路径问题#xff0c;BFS的特点是逐层搜索#xff0c;先搜到的层离起点…一、BFS搜索的原理BFS搜索的原理“逐层扩散”从起点出发按层次从近到远逐层先后搜索。编码用队列实现。应用BFS一般用于求最短路径问题BFS的特点是逐层搜索先搜到的层离起点更近。二、BFS找最短路路径应用场合:点和点直接的距离是1即边长是1。寻找从到*的最短路径。使用队列来实现。最短路径问题用BFS解决逐层扩散。往BFS的队列中加入邻居结点时按距离起点远近的顺序加入: 先加入距离起点为1的邻居结点加完之后再加入距离为2的邻居结点等等。搜完一层才会继续搜下一层。三、输出路径的两种方法简单方法每扩展到一个点v都在v上存储从起点s到v的完整路径到达终点t时便得到了从起点s到t的完整路径。优点简单、适合小图。缺点占用大量空间因为每个点上都存储子完整的路径不适合大图。标准方法在每个点上记录它的前驱点从终点一步步回溯到起点就可以得到一条完整路径。优点节省空间因为每个点上只存储了上一个点适合大图。四、蓝桥杯真题(602号)题目求字典序最小的最短路径。在每次扩散下一层往BFS的队列中加入下一层的结点时按字典序“DLRU”的顺序加下一层的结点那么第一个搜到的最短路径就是字典序最小的。计算复杂度每个点只搜一次即进入队列和出队列一次。复杂度O(n)n是迷宫内结点的总数。BFS能用于解决1千万个点的最短路问题。输出路径的两种方法简单方法标准方法路径打印:从终点递归到起点然后打印读迷宫代码BFS队列实现五、连通性判断: BFSBFS判断连通性的步骤:从图上任意一个点u开始遍历把它放进队列中。弹出队首u标记u已搜过然后搜索u的邻居点即与u连通的点放到队列中。继续弹出队首标记搜过然后搜索与它连通的邻居点放进队列。继续以上步骤直到队列为空此时一个连通块已经找到。其他没有访问到的点属于另外的连通块按以上步骤再次处理这些点。最后所有点都搜到所有连通块也都找到。六、BFS的三种实现queuelistdeque (最快)用下面的“178号真题”演示三种实现。七、蓝桥杯真题(178号)BFS连通性判断图论的一个简单问题给定一张图图由点和连接点的边组成要求找到图中互相连通的部分。什么岛屿不会被完全淹没?若岛中有个陆地 (称为高地)它周围都是陆地那么这个岛不会被完全淹没。用BFS搜出有多少个岛 (连通块)检查这个岛有没有高地统计那些没有高地的岛(连通块) 的数量就是答案。计算复杂度:每个像素点只用搜一次且必须至少搜一次共N^2个点BFS的复杂度是O(N^2)不可能更好了。1.queue2.list3.deque八、BFS判重BFS队列BFS逐步扩展下一层把扩展出的下一层状态放进队列中处理。如果这些状态有相同的只需搜一次只需要进入队列一次。必须判重。Python判重方法字典、set()。1.字典判重字典无序、可变、有索引的集合。字典:用花括号定义有键和值。2. set判重set()函数创建一个无序、不重复元素集关系测试删除重复数据计算交集、差集、并集、补集。九、双向广搜应用场景:有确定的起点s和终点t把从起点到终点的单向搜索变换为分别从起点出发和从终点出发的“相遇”问题。操作: 从起点s(正向搜索) 和终点t(逆向搜索) 同时开始搜索当两个搜索产生相同的一个子状态v时就结束v是相遇点。得到的s-v-t是一条最佳路径。队列:一般用两个队列分别处理正向BFS和逆向BFS。双向广搜的复杂度当下一层扩展的状态很多时双向广搜能大大优化减少大量搜索。由于起点和终点的串不同正向BFS和逆向BFS扩展的下一层数量也不同也就是进入2个队列的串的数量不同先处理较小的队列可以加快搜索速度。十、蓝桥杯真题(178号)分析从起始状态到终止状态求最少跳跃次数是一个最短路径问题用BFS。建模直接让炸蜢跳到空盘有点麻烦因为有很多在跳。反过来看让空盘跳跳到虾蜢的位置简单多了只有一个空盘在跳。化圆为线题目是一个圆圈不好处理用一个建模技巧“化圆为线”把圆形转换为线形。把空盘看成0有9个数字{0,1,2,3,4,5,6,7,8}一个圆圈上的9个数字拉直成了一条线上的9个数字这条线的首尾两个数字处理成相连的。八数码问题有9个数字{0,1,2,3,4,5,6,7,8}共有9!362880种排列不算多。最短路径初始状态:“012345678”,目标状态:“087654321”。从初始状态“012345678”跳一次有4种情况:“102345678”、“210345678”“812345670”、“712345608”。然后从这4种状态继续跳到下一种状态一直跳到目标状态为止。用BFS扩展每一层。每一层就是炸蜢跳了一次扩展到某一层时发现终点“087654321”这一层的深度就是蛇蟠跳跃的次数。为什么去重?如果不去重第1步到第2步有4种跳法;第2步到第3步有4*4种;...;第20步有4^20 1万亿种那可就完犊子了。判断有没有重复跳如果跳到一个曾经出现过的情况就不用往下跳了。一共只有9!362880种情况。代码复杂度在每一层能扩展出最少4种、最多362880种情况最后算出的答案是20层那么最多算20*3628807257600次。在代码中统计实际的计算次数是1451452次。队列:最多有9!362880种情况进入队列。1. 字典去重用list实现队列速度慢:3s2. set()去重用list实现队列速度快:1.4s3.双向广搜队列q1 : 正向搜索队列q2 : 逆向搜索用cnt统计运行了多少次:54568次。前面用普通BFS计算:1451452次。双向广搜的计算量只有4%。
