DFS(深度优先搜索)与回溯算法详解
DFS(深度优先搜索)与回溯算法详解
一、DFS 基础
1. 什么是DFS?
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。其核心思想是:
- 一条路走到黑:从起点出发,尽可能深入未访问的分支,直到无法继续前进。
- 回溯:当走到尽头时,回退到上一个分叉点,选择另一条未探索的路径继续深入。
2. DFS 的实现方式
DFS 可以通过两种方式实现:
- 递归:利用函数调用栈隐式实现回溯。
- 显式栈:手动维护一个栈来模拟递归过程。
示例:二叉树的DFS遍历
struct TreeNode {int val;TreeNode* left;TreeNode* right;
};// 递归实现DFS(前序遍历)
void dfs(TreeNode* root) {if (!root) return;cout << root->val << " "; // 访问当前节点dfs(root->left); // 递归左子树dfs(root->right); // 递归右子树
}
二、回溯算法
1. 什么是回溯?
回溯(Backtracking)是一种通过“试错”寻找问题解的算法。它在DFS的基础上,通过剪枝(Pruning)避免无效搜索,通常用于解决组合、排列、子集等需要穷举所有可能性的问题。
2. 回溯的核心步骤
- 选择:在当前状态下,做出一个可能的决策。
- 递归:基于这个决策,进入下一层递归。
- 撤销:递归返回后,撤销当前决策,回到之前的状态(即“回溯”)。
3. 回溯模板
void backtrack(路径, 选择列表) {if (满足终止条件) {将路径加入结果集;return;}for (选择 : 选择列表) {if (选择不合法) continue; // 剪枝做出选择; // 将选择加入路径backtrack(新路径, 新选择列表);撤销选择; // 将选择从路径中移除(回溯)}
}
三、经典问题与代码实现
1. 全排列问题
问题描述:给定无重复元素的数组 [1,2,3],返回所有可能的排列。
示例代码:
vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<int> path;vector<bool> used(nums.size(), false); // 记录元素是否被使用function<void()> backtrack = [&]() {if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (used[i]) continue; // 剪枝:已使用的元素跳过used[i] = true; // 做出选择path.push_back(nums[i]);backtrack();path.pop_back(); // 撤销选择used[i] = false;}};backtrack();return res;
}
2. 组合总和问题
问题描述:给定候选数组 [2,3,6,7] 和目标值 7,找出所有和为 7 的组合(元素可重复使用)。
示例代码:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> res;vector<int> path;sort(candidates.begin(), candidates.end()); // 排序便于剪枝function<void(int, int)> backtrack = [&](int start, int sum) {if (sum == target) {res.push_back(path);return;}for (int i = start; i < candidates.size(); i++) {if (sum + candidates[i] > target) break; // 剪枝:超过目标值跳过path.push_back(candidates[i]);backtrack(i, sum + candidates[i]); // 允许重复使用元素(i不+1)path.pop_back();}};backtrack(0, 0);return res;
}
3. N皇后问题
问题描述:在 N×N 的棋盘上放置 N 个皇后,使得它们不能互相攻击。
示例代码:
vector<vector<string>> solveNQueens(int n) {vector<vector<string>> res;vector<string> board(n, string(n, '.')); // 初始化棋盘function<bool(int, int)> isValid = [&](int row, int col) {// 检查列是否有冲突for (int i = 0; i < row; i++) {if (board[i][col] == 'Q') return false;}// 检查左上对角线for (int i = row-1, j = col-1; i >=0 && j >=0; i--, j--) {if (board[i][j] == 'Q') return false;}// 检查右上对角线for (int i = row-1, j = col+1; i >=0 && j < n; i--, j++) {if (board[i][j] == 'Q') return false;}return true;};function<void(int)> backtrack = [&](int row) {if (row == n) {res.push_back(board);return;}for (int col = 0; col < n; col++) {if (!isValid(row, col)) continue; // 剪枝:非法位置跳过board[row][col] = 'Q'; // 放置皇后backtrack(row + 1); // 处理下一行board[row][col] = '.'; // 回溯}};backtrack(0);return res;
}
四、回溯算法的优化技巧
-
剪枝:提前终止不可能得到解的路径。
- 条件剪枝:如组合总和问题中的
sum + candidates[i] > target。 - 去重剪枝:如全排列问题中跳过已使用的元素。
- 条件剪枝:如组合总和问题中的
-
排序预处理:对输入数组排序,便于剪枝(如组合总和问题)。
-
记忆化:记录已访问的状态,避免重复计算(如数独问题)。
五、DFS与回溯的关系
- DFS 是回溯的实现方式:回溯算法通常通过递归的DFS实现。
- 回溯是DFS的应用场景:DFS用于遍历所有可能性,回溯通过剪枝优化DFS的效率。
- 区别:
- DFS 更强调遍历所有路径(如二叉树的遍历)。
- 回溯 更强调通过试错寻找解(如组合、排列问题)。
六、总结
- DFS 是遍历树或图的算法,核心是“一条路走到黑”。
- 回溯 是基于DFS的优化策略,通过“试错+剪枝”寻找问题的解。
- 关键步骤:选择 → 递归 → 撤销选择(回溯)。
- 经典问题:全排列、组合总和、N皇后、子集、数独等。
练习题
- 实现子集问题(返回数组的所有子集)。
- 解决数独问题(填充所有空格)。
- 优化全排列代码,处理输入数组包含重复元素的情况。
相关文章:
DFS(深度优先搜索)与回溯算法详解
DFS(深度优先搜索)与回溯算法详解 一、DFS 基础 1. 什么是DFS? 深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。其核心思想是: 一条路走到黑:从起点出发…...
服务器虚拟化技术详解与实战:架构、部署与优化
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 引言 在现代 IT 基础架构中,服务器虚拟化已成为提高资源利用率、降低运维成本、提升系统灵活性的重要手段。通过服务…...
数据分析系列--②RapidMiner导入数据和存储过程
一、下载数据 二、导入数据 1. 在本地计算机中创建3个文件夹 2. 从本地选择.csv或.xlsx 三、界面说明 四、存储过程 1.保存 Congratulations, you are done. 一、下载数据 点击下载AssociationAnalysisData.xlsx数据集 二、导入数据 1. 在本地计算机中创建3个文件夹 2. 从…...
CSS 背景与边框:从基础到高级应用
CSS 背景与边框:从基础到高级应用 1. CSS 背景样式1.1 背景颜色示例代码:设置背景颜色 1.2 背景图像示例代码:设置背景图像 1.3 控制背景平铺行为示例代码:控制背景平铺 1.4 调整背景图像大小示例代码:调整背景图像大小…...
国内外人工智能AI工具网站大全(一键收藏,应有尽有)
本文由 大侠(AhcaoZhu)原创,转载请声明。 链接: https://blog.csdn.net/Ahcao2008 国内外人工智能AI工具网站大全(一键收藏,应有尽有) 摘要一、AI写作工具二、AI图像工具2.1、常用AI图像工具2.2、AI图片插画生成2.3、AI图片背景移…...
Java中初步使用websocket(springBoot版本)
一、什么是websocket WebSocket是一种在Web应用程序中实现实时双向通信的协议。它为浏览器和服务器之间提供了一种持久连接,在一个连接上可以双向传输数据。相比传统的HTTP协议,WebSocket具有更低的延迟和更高的效率。 WebSocket使用了类似于握手的方式来…...
2025年大年初一篇,C#调用GPU并行计算推荐
C#调用GPU库的主要目的是利用GPU的并行计算能力,加速计算密集型任务,提高程序性能,支持大规模数据处理,优化资源利用,满足特定应用场景的需求,并提升用户体验。在需要处理大量并行数据或进行复杂计算的场景…...
K8S ReplicaSet 控制器
一、理论介绍 今天我们来实验 ReplicaSet 控制器(也叫工作负载)。官网描述如下: 1、是什么? ReplicaSet 副本集, 维护一组稳定的副本 Pod 集合。 2、为什么需要? 解决 pod 被删除了,不能自我恢…...
FreeRTOS学习 --- 任务调度
开启任务调度器 作用:用于启动任务调度器,任务调度器启动后, FreeRTOS 便会开始进行任务调度 该函数内部实现,如下: 1、创建空闲任务(优先级最低) 2、如果使能软件定时器,则创建定…...
【小鱼闪闪】单片机开发工具——米思齐软件下载安装(图文)
浏览器打开网址 mixly.org, 在软件平台选择mixly离线版。 最新版本为3.0,会支持audinio, ESP32、ESP8266 , 可以选择下载安装器或者完整版。 这里选择下载安装器,下载后运行“一键更新.bat”,即可自动下载最新版本的M…...
MFC开发,给对话框添加垂直滚动条并解决鼠标滚动响应的问题
无论在使用QT或者MFC进行界面开发时,都会出现在一个对话框里面存在好多的选项,导致对话框变得非常长或者非常大,就会显现的不美观,在这种情况下通常是添加一个页面的滚动条来解决这个问题,下面我们就来介绍给MFC的对话…...
动态规划DP 最长上升子序列模型 导弹防御模型(题目分析+C++完整代码实现)
概览检索 动态规划DP 最长上升子序列模型 导弹防御系统 原题链接 AcWiing 187. 导弹防御系统 题目描述 为了对抗附近恶意国家的威胁,R国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。 例如࿰…...
LevelDB 源码阅读:写入键值的工程实现和优化细节
读、写键值是 KV 数据库中最重要的两个操作,LevelDB 中提供了一个 Put 接口,用于写入键值对。使用方法很简单: leveldb::Status status leveldb::DB::Open(options, "./db", &db); status db->Put(leveldb::WriteOptions…...
药店药品销售管理系统的设计与实现
标题:药店药品销售管理系统的设计与实现 内容:1.摘要 摘要:本文介绍了药店药品销售管理系统的设计与实现。该系统旨在提高药店的运营效率和管理水平,通过信息化手段实现药品销售、库存管理、财务管理等功能。本文详细阐述了系统的需求分析、设计思路、技…...
人格分裂(交互问答)-小白想懂Elasticsearch
通过交互式追问了解一个中间件 ? 啥是Elasticsearch ! 分布式搜索和分析引擎 ? 为啥是分布式搜索,单体难道用不了吗 ? 实际上是说这个东西可以分布式部署 ! 单机可用但扩展性差,分布式通过分片、副本和负载均衡实现海量数据存储与高并发处理 ? 提…...
【论文投稿-第八届智能制造与自动化学术会议(IMA 2025)】HTML, CSS, JavaScript:三者的联系与区别
大会官网:www.icamima.org 目录 前言 一、HTML(超文本标记语言):网页的骨架 HTML 的作用: 例子: 总结: 二、CSS(层叠样式表):网页的外观设计 CSS 的…...
python | OpenCV小记(一):cv2.imread(f) 读取图像操作(待更新)
python | OpenCV小记(一):cv2.imread(f)读取图像操作 1. 为什么 [:, :, 0] 提取的是第一个通道(B 通道)?OpenCV 的通道存储格式索引操作 [:, :, 0] 的解释常见误解 1. 为什么 [:, :,…...
网络工程师 (9)文件管理
一、树形目录结构 (一)定义与构成 树形目录结构由一个根目录和若干层子文件夹(或称为子目录)组成,它像一棵倒置的树。这棵树的根称为根文件夹(也叫根目录),从根向下,每一…...
Java中的线程池参数(详解)
public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler) {} 此构造方法的参数如下: int corePoolSize&…...
2 MapReduce
2 MapReduce 1. MapReduce 介绍1.1 MapReduce 设计构思 2. MapReduce 编程规范3. Mapper以及Reducer抽象类介绍1.Mapper抽象类的基本介绍2.Reducer抽象类基本介绍 4. WordCount示例编写5. MapReduce程序运行模式6. MapReduce的运行机制详解6.1 MapTask 工作机制6.2 ReduceTask …...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
