当前位置: 首页 > news >正文

第五十二章 BFS进阶(二)——双向广搜

第五十二章 BFS进阶(二)——双向广搜

  • 一、双向广搜
    • 1、优越之处
    • 2、实现逻辑
    • 3、复杂度分析
  • 二、例题
    • 1、问题
    • 2、分析
    • 3、代码

一、双向广搜

1、优越之处

双向广搜是指我们从终点和起点同时开始搜索,当二者到达同一个中间状态的时候,即相遇。

那么这么搜有什么好处呢?

我们知道,在很多题目中,我们使用BFS的时间复杂度是指数级别的。

也就是说,如果讲BFS的进行次数画成一个函数的话,就会画成下面这个图。

在这里插入图片描述

如果我们采取从两端出发,到中间某点相遇的做法。

那么示意图可以画成下面的样子:
在这里插入图片描述

可能原来我们需要进行A次搜索,但是双向广搜的话,我们就只需要进行B次搜索。(上图仅仅表示一个大概意思,目的仅仅为了突出双向广搜进行了很大的优化,请勿追究细节)

除了上面这种大致的表示方法外,我们还可以画成一个搜索树的形式来看。

在这里插入图片描述
红色绿色线交叉的部分组成的菱形是双向广搜过程中所需搜索的状态数量。

上面的两个图仅仅是感性的分析了一下,双向广搜的优越之处。

我们还需要量化计算一下,到底优化了多少,具体的时间复杂度是多少,在分析复杂度之前,我们需要先看一下双向广搜大体的实现逻辑。

2、实现逻辑

我们创建两个队列。

一个队列从起点开始广搜,一个队列从终点开始广搜。

而在BFS中,我们的执行次数和队列中的元素是相关的。我们队列中的元素越多,BFS需要扩展的就越多。所以我们可以通过队列中的元素个数来代表一个BFS扩展时的复杂程度。

因此,我们可以比较两个BFS的队列中的元素,谁队列中元素少,就对哪个BFS进行拓展。

3、复杂度分析

根据上面的算法实现,我们可以知道,基本上就是从终点开始的BFS和从起点开始的BFS轮流进行。

我们可以认为二者进行的次数是一样的。

假设二者一共扩展了KKK次,那么各自可以认为进行了k/2k/2k/2次。

这里的拓展是只刚才搜索树中的。假设每次扩展是多两个状态入队,那么总共的状态就是1+21+22....+2k/2−11 + 2^1 + 2^2 ....+2^{k/2-1}1+21+22....+2k/21,求和以后约等于2k/22^{k/2}2k/2,那么两个BFS加起来就是2k/2+12^{k/2+1}2k/2+1

如果单向广搜的话,按照刚才的求和公式,对kkk层的状态求和,大概是2k2^{k}2k

那么我们就发现优化了大约2k/22^{k/2}2k/2倍。

二、例题

1、问题

在这里插入图片描述

2、分析

过程很简单,就是从起点开始枚举每一个可能的变化,直到最后变成了B。

由于我们已经知道了终点过程,所以可以同时从B到A开始变化。一直到二者中间状态重合。

3、代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6;
int n;
string A, B;
string a[N], b[N];
int extend(queue<string>& q, unordered_map<string, int >&da,unordered_map<string, int>&db,string a[N], string b[N])
{int d = da[q.front()];while(q.size() && da[q.front()] == d){auto t = q.front();q.pop();for(int i = 0; i < n; i ++ ){for(int j = 0; j < t.size(); j ++ ){if(t.substr(j, a[i].size()) == a[i]){string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());if(db.count(r))return da[t] + db[r] + 1;if(da.count(r))continue;da[r] = da[t] + 1;q.push(r);}}}}return 11;
}
int bfs()
{if(A == B)return 0;queue<string>qa, qb;unordered_map<string, int> da, db;qa.push(A), qb.push(B);da[A] = db[B] = 0;int step = 0;while(qa.size() && qb.size()){int t;if(qa.size() < qb.size()){t = extend(qa, da, db, a, b);}else{t = extend(qb, db, da, b, a);}if(t <= 10)return t;if(++step == 10)return -1;}return -1;
}void solve()
{cin >> A >> B;while(cin >> a[n] >> b[n])n ++;int t = bfs();if(t == -1)cout << "NO ANSWER!\n";else cout << t << "\n";
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}

