回溯算法讲解

1. 什么是回溯算法？

定义

回溯算法是一种 系统化搜索解空间的算法。它尝试所有可能的选择，通过递归深度优先搜索的方式生成解。在尝试某条路径时，如果发现这条路径不满足条件，会立即回退（撤销当前选择），尝试其他路径。

本质
  1. 递归 + 搜索：回溯算法以递归为基础，通过每层递归函数管理当前的状态。
  2. 试探和回退：在每一步进行试探性选择，如果发现不满足条件，则撤销选择，回到上一步。
  3. 剪枝优化：通过条件判断提前终止无效路径的探索。

2. 回溯算法的核心框架

回溯算法的核心三要素：

  1. 路径：当前已经做出的选择。
  2. 选择列表：当前可以选择的选项。
  3. 结束条件：到达问题的解要求时，停止递归并保存结果。

在 Java 中，我们通过以下具体方式实现这些三要素：

  • 路径：使用 List 或 StringBuilder 动态存储当前的选择。
  • 选择列表：通过循环遍历未选择的选项，通常使用数组或布尔标记 used[]。
  • 结束条件：在递归函数中添加退出条件，例如路径长度或总计数。
Java 的代码框架
void backtrack(参数列表) {if (满足结束条件) {保存结果;return;}for (每个选择 in 选择列表) {做出选择;backtrack(路径更新后的参数);撤销选择;}
}

3. Java 中的回溯算法实现要点

3.1 路径的实现

路径表示当前递归中已选择的内容。在 Java 中，常用以下数据结构表示：

  • List：适合动态存储对象集合（如组合问题）。
  • StringBuilder：适合字符串拼接（如排列问题）。
  • 数组：当路径大小固定时，数组更高效。

路径更新的核心操作：

  • 加入新选择：调用 add() 或 append()。
  • 撤销选择：调用 remove() 或 deleteCharAt()。
3.2 选择列表的实现

选择列表表示当前可以选择的元素。通常，以下数据结构适合表示选择列表：

  1. 数组：对字符串、数字的排列组合非常常用。
  2. 布尔数组 used[]：用于标记某个元素是否被选择过。
  3. Map 或 Set：当选择空间包含约束或需要高效去重时使用。

实现要点：

  • 每次递归前，遍历选择列表。
  • 通过条件判断跳过已选择的元素。
3.3 结束条件的实现

结束条件是回溯的退出机制，通常包括以下逻辑：

  • 路径长度达到目标长度。
  • 当前选择满足问题的约束。
  • 选择列表为空（对于排列问题）。

4. 示例：全排列问题（Java 回溯架构解析）

问题

给定一个字符串，求其所有排列，例如 "abc"。

