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

解析：深度优先搜索、广度优先搜索和回溯搜索

news 来源：原创 2025/8/14 16:08:44

一、深度优先搜索（DFS）

1. 原理

思想：从起始节点出发，顺着一条路径不断深入，直到到达目标或无路可走，然后回溯到最近的分支点，继续探索其他分支。
应用场景：路径查找、连通性检测、拓扑排序、强连通分量、迷宫求解等。

2. 算法步骤（递归／栈式示例）

DFS(u):标记 u 为已访问for 每个邻居 v ∈ Adj[u]:if v 未访问:DFS(v)

伪代码（使用显式栈）：

function DFS(start):stack ← 空栈push start 到 stackwhile stack 非空:u ← pop stackif u 未访问:标记 u 为已访问for v ∈ Adj[u]:            // 可按任意顺序if v 未访问:push v 到 stack

3. 时间复杂度推导

节点个数：|V|
边数：|E|
每个节点只标记一次，每条边在遍历邻接表时也只会被看一遍（无向图会重复两次，但常写为 O(E)）。
总时间：
$T_{\mathrm{DFS}} = O(|V| + |E|)$

4. 空间复杂度

递归栈／显式栈最坏深度为 O(h)，h 为搜索深度（在图上为 O(|V|)），加上标记数组 O(|V|)。
空间：O(|V| + h) ≈ O(|V|)。

5. 优缺点

优点
- 实现简单，递归写法直观。
- 空间开销通常较 BFS 小（受限于深度而非宽度）。
- 易于回溯，可用于拓扑排序、强连通分量等高级图算法。
缺点
- 不保证最短路径（先深入，再回退）。
- 在最坏情况下可能退入极深的递归，导致栈溢出。
- 对于特别深或含环的图，需要事先做好“已访问”标记防止死循环。

二、广度优先搜索（BFS）

1. 原理

思想：以起始节点为根，先访问其所有邻居，再依次访问下一层邻居，保证层级（距离）依次递增。
应用场景：最短路径（无权图）、分层遍历、最小跳数问题、连通分量检测等。

2. 算法步骤（队列式）

function BFS(start):创建空队列 Q标记 start 为已访问；enqueue start 到 Qwhile Q 非空:u ← dequeue Qfor v ∈ Adj[u]: if v 未访问:标记 v 为已访问enqueue v 到 Q

3. 时间复杂度推导

与 DFS 一样，每个顶点进队出队各一次，访问每条边一次。
总时间：
$T_{\mathrm{BFS}} = O(|V| + |E|)$

4. 空间复杂度

队列在最宽层级可能存放 O(w) 个节点，w 最坏可至 O(|V|)。
标记数组 O(|V|)。
空间：O(|V|)。

5. 优缺点

优点
- 保证找到从起点到任一节点的最短（最少边）路径。
- 实现简单，易于理解。
缺点
- 对内存要求高，最宽层可能存放大量节点。
- 在极度稠密或高 branching 的情况下，空间迅速膨胀。

三、回溯搜索（Backtracking）

1. 原理

思想：系统地构造解空间树，试探每一个可能的解分支，一旦发现某一路径不可能通向可行解（违反约束或已达死胡同），便“回溯”撤销最近那一步，尝试其他可能。
应用场景：组合优化（八皇后、子集和、图着色）、约束满足问题（CSP）、数独、排列生成等。

2. 算法步骤（示例：N 皇后）

function backtrack(状态 state):if state 满足完整解条件:输出一个解returnfor 每个候选分支 choice in 可行 choices(state):做出 choice（更新 state）backtrack(state)撤销 choice（恢复 state）

关键在于保持“可行性检测”函数，及时剪枝。

3. 时间复杂度推导

记号：
- b = 平均分支因子（每一步可做的选择数）
- d = 解的最大深度（决策步数）
解空间大小：
若无剪枝，则节点总数 ≈
$1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1} = O(b^d)$
因此，最坏时间复杂度：
$T_{\mathrm{BT}} = O(b^d)$
剪枝：若能有效剪枝，平均复杂度可大幅降低，但仍指数级别。