相关文章:

第五十二章 BFS进阶(二)——双向广搜

第五十二章 BFS进阶&#xff08;二&#xff09;——双向广搜一、双向广搜1、优越之处2、实现逻辑3、复杂度分析二、例题1、问题2、分析3、代码一、双向广搜 1、优越之处 双向广搜是指我们从终点和起点同时开始搜索&#xff0c;当二者到达同一个中间状态的时候&#xff0c;即相…...

业务建模题

一. 单选题&#xff1a;1.在活动图中负责在一个活动节点执行完毕后切换到另一个节点的元素是( A)。A.控制流 B.对象流 C.判断节点 D.扩展区城2.以下说法错误的是(C)。A.活动图中的开始标记一般只有一一个,而终止标记可能有多个B.判断节点的出口条件必须保证不互相重复,并且不缺…...

电子秤专用模拟数字(AD)转换器芯片HX711介绍

HX711简介HX711是一款专为高精度电子秤而设计的24 位A/D 转换器芯片。与同类型其它芯片相比&#xff0c;该芯片集成了包括稳压电源、片内时钟振荡器等其它同类型芯片所需要的外围电路&#xff0c;具有集成度高、响应速度快、抗干扰性强等优点。降低了电子秤的整机成本&#xff…...

微服务 RocketMQ-延时消息 消息过滤 管控台搜索问题

~~微服务 RocketMQ-延时消息 消息过滤 管控台搜索问题~~ RocketMQ-延时消息实现延时消息RocketMQ-消息过滤Tag标签过滤SQL标签过滤管控台搜索问题RocketMQ-延时消息 给消息设置延时时间&#xff0c;到一定时间&#xff0c;消费者才能消费的到&#xff0c;中间件内部通过每秒钟扫…...

js发送邮件(node.js)

以前看别人博客留言或者评论文章时必须填写邮箱信息&#xff0c;感觉甚是麻烦。 后来才知道是为了在博主回复后让访客收到邮件&#xff0c;用心良苦。 于是我也在新增留言和文章评论的接口里&#xff0c;新增了给自己发送邮件提醒的功能。 我用的QQ邮箱&#xff0c;具体如下…...

English Learning - Day58 一周高频问题汇总 2023.2.12 周日

English Learning - Day58 一周高频问题汇总 2023.2.12 周日这周主要内容继续说说状语从句结果状语从句这周主要内容 DAY58【周日总结】 一周高频问题汇总 &#xff08;打卡作业详见 Day59&#xff09; 一近期主要讲了 一 01.主动脉修饰 以下是最常问到的知识点拓展&#xff…...

【微电网】基于风光储能和需求响应的微电网日前经济调度(Python代码实现)

目录 1 概述 2 知识点及数学模型 3 算例实现 3.1算例介绍 3.2风光参与的模型求解 3.3 风光和储能参与的模型求解 3.5 风光储能和需求响应都参与模型求解 3.6 结果分析对比 4 Python代码及算例数据 1 概述 近年来&#xff0c;微电网、清洁能源等已成为全球关注的热点…...

四种方式的MySQL安装

mysql安装常见的方法有四种序号 安装方式 说明1 yum\rpm简单、快速&#xff0c;不能定制参数2二进制 解压&#xff0c;简单配置就可使用 免安装 mysql-a.b.c-linux2.x-x86_64.tar.gz3源码编译 可以定制参数&#xff0c;安装时间长 mysql-a.b.c.tar.gz4源码制成rpm包 把源码制…...

软考高级信息系统项目管理师系列之九:项目范围管理

软考高级信息系统项目管理师系列之九:项目范围管理 一、范围管理输入、输出、工具和技术表二、范围管理概述三、规划范围管理四、收集需求1.收集需求:2.需求分类3.收集需求的工具与技术4.收集需求过程主要输出5.需求文件内容6.需求管理7.可跟踪性8.双向可跟踪性9.需求跟踪矩阵…...

【项目精选】javaEE健康管理系统(论文+开题报告+答辩PPT+源代码+数据库+讲解视频)