完整代码实现
import java.util.ArrayList;
import java.util.List;public class BacktrackExample {public static void main(String[] args) {String input = "abc";List<String> results = permute(input);System.out.println("全排列结果: " + results);}public static List<String> permute(String input) {List<String> results = new ArrayList<>(); // 结果集boolean[] used = new boolean[input.length()]; // 标记数组StringBuilder path = new StringBuilder(); // 路径backtrack(input.toCharArray(), path, used, results); // 开始回溯return results;}private static void backtrack(char[] chars, StringBuilder path, boolean[] used, List<String> results) {// 结束条件：路径长度等于字符数组长度if (path.length() == chars.length) {results.add(path.toString());return;}// 遍历选择列表for (int i = 0; i < chars.length; i++) {if (used[i]) continue; // 跳过已被选择的字符// 做出选择used[i] = true;path.append(chars[i]);// 递归到下一层backtrack(chars, path, used, results);// 撤销选择path.deleteCharAt(path.length() - 1);used[i] = false;}}
}

5. 架构中的关键操作详解

5.1 路径：StringBuilder
  • 每次递归将当前选择加入路径。
  • 使用 path.append(chars[i]) 添加字符。
  • 在撤销时调用 path.deleteCharAt() 回退到上一状态。
5.2 选择列表：boolean[] used
  • used[i] 标记字符 chars[i] 是否已被选择。
  • 在进入下一层递归时标记为 true，在撤销选择时恢复为 false。
used[i] = true;  // 标记为已选择
path.append(chars[i]);  // 加入路径
backtrack(chars, path, used, results);  // 递归
path.deleteCharAt(path.length() - 1);  // 撤销路径
used[i] = false;  // 恢复标记
5.3 结束条件
  • 判断当前路径是否构成完整解。
  • 对于全排列问题，路径长度等于输入字符串长度时结束递归。
if (path.length() == chars.length) {results.add(path.toString()); // 保存结果return;
}

6. 回溯过程的动态解析

输入

字符串 "abc"。

递归过程

回溯算法的递归过程可以表示为一棵树，每个节点是当前路径，每个分支是一个新的选择。

递归树
                ""/       |       \"a"      "b"      "c"/   \     /   \     /   \"ab"  "ac" "ba"  "bc" "ca"  "cb"|      |     |      |     |     |"abc" "acb" "bac"  "bca" "cab" "cba"
动态过程

  1. 初始状态：

    • 路径：""
    • 选择列表：['a', 'b', 'c']

  2. 第一次递归：

    • 路径："a"
    • 选择列表：['b', 'c']

  3. 第二次递归：

    • 路径："ab"
    • 选择列表：['c']

  4. 第三次递归：

    • 路径："abc"
    • 满足结束条件，保存结果。

  5. 回溯：

    • 撤销选择 'c'，路径回到 "ab"，尝试其他选项。

7. 复杂度分析

  • 时间复杂度：
    • 全排列问题有 n! 种可能解，每次需要 O(n) 时间构造路径，复杂度为 O(n * n!)。
  • 空间复杂度：
    • 递归深度为 O(n)，路径和标记数组需要 O(n)。

8.回溯算法处理相同字符的核心问题与解决方法

核心问题

对于字符串 "aabc"，我们希望生成所有不重复的全排列。

如果直接使用回溯算法而不处理重复字符，可能会导致重复排列的结果。例如，aabc 会出现多次。

为什么会产生重复？

假设输入字符串是 "aabc"，两个 'a' 被当作不同的字符，未对其加以区分。回溯算法的递归过程如下：

第一层递归：

  • 选择第一个 'a' 开始： 
    aabc -> "a" (剩余字符: ['a', 'b', 'c'])
继续递归，生成排列 "aabc"。
  • 选择第二个 'a' 开始： 
    aabc -> "a" (剩余字符: ['a', 'b', 'c'])
继续递归，生成重复排列 "aabc"。

两次分支的结果完全相同。

重复的本质：

  • 未对重复字符（如两个 'a'）进行有效区分。
  • 回溯算法对每个字符进行无差别处理，导致多次选择相同字符。
解决思路：去重的核心

为避免重复，我们需要确保相同字符在同一层递归中只被选择一次。

解决方案包括以下两步：

排序字符串：

  • 先对字符串进行排序，使得相同字符相邻。
  • 如 "aabc" -> ['a', 'a', 'b', 'c']。

剪枝：

  • 当递归遍历相邻字符时，如果当前字符与前一个字符相同，且前一个字符尚未被使用，则跳过当前字符。
  • 剪枝条件： 
    if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;
剪枝逻辑解析

剪枝条件：

if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;

含义：

  • chars[i] == chars[i - 1]：
    • 当前字符与前一个字符相同。
  • !used[i - 1]：
    • 前一个字符尚未被使用。
  • 跳过逻辑：
    • 如果当前字符是重复字符，且前一个重复字符在当前层未被使用，说明当前分支已经在前一个字符的选择中被考虑过，应跳过当前字符。
剪枝的效果

  • 避免重复分支：

    • 相邻相同字符在同一层递归中只会被选择一次。

  • 允许在不同位置重复：

    • 相同字符可以出现在不同的排列位置。例如，aabc 中的两个 'a' 可以分别放在首位和中间。

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/17168.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

[刷题]入门3.彩票摇奖

[刷题]入门3.彩票摇奖

博客主页&#xff1a;算法歌者本篇专栏&#xff1a;[刷题]您的支持&#xff0c;是我的创作动力。 文章目录 1、题目2、基础3、思路4、结果 1、题目 链接&#xff1a;洛谷-P2550-彩票摇奖 2、基础 此题目考察数组、三重循环、自增操作的能力。 3、思路 写代码时候&#xf…
阅读更多...
数据在内存中的存储

数据在内存中的存储

1&#xff1a;整数在内存中的存储 在前面我们已经在操作符那一章博客中引入了&#xff0c;原反补的概念。 正整数的原&#xff0c;反&#xff0c;补码相同。 负整数的三种码表示不同。 2&#xff1a;大小端字节序和字符序判断 1&#xff1a;什么是大小端 很明显&#xff0…
阅读更多...
Java线程池：ThreadPoolExecutor原理解析

Java线程池：ThreadPoolExecutor原理解析

一、线程池的基本概念 1.1 线程池的定义 线程池是一组预先创建的线程&#xff0c;这些线程可以重复使用来执行多个任务&#xff0c;避免了频繁创建和销毁线程的开销。线程池的核心思想是通过复用一组工作线程&#xff0c;来处理大量的并发任务&#xff0c;减少系统资源消耗&a…
阅读更多...
从0开始学习机器学习--Day26--聚类算法

从0开始学习机器学习--Day26--聚类算法

无监督学习(Unsupervised learning and introduction) 监督学习问题的样本 无监督学习样本 如图&#xff0c;可以看到两者的区别在于无监督学习的样本是没有标签的&#xff0c;换言之就是无监督学习不会赋予主观上的判断&#xff0c;需要算法自己去探寻区别&#xff0c;第二张…
阅读更多...
网页直播/点播播放器EasyPlayer.js网页web无插件播放器渲染页面出现倒挂的原因排查

网页直播/点播播放器EasyPlayer.js网页web无插件播放器渲染页面出现倒挂的原因排查

EasyPlayer.js网页web无插件播放器属于一款高效、精炼、稳定且免费的流媒体播放器&#xff0c;可支持多种流媒体协议播放&#xff0c;无须安装任何插件&#xff0c;起播快、延迟低、兼容性强&#xff0c;使用非常便捷。 EasyPlayer.js播放器不仅支持H.264与H.265视频编码格式&a…
阅读更多...
P3-3.【结构化程序设计】第三节——知识要点：while语句、do-while语句和for语句

P3-3.【结构化程序设计】第三节——知识要点：while语句、do-while语句和for语句

视频&#xff1a; P3-3.【结构化程序设计】第三节——知识要点&#xff1a;while语句、do-while语句和for语句 知识要点&#xff1a;while语句、do-while语句和for语句 目录 一、任务分析 二、必备知识与理论 三、任务实施 一、任务分析 输出某班若干学生的成绩&#xff0…
阅读更多...
面试时问到软件开发原则，我emo了

面试时问到软件开发原则，我emo了

今天去一个小公司面试&#xff0c;面试官是公司的软件总监&#xff0c;眼镜老花到看笔记本电脑困难&#xff0c;用win7的IE打开leetcode网页半天打不开&#xff0c;公司的wifi连接不上&#xff0c;用自己手机热点&#xff0c;却在笔记本电脑上找不到。还是我用自己的手机做热点…
阅读更多...
【重生之我要苦学C语言】深入理解指针6

【重生之我要苦学C语言】深入理解指针6

深入理解指针6 sizeof和strlen的对比 sizeof 操作符 整型&#xff1a; #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() {int a 10;printf("%zd\n", sizeof(a));printf("%zd\n", sizeof(int));printf("%zd\n", sizeo…
阅读更多...
虚拟展厅赋能线上品牌发布会，打造沉浸式体验

虚拟展厅赋能线上品牌发布会，打造沉浸式体验

线上品牌发布会与虚拟展厅的结合&#xff0c;为企业提供了一个全新的、高效的品牌展示和营销平台。视创云展巧妙融合了3D导览、720全景沉浸体验、虚拟数字人交互、音视频通话以及个性化的互动功能&#xff0c;打造极具沉浸感的线上虚拟品牌发布会&#xff0c;深度赋能体验经济时…
阅读更多...
shell编程（3）脚本参数传递与数学运算

shell编程（3）脚本参数传递与数学运算

声明!!! 学习视频来自B站UP主泷羽sec&#xff0c;如涉及侵权马上删除文章 视频链接&#xff1a;泷羽sec 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 # 向脚本程序传参 脚本如下&#xff1a; echo 执行的文件名…
阅读更多...
CTF-Crypto-affine

CTF-Crypto-affine

首页看描述 一个数学方程和一个flag&#xff0c;应该就是密文构成 y 17x-8 flag{szzyfimhyzd} e一下题目&#xff0c;字典给了一个线索&#xff0c;仿射&#xff0c;那应该就是仿射密码 e一下原理 简单来说&#xff0c;该加密方式&#xff0c;需要两个秘钥来进行加密和解密&a…
阅读更多...
YOLOv8改进，YOLOv8结合DynamicConv（动态卷积），CVPR2024，二次创新C2f结构

YOLOv8改进，YOLOv8结合DynamicConv（动态卷积），CVPR2024，二次创新C2f结构

摘要 大规模视觉预训练显著提高了大规模视觉模型的性能。现有的低 FLOPs 模型无法从大规模预训练中受益。在本文中，作者提出了一种新的设计原则，称为 ParameterNet，旨在通过最小化FLOPs的增加来增加大规模视觉预训练模型中的参数数量。利用 DynamicConv 动态卷积将额外的参…
阅读更多...
【AI数字人整合包及教程】EchoMimic：开启数字人新纪元

【AI数字人整合包及教程】EchoMimic：开启数字人新纪元

在当今数字化转型的浪潮中&#xff0c;人工智能技术正以前所未有的速度重塑我们的生活方式。其中&#xff0c;阿里巴巴旗下蚂蚁集团推出的一款名为EchoMimic的开源AI数字人项目&#xff0c;正在引领一场前所未有的技术革命。本文将深入探讨EchoMimic的技术特点&#xff0c;与其…
阅读更多...
linux逻辑卷练习

linux逻辑卷练习

目录 知识点&#xff1a; 常用命令 题目&#xff1a; 解题&#xff1a; 1&#xff09;分区 2&#xff09;创建物理卷 3&#xff09;创建卷组 4&#xff09;生成逻辑卷 "要带参数 -n" 5&#xff09;扩容 6&#xff09;格式化(添加文件系统) 7&#xff09;挂…
阅读更多...
【MySQL】SQL语言

【MySQL】SQL语言

【MySQL】SQL语言 文章目录 【MySQL】SQL语言前言一、SQL的通用语法二、SQL的分类三、SQLDDLDMLDQLDCL 总结 前言 本篇文章将讲到SQL语言&#xff0c;包括SQL的通用语法,SQL的分类,以及SQL语言的DDL,DML,DQL,DCL。 一、SQL的通用语法 在学习具体的SQL语句之前&#xff0c;先来…
阅读更多...
51单片机基础04 LCD1602时序；Proteus仿真单片机、总线、网络标号等；

51单片机基础04 LCD1602时序；Proteus仿真单片机、总线、网络标号等；

目录 一、LCD显示字符 1、写指令 &#xff08;1&#xff09;、LCD状态配置 &#xff08;2&#xff09;、显示开关与光标 2、写数据 &#xff08;1&#xff09;、设置地址 &#xff08;2&#xff09;、设置数据 3、初始化代码 &#xff08;1&#xff09;、初始化流程 …
阅读更多...
性能优化（二）：ANR

性能优化（二）：ANR

介绍 ANR全称Application Not Responding&#xff0c;意思就是程序未响应。如果一个应用无法响应用户的输入&#xff0c;系统就会弹出一个ANR对话框&#xff0c;用户可以自行选择继续等待亦或者是停止当前程序。 Android系统会监控程序的响应状况&#xff0c;一旦出现下面情况…
阅读更多...
哑光电影人像自拍风景摄影后期Lr调色教程，手机滤镜PS+Lightroom预设下载！

哑光电影人像自拍风景摄影后期Lr调色教程，手机滤镜PS+Lightroom预设下载！

调色教程 哑光电影人像自拍风景摄影后期调色旨在通过 Lightroom 软件为照片营造出一种具有电影质感的哑光效果&#xff0c;同时突出人像与风景的融合之美。 预设信息 调色风格&#xff1a;电影风格预设适合类型&#xff1a;人像&#xff0c;风光&#xff0c;自拍&#xff0c;…
阅读更多...
二五、pxe自动装机

二五、pxe自动装机

pxe自动装机 pxe------------------------------自动安装系统必要的运行环境 无人值守--------------------为系统定制化的安装需要的软件 pxe的优点&#xff1a; 1、规模化&#xff1a;同时装配多台服务器&#xff08;20-30&#xff09; 2、自动化&#xff1a;系统安装和…
阅读更多...
Cadence安装

Cadence安装

记录一下安装过程&#xff0c;方便以后安装使用Cadence。 去吴川斌的博客下载安装包&#xff0c;吴川斌博客&#xff1a; https://www.mr-wu.cn/cadence-orcad-allegro-resource-downloads/ 下载阿狸狗破戒大师 我这边下载的是版本V3.2.6&#xff0c;同样在吴川斌的博客下载安装…
阅读更多...
最新文章

Copyright @ 2022~2023