-
回溯算法（回溯搜索法）
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯是递归的副产品，只要有递归就会有回溯。
回溯算法，不是一个高效的算法，纯暴力算法，实际上是递归算法的一部分，最多再剪枝⼀下。
回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，穷举过程就是遍历一颗多叉树的过程。
回溯算法能解决几种问题：
1、全排列。给定一个没有重复数字的序列，返回其所有可能的全排列。
2、部分棋盘问题，n皇后问题，解数独等
3、切割。一个字符串有几种切割的方式
4、子集。一个字符串或是N个数的集合里有多少符合条件的子集
5、组合问题。N个数里面按一定规则找出k个数的组合。例如力扣
https://leetcode.cn/problems/4sjJUc/有重复元素集合的组合回溯法：通常被抽象为一个n叉树，横方向是for循环,纵方向递归
- List
- /**
- * 回溯代码框架
- */
- void backtrack(path,chooseList){
- //满足结束条件
- if(isOver){
- result.add(path);
- return;
- }
- for(choose:chooseList){
- //做选择
- backtrack(path,choose);
- //撤销选择
- }
- }
- /**
- *多叉树
- */
- void traceTree(TreeNode root){
- if( root == null){
- return;
- }
- for(TreeNode child: root.children){
- raceTree(child);
- }
- }
回溯法中递归函数参数很难⼀次性确定下来，⼀般先写逻辑，需要什么参数，填什么参数。
-
相关阅读:
纯CSS实现炫酷文本阴影效果
java程序设计项目案例化教程题库及答案
网络安全等级保护2.0详解
KubeEdge SIG AI发布首个分布式协同AI Benchmark调研
申银万国期货通过ZStack Cube信创超融合一体机打造金融信创平台
基于TI DRV8424驱动步进电机实现调速和行程控制
【MySQL系列】 第四章 · 约束
Spring Boot的创建和使用（JavaEE进阶系列2）
基于SpringBoot+Vue的疫苗接种管理系统
电商通用（二）
- 原文地址：https://blog.csdn.net/xiaoxiaovbb/article/details/127940998
- 最新文章
-
园友特惠｜ 1Panel 企业版 & AI 一体机限量放售，最高直降 5100！
C# 内存安全性的重大演进：重新定义 unsafe 关键字
为了随时随地控制 AI Agent，我做了一个 Web Terminal
AAVE V3 v3.7 版本更新：Isolation Mode 被移除，清算流程精度修复
Agent 架构设计与能力构建
从 Responses API 到 Chat Completions：一个模型网关的设计复盘
上位机程序发布打包成安装包---Inno Setup
【EF Core】继承策略——TPT
Solon Server 启动模式深度解析：从 0.3MB 内核到 10+ Server 插件
Agent工厂与A2A网络——AgentMesh设计思路