点击下载源码 javaEE健康管理系统主要功能包括&#xff1a;教师登录退出、教师饮食管理、教师健康日志、体检管理等等。本系统结构如下&#xff1a; &#xff08;1&#xff09;用户模块&#xff1a; 实现登录功能 实现用户登录的退出 实现用户注册 &#xff08;2&#xff09;教…...

ctfshow nodejs

web 334 大小写转换特殊字符绕过。 “ı”.toUpperCase() ‘I’&#xff0c;“ſ”.toUpperCase() ‘S’。 “K”.toLowerCase() ‘k’. payload: CTFſHOW 123456web 335 通过源码可知 eval(xxx)&#xff0c;eval 中可以执行 js 代码&#xff0c;那么我们可以依此执行系…...

无线传感器原理及方法|重点理论知识|2021年19级|期末考试

Min-Max定位 【P63】 最小最大法的基本思想是依据未知节点到各锚节点的距离测量值及锚节点的坐标构造若干个边界框,即以参考节点为圆心,未知节点到该锚节点的距离测量值为半径所构成圆的外接矩形,计算外接矩形的质心为未知节点的估计坐标。 多边定位法的浮点运算量大,计算代…...

带你写出符合 Promise/A+ 规范 Promise 的源码

Promise是前端面试中的高频问题&#xff0c;如果你能根据PromiseA的规范&#xff0c;写出符合规范的源码&#xff0c;那么我想&#xff0c;对于面试中的Promise相关的问题&#xff0c;都能够给出比较完美的答案。 我的建议是&#xff0c;对照规范多写几次实现&#xff0c;也许…...

回流与重绘

触发回流与重绘条件&#x1f449;回流当渲染树中部分或者全部元素的尺寸、结构或者属性发生变化时&#xff0c;浏览器会重新渲染部分或者全部文档的过程就称为 回流。引起回流原因1.页面的首次渲染2.浏览器的窗口大小发生变化3.元素的内容发生变化4.元素的尺寸或者位置发生变化…...

openpyxl表格的简单实用

示例:创建简单的电子表格和条形图 在这个例子中,我们将从头开始创建一个工作表并添加一些数据,然后绘制它。我们还将探索一些有限的单元格样式和格式。 我们将在工作表上输入的数据如下: 首先,让我们加载 openpyxl 并创建一个新工作簿。并获取活动表。我们还将输入我们…...

【寒假day4】leetcode刷题

&#x1f308;一、选择题❤1.下列哪一个是析构函数的特征&#xff08; &#xff09;。A: 析构函数定义只能在类体内 B: 一个类中只能定义一个析构函数 C: 析构函数名与类名相同 D: 析构函数可以有一个或多个参数答案&#xff1a;B答案解析&#xff1a;析构函数是构造函…...

【竞赛题】6355. 统计公平数对的数目

题目&#xff1a; 给你一个下标从 0 开始、长度为 n 的整数数组 nums &#xff0c;和两个整数 lower 和 upper &#xff0c;返回 公平数对的数目 。 如果 (i, j) 数对满足以下情况&#xff0c;则认为它是一个 公平数对 &#xff1a; 0 < i < j < n&#xff0c;且 l…...

Redis集群搭建(主从、哨兵、分片)

1.单机安装Redis 首先需要安装Redis所需要的依赖&#xff1a; yum install -y gcc tcl然后将课前资料提供的Redis安装包上传到虚拟机的任意目录&#xff1a; 例如&#xff0c;我放到了/tmp目录&#xff1a; 解压缩&#xff1a; tar -xzf redis-6.2.4.tar.gz解压后&#xff1…...

Dart语法基础补充

Asynchrony support Dart 库中充满了返回 Future 或 Stream 对象的函数。 这些函数是异步的&#xff1a;它们在设置一个可能耗时的操作&#xff08;例如 I/O&#xff09;后返回&#xff0c;而不等待该操作完成。 async 和 await 关键字支持异步编程&#xff0c;让编写看起来类…...

Nginx - 深入理解nginx的处理请求、进程关系和配置文件重载

概述 Nginx的系统学习整理的第三篇博客&#xff0c;主要介绍nginx的应用场景和架构基础&#xff0c;以便更好的理解&#xff0c;再生产环境中进行性能调优。 Nginx的三个主要应用场景 1.静态资源服务&#xff0c;通过本地文件系统提供服务 2.反向代理服务&#xff0c;强大的性…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...