4. 空间复杂度

主花销在于递归栈深度 O(d) 及维护当前解的空间 O(d)。
空间：O(d)。

5. 优缺点

优点
- 通用性强，可处理任意约束问题。
- 通过剪枝和启发式（如最小剩余值、动态变量排序）可极大加速。
缺点
- 指数级复杂度，极易爆炸。
- 过度依赖剪枝策略和问题结构。

四、算法横向对比

特性	DFS	BFS	Backtracking
搜索方式	深度优先	广度优先	构造—试探—回溯
数据结构	递归栈 / 显式栈	队列	递归栈
时间复杂度	$T_{\mathrm{DFS}} = O(\|V\| + \|E\|)$	$T_{\mathrm{BFS}} = O(\|V\| + \|E\|)$	$T_{\mathrm{BT}} = O(b^d)$
空间复杂度	O(V）	O(V）	O(d）
最短路径	不保证	保证（无权图）	视问题而定
完整性	可遍历整个连通分量	可遍历所有可达节点	完备（会枚举所有解/证明无解）
剪枝能力	仅防环	仅防环	高度依赖剪枝策略
应用场景	拓扑排序、强连通分量等	最短路径、层次遍历	组合优化、约束满足
优点	简单，内存小	最短路径保证，简单	通用性强，可剪枝
缺点	可能深度过大，易爆栈	空间开销大	指数爆炸，剪枝难设计

若关心最短路径：选 BFS；
若场景需遍历全图／做结构化分析：可优先 DFS；
若需在剪枝约束下寻找可行解或全部解：回溯算法是首选。

解析：深度优先搜索、广度优先搜索和回溯搜索

一、深度优先搜索（DFS） 1. 原理思想：从起始节点出发，顺着一条路径不断深入，直到到达目标或无路可走，然后回溯到最近的分支点，继续探索其他分支。应用场景：路径查找、连通性检测、…...

编程日记 2025/8/14 16:08:44

探索大语言模型（LLM）：循环神经网络的深度解析与实战（RNN、LSTM 与 GRU）

一、循环神经网络（RNN） 1.1 基本原理循环神经网络之所以得名，是因为它在处理序列数据时，隐藏层的节点之间存在循环连接。这意味着网络能够记住之前时间步的信息，并利用这些信息来处理当前的输入。想象一下&#xf…...

编程日记 2025/8/11 6:34:01

从零开始开发 MCP Server

作者：张星宇在大型语言模型（LLM）生态快速演进的今天，Model Context Protocol（MCP）作为连接 AI 能力与真实世界的标准化协议，正逐步成为智能体开发的事实标准。该协议通过定义 Resources&#…...

编程日记 2025/8/11 3:00:29

Oracle日志系统之重做日志和归档日志

Oracle日志系统之重做日志和归档日志重做日志归档日志本文讨论Oracle日志系统中对数据恢复非常重要的两个日志：重做日志和归档日志。重做日志重做日志，英文名Redo Log，顾名思义，是用来数据重做的，主要使用场景是事…...

编程日记 2025/8/10 5:39:49

嵌入式开发--STM32G4系列硬件CRC支持MODBUS和CRC32

需求在项目中，需要用到MODBUS CRC16校验，也要用到CRC32的校验，出于效率的考虑，准备用硬件CRC。 CRC 16的参数模型有很多种，我这里用的是MODBUS，对于不同的参数模型，会有不同的参数设置和初值&a…...

编程日记 2025/8/7 23:53:29

基于尚硅谷FreeRTOS视频笔记——4—多任务处理

目录多任务处理任务调度任务的调度策略优先级不同优先级相同多任务处理通俗来讲就是能够在同一时间同时进行多个任务的处理，这就时多任务处理。但是，单核处理器一次只能处理一个任务，就是说在while中，任务们只能…...

编程日记 2025/8/13 17:24:26

中小型及初创企业如何实现数字化转型？

在当今动态的商业环境中，财务团队开始肩负起推动企业数字化转型的重任，即从传统的财务规划系统稳步迈向基于商业智能平台和以创新技术为驱动的解决方案领域。这些举措有望提高运营和分析效率，同时依托数据驱动的决策机制，帮助企业…...

编程日记 2025/8/5 14:59:26

先创建一个用于测试的java 编写程序 #java.util使java标准库的一个包，这里拉取Scanner类 import java.util.Scanner;public class VariableTest {public static void main(String[] args) {#创建一个 Scanner 对象Scanner scanner new Scanner(System.in);System.…...

编程日记 2025/8/14 12:59:14

Python基础知识语法归纳总结（数据类型-1）

Python基础知识&语法归纳总结（数据类型） 一、Python基本数据类型尤其注意，Python中的变量不需要特定的去声明，每个变量在使用前都必须对其进行赋值，它没有类型，我们所说的“类型”是变量所指的内存中对…...

编程日记 2025/8/13 5:06:25

Spring数据访问全解析：ORM整合与JDBC高效实践

目录一、Spring ORM集成深度剖析 🌟 ORM模块架构设计核心集成特性： 整合MyBatis示例配置： 二、Spring JDBC高效实践指南 🌟 传统JDBC vs Spring JDBC对比 🌟 JdbcTemplate核心操作示例批量操作优化&#xf…...

编程日记 2025/8/14 1:27:06

哪种电脑更稳定？Mac？Windows？还是云电脑？实测解密

随着科技的发展进步，电脑已成为当下各类群体的必备产品之一，它的妙用有很多，无论是学生党、打工人还是已经退休的人群或都离不开它的存在。然而，电脑虽好却也差异很大、不同品牌、不同系统、不同配置、不同价位的统统都会有区别。…...

编程日记 2025/8/9 17:27:32

【AI模型学习】关于写论文——论文的审美

文章目录一、“补丁法”（Patching）1.1 介绍1.2 方法论1.3 实例二、判断工作的价值2.1 介绍2.2 详细思路2.3 科研性vs工程性三、novelty以及误区3.1 介绍3.2 举例看了李沐老师的读论文系列后，总结三个老师提到的有关课题研究和论文写作的三…...

编程日记 2025/8/7 1:58:43

【面经】杭州产链数字科技一面

1.介绍一下自己面试官您好！我叫***，目前是就读于****计算机科学与技术专业的一名学生。我平时在学校也自学了编程相关的知识，比如Java基础、Springboot、SpringCloud，关系型数据库Mysql，非关系型数据库Redis&#xff…...

编程日记 2025/8/10 14:09:24

微信小程序调用yolo目标检测模型

目录后端前端微信小程序完整代码后端利用Flask，调用目标检测模型，后端代码如下。 # flask_yolo.py from flask import Flask, request, jsonify from ultralytics import YOLO from PIL import Imageapp Flask(__name__) model_path best.p…...

编程日记 2025/8/10 16:38:34

vmware17 虚拟机 ubuntu22.04 桥接模式，虚拟机无法接收组播消息

问题描述： 在一个项目中，宿主机win10中，使用的vmware17pro 虚拟机安装的ubuntu22.04，按照网上的教程使用Qt绑定组播消息，在另外一个Ubuntu工控机上发送用wiresahrk抓包的组播消息 sudo tcpreplay -i enp1s0 --loop0 y…...

编程日记 2025/8/12 16:00:33

Kaggle-Bag of Words Meets Bags of Popcorn-(二分类+NLP+Bert模型)

Bag of Words Meets Bags of Popcorn 题意： 有很多条电影评论记录，问你每一条记录是积极性的评论还是消极性的评论。数据处理： 1.首先这是文件是zip形式，要先解压，注意sep ‘\t’。 2.加载预训练的 BERT 分词器 …...

编程日记 2025/8/12 20:40:00

数字信号处理技术架构与功能演进

数字信号处理（DSP）是通过数字运算实现信号分析、变换、滤波及调制解调的技术领域，其发展过程与技术应用如下： 一、定义与核心功能技术定义：通过算法将模拟信号转换为数字形式进行处理，具有高精度、可编程…...

编程日记 2025/8/14 23:28:38

IaaS架构剖析、场景实践

一、什么是 IaaS 1.1 定义 Infrastructure as a Service（IaaS，基础设施即服务）是一种按需、弹性提供计算、存储、网络和安全等底层 IT 资源的云服务模式。用户通过 API、CLI 或 Web 控制台即可在几分钟内创建、扩容或释放资源，而…...

编程日记 2025/8/14 14:04:24

国产之光DeepSeek架构理解与应用分析02

本专栏国产之光DeepSeek架构理解与应用分析-CSDN博客国产之光DeepSeek架构理解与应用分析02-CSDN博客前置的一些内容理解 GPU TPU NPU的区别？ 设计目的 GPU：最初是为了加速图形渲染而设计的，用于处理图像和视频数据，以提供高…...

编程日记 2025/8/13 9:30:41

EDID结构

EDID DDC通讯中传输显示设备数据 VGA , DVI 的EDID由128字节组成，hdmi的EDID增加扩展块128字节。扩展快的内容主要是和音频属性相关的，DVI和vga没有音频，hdmi自带音频，扩展快数据规范按照cea-861x标准。 Edid为了让pc或其他的图像…...

编程日记 2025/8/3 5:58:50

4.黑马学习笔记-SpringMVC(P43-P47)

1.SpringMVC简介 SpringMVC技术（更少的代码，简便）与servlet技术功能相同，属于web层开发技术。 SpringMVC是一种基于java实现MVC模型的轻量级web框架。轻量级指的是（内存占用比较低，运行效率高）…...

编程日记 2025/8/3 5:58:48

CSS 文件格式

A QFrame#andrFrm[status"android_en"] A：表示父类或顶层窗口的类型。如果 A 是一个自定义的类名，确保该类已经正确注册到 Qt 系统中。QFrame：表示具体的控件类型。#andrFrm：表示控件的对象名称（通过 setOb…...

编程日记 2025/8/3 5:58:46

java输出HelloWorld

创建一个java格式文件，这里命令为HelloWorld 这里我选择用notepad编译，也可以直接用记事本 #public 访问修饰词，表示这个类可以被其他任何类访问 #class 定义类的关键字 #HelloWorld 类名，遵循驼峰命名法（首字母大写…...

编程日记 2025/8/12 12:44:59

【SAP ME 44】在 HANA DB中报废SFC时的SHOP_ORDER表记录锁定

症状 SELECT…FROM SHOP_ORDER FOR UPDATE 在 SFC 报废期间持有锁，当同时调用数量较大时，可能会导致 HANA 数据库出现大量锁积压。这有时会导致因等待 HANA 数据库释放“选择更新”锁而导致报废 SFC 花费数分钟。 HANA 数据库日志中的示例： # begin PreparedStatement_ex…...

编程日记 2025/8/10 5:17:24

《软件设计师》复习笔记（12.1）——范围管理、进度管理

目录一、范围管理 1. 核心概念 2. 范围管理过程 WBS（工作分解结构）示例真题示例： 二、进度管理 1. 核心过程 2. 关键工具与技术真题示例： 一、范围管理 1. 核心概念项目范围：为交付产品必须完成的工作…...

编程日记 2025/8/15 6:30:39

Git-使用教程（新手向）

一、基本概念： 1.Git，Github的关系： Git --- 本地用于管理代码的工具，可类比为游戏存档。（存档，仓库，项目在Git中是一个东西） Github --- 远程仓库平台，可类比为云端。…...

编程日记 2025/8/14 16:54:00

密码学中的盐值是什么？

目录 1. 盐值的基本概念 2. 盐值的作用 (1) 防止彩虹表攻击 (2) 防止相同的密码生成相同的哈希值 (3) 增加暴力破解的难度 3. 如何使用盐值？ (1) 生成盐值 (2) 将盐值附加到密码 (3) 存储盐值和哈希值 (4) 验证密码 4. 盐值如何增加暴力破解的难度在线暴…...

编程日记 2025/8/10 19:38:32

[工具]Java xml 转 Json

[工具]Java xml 转 Json 依赖  <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.37</version> </dependen…...

编程日记 2025/8/14 17:30:57

安全光幕的CE认证

在工业自动化飞速发展的当下，安全光幕作为保障操作人员安全的关键设备，其重要性不言而喻。对于想要进军欧盟市场的安全光幕制造商来说，CE 认证是必须跨越的一道关卡。今天，我们就来深入探讨安全光幕的 CE 认证流程。什么是安全…...

编程日记 2025/8/10 22:11:18

DNS解析失败怎么解决？

在互联网时代，畅快地浏览网页、使用各类网络服务已成为生活常态。然而，当屏幕突然弹出 “DNS解析失败”的提示，原本顺畅的网络连接戛然而止，让人倍感困扰。DNS即域名系统，它如同互联网的 “电话簿”，负责将…...

编程日记 2025/8/7 5:11:52

亚马逊商品详情API数据接口概述，Amazon API

亚马逊商品详情API数据接口概述亚马逊商品详情API（如Amazon Product Advertising API或Selling Partner API (SP-API)）是亚马逊为开发者提供的官方接口，允许通过编程方式获取商品的详细信息，包括商品标题、价格、描述、图片、用…...

编程日记 2025/8/13 18:23:10

TCP/IP和UDP协议的发展历程

TCP/IP和UDP协议的发展历程引言互联网的发展史是人类技术创新的辉煌篇章，而在这一发展过程中，通信协议发挥了奠基性的作用。TCP/IP（传输控制协议/互联网协议）和UDP（用户数据报协议）作为互联网通信的基础…...

编程日记 2025/8/15 2:32:49

LeetCode 259 题全解析：Swift 快速找出“满足条件”的三人组

文章目录摘要描述示例 1：示例 2：示例 3： 题解答案（Swift）题解代码分析示例测试及结果时间复杂度空间复杂度总结摘要本文围绕 LeetCode 259 题“较小的三数之和”，通过 Swift 给出两种解法，并…...

编程日记 2025/8/6 23:52:12

【MySQL】MySQL表的增删改查（CRUD） —— 上篇

目录 MySQL表的增删改查（CRUD） 1. 新增（Create）/插入数据 1.1 单行数据全列插入 insert into 表名 values(值, 值......); 1.2 单行数据指定列插入 1.3 多行数据指定列插入 1.4 关于时间日期（datetime&am…...

编程日记 2025/8/13 1:21:55

基于大模型的腹股沟疝诊疗全流程风险预测与方案制定研究报告

目录一、引言 1.1 研究背景与意义 1.2 国内外研究现状 1.3 研究目的与创新点二、大模型技术概述 2.1 大模型基本原理 2.2 常用大模型类型及特点 2.3 大模型在医疗领域的应用潜力三、腹股沟疝诊疗流程分析 3.1 腹股沟疝的发病机制与分类 3.2 传统术前评估方法与局…...

编程日记 2025/8/15 11:33:35

使用nssm将Nginx配置为Windows服务

使用nssm将Nginx配置为Windows服务下载nssm工具 ：使用NSSM创建服务启动并验证服务管理服务（启动/停止/重启） 下载nssm工具 ： nssm下载网址下载到指定路径下，解压就行。使用NSSM创建服务 winr打开运行命令框&am…...

编程日记 2025/8/10 4:55:38

（8）VTK C++开发示例 --- 交互式3D部件

文章目录 1. 概述2. CMake链接VTK3. main.cpp文件4. 演示效果更多精彩内容👉内容导航 👈👉VTK开发 👈 1. 概述这个例子介绍了3D小部件（vtkBoxWidget）。3D小部件利用了前面介绍的事件/观察者设计模式。它们…...

编程日记 2025/8/13 6:22:50

ReAct、CoT 和 ToT：大模型提示词推理架构的对比分析

ReAct、CoT 和 ToT：大模型提示词推理架构的对比分析在大型语言模型（LLM）的研究与应用中，如何有效提升模型在复杂任务上的推理能力是关键问题之一。目前，ReAct（Reasoning and Acting）、CoT&…...

编程日记 2025/8/12 10:08:27

Evidential Deep Learning和证据理论教材的区别（主要是概念）

最近终于彻底搞懂了Evidential Deep Learning，之前有很多看不是特别明白的地方，原来是和证据理论教材（是的，不只是国内老师写的，和国外的老师写的教材出入也比较大）的说法有很多不一样，所以特地…...

编程日记 2025/8/11 3:00:28

golang context源码

解析 context结构 Deadline：返回 context 的过期时间； Done：返回 context 中的 channel； Err：返回错误； Value：返回 context 中的对应 key 的值. type Context interface {Deadline() (deadl…...

编程日记 2025/8/15 4:52:00

VSCODE插值表达式失效问题

GET https://cdn.jsdelivr.net/npm/vue2.6.14/dist/vue.js net::ERR_CONNECTION_-CSDN博客更换正确的vue域名 GET https://cdn.jsdelivr.net/npm/vue2.6.14/dist/vue.js net::ERR_CONNECTION_ <script src"https://unpkg.com/vue2.6.14/dist/vue.js"></sc…...

编程日记 2025/8/15 10:29:59

6.VTK 颜色

文章目录概念RGB示例HSV示例概念 RGB颜色系统：通过红(R)、绿(G)、蓝(B)三个颜色分量的组合来定义颜色。每个分量的取值范围是0到1，其中(0, 0, 0)代表黑色，而(1, 1, 1)代表白色。可以使用vtkProperty::SetColor(r, g, b)方法为Actor设置颜色…...

编程日记 2025/8/12 9:56:17

MQTTClient.c的线程模型与异步事件驱动

MQTTClient.c的线程模型与异步事件驱动 1. 多线程架构设计 MQTTClient.c通过分离网络I/O和用户逻辑线程实现异步通信，核心设计如下： sequenceDiagramparticipant 主线程 as 主线程（用户调用）participant 发送队列 as 发送队列pa…...

编程日记 2025/8/14 8:50:29

Flutter异常Couldn‘t find dynamic library in default locations

Flutter项目在Windows系统使用ffigen生成代码时报下面的错误： [SEVERE] : Couldnt find dynamic library in default locations. [SEVERE] : Please supply one or more path/to/llvm in ffigens config under the key llvm-path. Unhandled exception: Exception: …...

编程日记 2025/8/13 5:31:36

在PyCharm中部署AI模型的完整指南

引言随着人工智能技术的快速发展，越来越多的开发者开始将AI模型集成到他们的应用程序中。PyCharm作为一款强大的Python IDE，为AI开发提供了出色的支持。本文将详细介绍如何在PyCharm中部署AI模型，从环境配置到最终部署的完整流程。第一部分：准备工作 1. 安装PyCharm …...

编程日记 2025/8/12 19:31:50

6.6.图的广度优先遍历(英文缩写BFS)

树是一种特殊的图，树的广度优先遍历即层次遍历，所以会从树的角度入手图的广度优先遍历： BFS与DFS的区别在于，BFS使用了队列，DFS使用了栈一.广度优先遍历： 1.树的广度优先遍历： 详情见"…...

编程日记 2025/8/13 1:24:07

练习（杨辉三角、字符串旋转）

一、以下程序执行的结果： int main() {//0~255unsigned char a 200;//00000000000000000000000011001000//11001000 - a 截断unsigned char b 100;//00000000000000000000000001100100//01100100 - b unsigned char c 0;c a b;//11001000 - a//0110010…...

编程日记 2025/8/10 12:34:09