回溯算法理论基础
目录
- 什么是回溯法
- 回溯法的效率
- 回溯法解决的问题
- 如何理解回溯法
- 回溯法模板
什么是回溯法
回溯法也可以叫做回溯搜索法,它是一种搜索的方式。
回溯是递归的副产品,只要有递归就会有回溯。
所以以下讲解中,回溯函数也就是递归函数,指的都是一个函数。
回溯法的效率
回溯法的性能如何呢,这里要和大家说清楚了,虽然回溯法很难,很不好理解,但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢?
因为没得选,一些问题能暴力搜出来就不错了,撑死了再剪枝一下,还没有更高效的解法。
此时大家应该好奇了,都什么问题,这么牛逼,只能暴力搜索。
回溯法解决的问题
回溯法,一般可以解决如下几种问题:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
组合是不强调元素顺序的,排列是强调元素顺序。
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构,是的,我指的是所有回溯法的问题都可以抽象为树形结构!
因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。
递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。
回溯法模板
回溯三部曲
- 1.回溯函数模板返回值以及参数
回溯算法中函数返回值一般为void。
再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数。
回溯函数伪代码如下:
void backtracking(参数)
- 2.回溯函数终止条件
什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。
回溯函数伪代码如下:
if (终止条件) {存放结果;return;
}
- 3.回溯搜索的遍历过程

