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

回溯算法理论基础

目录

    • 什么是回溯法
    • 回溯法的效率
    • 回溯法解决的问题
    • 如何理解回溯法
    • 回溯法模板

什么是回溯法

回溯法也可以叫做回溯搜索法,它是一种搜索的方式。
回溯是递归的副产品,只要有递归就会有回溯。
所以以下讲解中,回溯函数也就是递归函数,指的都是一个函数。

回溯法的效率

回溯法的性能如何呢,这里要和大家说清楚了,虽然回溯法很难,很不好理解,但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢?
因为没得选,一些问题能暴力搜出来就不错了,撑死了再剪枝一下,还没有更高效的解法。
此时大家应该好奇了,都什么问题,这么牛逼,只能暴力搜索。

回溯法解决的问题

回溯法,一般可以解决如下几种问题:

  • 组合问题: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提示覆盖索引前缀索引设计原则索引 概述 索引&#xf…...

【前端】进阶Mac OS软件商城页面_缤纷多彩的创意UI

非常漂亮的仿Mac OS界面&#xff0c;更改下参数就可以变成你需要的界面。 还可以一键更换背景主题 灵感来源于米科瓦伊加文齐奥夫斯基 附上css、html、js源码 下面是html文件 <!DOCTYPE html> <html lang"en" > <head><meta charset"…...

格创东智与金羽新能合作|先进工业互联网助力固态电池智能化运营

2022年12月&#xff0c;浙江金羽新能源科技有限公司&#xff08;以下简称金羽新能&#xff09;与格创东智签订战略合作框架协议&#xff0c;并在湖州安吉举行金羽新能固态电池MES项目启动会。 固态电池是一种使用固体电极和固体电解质的电池。相较传统锂电池&#xff08;液态电…...

软件测试面试刷题app包含了各种难题

软件测试的生命周期&#xff1a; V模型&#xff1a;与软件开发阶段呼应 软件开发&#xff1a;需求分析-->概要设计-->详细设计-->编码阶段软件测试&#xff1a;单元测试-->集成测试-->系统测试-->验收测试从基本流程的角度讲&#xff1a; 需求阶段&#xff…...

19、ClickHouse企业中常见的20种用法

文章目录19、ClickHouse企业中常见的20种用法-- 1、表结构添加字段-- 2、删除语句-- 3、更新语法-- 4、查询表字段结构-- 5、展示字段加密处理 身份证号&#xff08;字母加数字&#xff09;加密-- 6、展示字段加密处理 手机号&#xff08;纯数字&#xff09;加密-- 7、计数 去重…...

怎么样用香港主机搭建游戏网站

香港是全球主要的互联网骨干节点&#xff0c;拥有质量较高的网络基础设施&#xff0c;在网络速度和稳定性方面表现良好。因此&#xff0c;使用香港主机搭建游戏网站可以使用户在游戏中的体验流畅且基本不会延迟情况。本文将向用户解释如何使用香港主机搭建游戏网站。在搭建游戏…...

重磅!GitLab 提出五大预测,洞见 2023 年 DevSecOps 发展趋势

本文来源&#xff1a;about.gitlab.com 作者&#xff1a;Sandra Gittlen 译者&#xff1a;极狐(GitLab) 市场部内容团队 2023 年&#xff0c;企业会将更多的时间和资源投入到持续的安全左移上&#xff0c;完成从 DevOps 到 DevSecOps 的演变。 GitLab CMSO Ashley Kramer 表示…...

内核模块(传参和依赖)

目录 一、模块传参 二、模块依赖 三、内核空间和用户空间 四、执行流 五、模块编程与应用编程的比较 六、内核接口头文件查询 七、小作业 一、模块传参 module_param(name,type,perm);//将指定的全局变量设置成模块参数 name:全局变量名 type&#xff1a; 使用符号 …...

基础篇:03-SpringCloud工程部署启动

目录 1.工程搭建部署 方案一&#xff1a;完整工程导入 方案二&#xff1a;从零开始搭建 1.工程与module创建 2.数据库导入 3.项目启动 3.1 启动并访问user-service 3.2 启动并访问order-service 4.服务远程调用 时序图说明 服务远程调用实现 注入RestTemplate Res…...

二、产品经理——【需求收集】【需求管理】

0. 学习目标 能够理解并描述需求能够收集并管理需求 1. 如何定义需求 1.1. 需求的定义 原始需求&#xff1a;没有经过任何分析&#xff0c;或者没有经过任何额外解读的需求信息 避免日后纠纷&#xff0c;尽量记录一下原始需求&#xff01;先记录下来&#xff0c;后面再进行分…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...