算法系列之回溯算法

在计算机科学领域,算法是解决问题的核心。回溯算法作为一种经典的算法设计技巧,以其试错和回退的思想,在解决许多复杂问题时展现出强大的能力。本文将深入探讨回溯算法,包括其核心概念、实现步骤、代码示例以及适用场景,帮助读者更好地理解和应用这一算法。
回溯算法概述
- 回溯算法
回溯算法(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…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...