回溯函数遍历过程伪代码如下:
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果
}
for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历
回溯算法模板框架如下:
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}相关文章:
回溯算法理论基础
目录什么是回溯法回溯法的效率回溯法解决的问题如何理解回溯法回溯法模板什么是回溯法 回溯法也可以叫做回溯搜索法,它是一种搜索的方式。 回溯是递归的副产品,只要有递归就会有回溯。 所以以下讲解中,回溯函数也就是递归函数,指…...
【STM32笔记】低功耗模式下GPIO省电配置避坑实验(闲置引脚配置为模拟输入其实更耗电)
【STM32笔记】低功耗模式下GPIO省电配置避坑实验(闲置引脚配置为模拟输入其实更耗电) 前文: blog.csdn.net/weixin_53403301/article/details/128216064 【STM32笔记】HAL库低功耗模式配置(ADC唤醒无法使用、低功耗模式无法烧录解…...
AI算法创新赛-人车目标检测竞赛总结02
源码目录--AI0000026/ --models/ #存放原始模型文件 --scripts/ #存放模型编译、量化所用到的命令脚本,标签格式转换的脚本。 --data/ #存放B榜数据集102张图片 --bmodel/ #存放编译或量化生成的xxx.bmodel --test/ #存放执行推理的代码,会调用bmodel/中…...
Python 编程必备:盘点nginx和gunicorn的几大用法,建议收藏
程序员是新兴技术工种中比较高薪的一个,在互联网公司,程序员往往与秃头,压力大,找不到女朋友等等挂钩。 最近,最新技能类榜单出炉,这是一个关于程序员自己给自己贴的几个标签。 其中,不难看出…...
USB3.0移动硬盘启动Win7的方法(AHCI/AMD USB3.0/Win7)
古董电脑(intel处理器,无USB3.0接口)突然坏了,已经没有维修价值了,硬盘还是完好的。欲把硬盘拆下来,装到USB3.0硬盘盒上,然后在新电脑(AMD R5-4650G/A520)上从USB3.0硬盘盒上启动。 一、需要工具 SATA数据线PS/2鼠标…...
Python学习-----函数3.0(嵌套函数、闭包、装饰器)
目录 1.函数嵌套 2.闭包 3.装饰器 这一节,我会详细Python中讲解函数的进阶内容,包括嵌套函数、闭包和装饰器。一起来学习吧!!! 1.函数嵌套 概念:函数里面再定义一个函数 作用:当我们在一个多…...
最新版EasyRecovery数据恢复软件使用测评介绍
我们在逐渐适应信息电子化的同时,也有一些潜在的麻烦接踵而来,其中较为常见的就是文件和数据的保存问题。显然,设备的存储空间是有限的,这就不可避免地会出现数据被删除、覆盖或丢失的现象,如果丢失的是重要数据&#…...
关于知识图谱TransR
论文题目 Learning Entity and Relation Embeddings for Knowledge Graph Completion 论文链接 TransR 文中指出,不管是TransE还是TransH都是将实体和关系映射同一空间,但是,一个实体可能具有多个层面的信息,不同的关系可能关注…...
始于日志,不止于日志,Elastic Stack全面介绍
1、Elastic Stack是什么? 说Elastic Stack之前,先说一下ELK Stack。这个词相信很多人都是耳熟能详的,作为一个著名的日志系统解决方案,应用非常广泛。 “ELK”是三个开源项目的首字母缩写词:Elasticsearch、Logstash…...
FDX-B|EMID格式低频RFID 读卡模块LD6900技术选型与说明
FDX-B|EMID格式低频RFID 读卡模块LD6900是华翔天诚推出一款基于 RFID 无线射频识别技术的低频(LF)读卡模块,工作频率支持 134.2KHZ、125KHZ,符合 ISO 11784/5 国际标准,支持对 FDX-B、EMID 两种协议格式电子标签的读取…...
《SQL基础》11. 索引
SQL - 索引索引概述结构B-TreeBTreeHash思考分类语法SQL性能分析SQL执行频率慢查询日志profile详情explain执行计划索引失效情况范围查询索引列运算字符串不加引号模糊查询or连接条件数据分布影响使用规则最左前缀法则SQL提示覆盖索引前缀索引设计原则索引 概述 索引…...
【前端】进阶Mac OS软件商城页面_缤纷多彩的创意UI
非常漂亮的仿Mac OS界面,更改下参数就可以变成你需要的界面。 还可以一键更换背景主题 灵感来源于米科瓦伊加文齐奥夫斯基 附上css、html、js源码 下面是html文件 <!DOCTYPE html> <html lang"en" > <head><meta charset"…...
格创东智与金羽新能合作|先进工业互联网助力固态电池智能化运营
2022年12月,浙江金羽新能源科技有限公司(以下简称金羽新能)与格创东智签订战略合作框架协议,并在湖州安吉举行金羽新能固态电池MES项目启动会。 固态电池是一种使用固体电极和固体电解质的电池。相较传统锂电池(液态电…...
软件测试面试刷题app包含了各种难题
软件测试的生命周期: V模型:与软件开发阶段呼应 软件开发:需求分析-->概要设计-->详细设计-->编码阶段软件测试:单元测试-->集成测试-->系统测试-->验收测试从基本流程的角度讲: 需求阶段ÿ…...
19、ClickHouse企业中常见的20种用法
文章目录19、ClickHouse企业中常见的20种用法-- 1、表结构添加字段-- 2、删除语句-- 3、更新语法-- 4、查询表字段结构-- 5、展示字段加密处理 身份证号(字母加数字)加密-- 6、展示字段加密处理 手机号(纯数字)加密-- 7、计数 去重…...
怎么样用香港主机搭建游戏网站
香港是全球主要的互联网骨干节点,拥有质量较高的网络基础设施,在网络速度和稳定性方面表现良好。因此,使用香港主机搭建游戏网站可以使用户在游戏中的体验流畅且基本不会延迟情况。本文将向用户解释如何使用香港主机搭建游戏网站。在搭建游戏…...
重磅!GitLab 提出五大预测,洞见 2023 年 DevSecOps 发展趋势
本文来源:about.gitlab.com 作者:Sandra Gittlen 译者:极狐(GitLab) 市场部内容团队 2023 年,企业会将更多的时间和资源投入到持续的安全左移上,完成从 DevOps 到 DevSecOps 的演变。 GitLab CMSO Ashley Kramer 表示…...
内核模块(传参和依赖)
目录 一、模块传参 二、模块依赖 三、内核空间和用户空间 四、执行流 五、模块编程与应用编程的比较 六、内核接口头文件查询 七、小作业 一、模块传参 module_param(name,type,perm);//将指定的全局变量设置成模块参数 name:全局变量名 type: 使用符号 …...
基础篇:03-SpringCloud工程部署启动
目录 1.工程搭建部署 方案一:完整工程导入 方案二:从零开始搭建 1.工程与module创建 2.数据库导入 3.项目启动 3.1 启动并访问user-service 3.2 启动并访问order-service 4.服务远程调用 时序图说明 服务远程调用实现 注入RestTemplate Res…...
二、产品经理——【需求收集】【需求管理】
0. 学习目标 能够理解并描述需求能够收集并管理需求 1. 如何定义需求 1.1. 需求的定义 原始需求:没有经过任何分析,或者没有经过任何额外解读的需求信息 避免日后纠纷,尽量记录一下原始需求!先记录下来,后面再进行分…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
