算法系列之回溯算法

在计算机科学领域,算法是解决问题的核心。回溯算法作为一种经典的算法设计技巧,以其试错和回退的思想,在解决许多复杂问题时展现出强大的能力。本文将深入探讨回溯算法,包括其核心概念、实现步骤、代码示例以及适用场景,帮助读者更好地理解和应用这一算法。
回溯算法概述
- 回溯算法
回溯算法(Backtracking Algorithm)是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,遇到正确解将其记录,直到找到了所有的解或者尝试了所有的可能为止。
- 回溯算法的基本思想
回溯算法的核心思想可以概括为试错和回退:
-
试错: 从问题的初始状态出发,逐步构建候选解,尝试每一种可能的选择。
-
回退: 当发现当前选择无法达到目标状态时,回退到上一步,尝试其他选择,直到找到所有可能的解或确定无解。
- 回溯算法的适用场景
回溯算法通常适用于以下类型的问题:
-
组合问题: 从一组元素中找出所有满足条件的组合,例如子集、排列、组合数等。
-
约束满足问题: 在满足一定约束条件下,寻找所有可能的解,例如八皇后问题、数独等。
-
搜索问题: 在图或树等数据结构中搜索特定路径或目标,例如迷宫问题、图的着色问题等。
回溯算法的实现步骤
- 确定解空间
首先,需要明确问题的解空间,即所有可能的候选解。解空间通常可以用树形结构表示,每个节点代表一个候选解,边代表选择。
- 定义递归函数
使用递归函数来实现回溯算法。递归函数需要包含以下关键步骤:
-
选择: 在当前状态下,选择一个可行的选项。
-
递归: 进入下一层递归,尝试构建更完整的候选解。
-
回退: 如果当前选择无法达到目标状态,则回退到上一步,尝试其他选择。
- 剪枝优化
为了提高算法效率,可以使用剪枝技术,即在递归过程中提前排除不可能达到目标状态的分支,减少不必要的搜索。
Java 实现示例:全排列问题
- 描述:
给出一组数字,返回该组数字的所有排列
例如:
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
(以数字在数组中的位置靠前为优先级,按字典序排列输出。)
数据范围:数字个数 0<n≤6
要求:空间复杂度 O(n!) ,时间复杂度 O(n!)
- 示例:
示例1
输入:[1,2,3]返回值:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例2
输入:[1]返回值:[[1]]
- 分析
我们可以将搜索过程展开成一颗递归树,树中的每个节点代表当前的状态,从根节点开始,通过三轮选择后到达叶子节点,每个节点都对因一个排列。如下图所示:

为了实现每个元素只被选择一次,我们引入了一个boolean的数组来标记当前元素是否已经选择,并基于它实现以下的剪枝操作。如下所示:

- 代码实现
public class Permutations {/*** 回溯法,全排列入口类* @param nums* @return*/public static List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();//递归方法backtrack(result, new ArrayList<>(),new boolean[nums.length], nums);return result;}/*** 回溯法,全排列递归方法* @param result* @param temp* @param selected* @param nums*/private static void backtrack(List<List<Integer>> result, List<Integer> temp, boolean[] selected, int[] nums) {// 如果排列的数组长度为数组长度,则说明已经排列完成,将排列结果添加到结果集if (temp.size() == nums.length) {result.add(new ArrayList<>(temp));return;}// 遍历数组,用数组的每个元素一次进行递归for (int i=0 ; i < nums.length; i++) {//剪枝:如果当前元素已经被使用过,则跳过if (selected[i]) {continue;}//排列的集合中添加当前元素temp.add(nums[i]);//将当前元素标记为已选则selected[i] = true;//递归进行下一轮选择backtrack(result, temp, selected, nums);//回退:撤销之前的选择temp.removeLast();//恢复之前的状态selected[i] = false;}}public static void main(String[] args) {int[] nums = {1,2,3};List<List<Integer>> result = permute(nums);System.out.println(result);}
}
总结
回溯算法是一种强大而灵活的算法设计技巧,适用于解决许多复杂的组合、约束满足和搜索问题。通过系统地构建候选解并在必要时回退,回溯算法能够有效地搜索解空间,找到所有可能的解。在实际应用中,结合剪枝等优化技术,可以进一步提高算法的效率。希望本文能够帮助读者更好地理解和应用回溯算法。
相关文章:
算法系列之回溯算法
在计算机科学领域,算法是解决问题的核心。回溯算法作为一种经典的算法设计技巧,以其试错和回退的思想,在解决许多复杂问题时展现出强大的能力。本文将深入探讨回溯算法,包括其核心概念、实现步骤、代码示例以及适用场景࿰…...
Uniapp 小程序接口封装与使用
深入理解 Uniapp 小程序接口封装与使用 在 Uniapp 小程序开发中,接口请求是获取和交互数据的关键部分。合理地封装接口不仅能提高代码的可维护性,还能增强项目的健壮性。今天,我们就来详细探讨一下如何在 Uniapp 中进行接口封装、引入以及使…...
Harmony开发笔记(未完成)
一、感想 作为一名拥有11年经验的Android开发者,我亲历了Android从高速发展到如今面临“僧多粥少”的过程。技术的世界瞬息万变,没有一种技术能够让人依赖一辈子。去年初,我自学了鸿蒙系统,并顺利通过了鸿蒙官方的初级和高级认。…...
观成科技:海莲花“PerfSpyRAT”木马加密通信分析
1.概述 在2024年9月中旬至10月,东南亚APT组织“海莲花”通过GitHub发布开源安全工具项目,针对网络安全人员发起了定向攻击。通过对相关攻击活动进行分析,可以将其与一些海莲花的样本关联起来。这些样本的通信数据结构与海莲花此前使用的攻击…...
Spring Boot @Async 注解深度指南
Spring Boot Async 注解深度指南 一、核心使用要点 启用异步支持 必须在启动类或配置类添加 EnableAsync,否则异步不生效。 SpringBootApplication EnableAsync public class Application { ... }线程池配置 默认问题:Spring 默认使用 SimpleAsyncTaskEx…...
windows设置暂停更新时长
windows设置暂停更新时长 win11与win10修改注册表操作一致 ,系统界面不同 1.打开注册表 2.在以下路径 \HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings 右键新建 DWORD 32位值,名称为FlightSettingsMaxPauseDays 根据需求填写数…...
Orange 开源项目 - 集成百度智能云-千帆大模型
1 集成百度智能云-千帆大模型 百度智能云-千帆ModelBuilder百度智能云千帆大模型服务与开发平台ModelBuilder(以下简称千帆ModelBuilder)是面向企业开发者的一站式大模型开发及服务运行平台。千帆ModelBuilder不仅提供了包括文心一言底层模型和第三方开源…...
特斯拉 FSD 算法深度剖析:软件层面全解读
一、引言 特斯拉的 FSD(Full Self-Driving)系统作为自动驾驶领域的前沿成果,其软件层面的算法设计至关重要。本文将从软件的角度,深入探讨特斯拉 FSD 所采用的算法,包括感知、规划、控制等多个方面,以期为…...
2025/2/17--2/23学习笔记(week1)_C语言
1 整数的存储 只有整数才有原码,反码,补码,原码取反加一(除了符号位)得到补码。补码的补码会变成原码。 在任何位运算里,都是操作的补码,因为整数在内存里都是以补码存储的 2 移位运算符 移位…...
数据结构:二叉树的数组结构以及堆的实现详解
目录 一.树与二叉树 1.树的概念与相关术语: 2.二叉树: (1)定义: (2)特殊的二叉树: (3)完全二叉树 (4)二叉树的存储结构&#x…...
AWS S3 如何设置公开访问权限?
1.让整个bucket都有公开访问权限 1.1关闭【阻止公共读】 1.2关闭ACL访问控制 1.3打开桶策略 这样桶内所有的图片就能访问了 2.只开放特定文件让其具有访问权限? 2.1关闭【阻止公共读】 如之前的图示 2.2打开ACL控制 2.3单个文件打开公共读...
使用TortoiseGit配合BeyondCompare实现在Git仓库中比对二进制文件
使用TortoiseGit的比对工具可以直接右键,点击选择比对和上一版本的变化差异: 但是TortoiseGit只能支持比对纯文本文件的变化差异,如果尝试比对二进制文件,会提示这不是一个有效的文本文件: BeyondCompare可以比对二进制…...
8、HTTP/1.0和HTTP/1.1的区别【高频】
第一个是 长连接: HTTP/1.0 默认 短连接,(它也可以指定 Connection 首部字段的值为 Keep-Alive实现 长连接)而HTTP/1.1 默认支持 长连接,HTTP/1.1是基于 TCP/IP协议的,创建一个TCP连接是需要经过三次握手的…...
Rk3568驱动开发_开发环境的搭建_1
1、环境说明: 需要用官方的程序包,这个程序需要在虚拟机里编译再将镜像烧录到板子里,本质上是给板子上一套Linux操作系统,镜像是.img文件 Linux操作系统被分成了多个模块,编译好后储存在镜像里,本质上就和…...
Solr中得Core和Collection的作用和关系
Solr中得Core和Collection的作用和关系 一, 总结 在Apache Solr中,Core和Collection 是两个核心概念,他们分别用于单机模式和分布式模式(SolrCloud)中,用于管理和组织数据。 二,Core 定义&am…...
Visual Studio Code 远程开发方法
方法1 共享屏幕远程控制,如 to desk, 向日葵 ,像素太差,放弃 方法2 内网穿透 ssh 第二个方法又很麻烦,尤其是对于 windows 电脑,要使用 ssh 还需要额外安装杂七杂八的东西;并且内网穿透服务提供商提供的…...
如何看到 git 上打 tag 的时间
在 Git 中可以通过以下方法查看标签(tag)的创建时间: 使用 git show 命令: 运行以下命令可以查看某个特定标签的详细信息,包括创建时间: git show 输出中会包含 Tagger 的信息和 Date 字段,显示…...
【HarmonyOS Next】鸿蒙TaskPool和Worker详解 (一)
【HarmonyOS Next】鸿蒙TaskPool和Worker详解 (一) 一、TaskPool和Worker如何实现多线程?各自特点是什么? 在鸿蒙中通过TaskPool和Worker实现多线程并发,两者都基于Actor并发模型实现。 Actor并发模型,每…...
如何设置HTTPOnly和Secure Cookie标志?
设置HttpOnly和Secure标志于Cookie中是增强Web应用安全性的重要措施。这两个标志帮助防止跨站脚本攻击(XSS)和中间人攻击(MitM)。下面是关于如何设置这些标志的具体步骤: 设置方法 在服务器端设置 根据你的服务器端…...
几个api
几个api 原型链 可以阅读此文 Function instanceof Object // true Object instanceof Function // true Object.prototype.isPrototypeOf(Function) // true Function.prototype.isPrototypeOf(Object) // true Object.__proto__ Function.prototype // true Function.pro…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
