回溯法

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

回溯法也可以叫做回溯搜索法,它是一种搜索的方式。

回溯是递归的副产品,只要有递归就会有回溯。

所以以下讲解中,回溯函数也就是递归函数,指的都是一个函数。

回溯法的效率

回溯法的性能如何呢,这里要和大家说清楚了,虽然回溯法很难,很不好理解,但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢?

因为没得选,一些问题能暴力搜出来就不错了,撑死了再剪枝一下,还没有更高效的解法。

此时大家应该好奇了,都什么问题,这么牛逼,只能暴力搜索。

回溯法解决的问题回溯法


一般可以解决如下几种问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等


组合是不强调元素顺序的,排列是强调元素顺序。

例如:{1, 2} 和 {2, 1} 在组合上,就是一个集合,因为不强调顺序,而要是排列的话,{1, 2} 和 {2, 1} 就是两个集合了。

记住组合无序,排列有序,就可以了。

理解回溯法


回溯法解决的问题都可以抽象为树形结构,是的,我指的是所有回溯法的问题都可以抽象为树形结构!

因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。

递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

这块可能初学者还不太理解,后面的回溯算法解决的所有题目中,我都会强调这一点并画图举相应的例子,现在有一个印象就行。


回溯算法中函数返回值一般为void。

再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数。


回溯函数终止条件

既然是树形结构,那么我们就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。



回溯函数遍历过程伪代码如下:

for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
    处理节点;
    backtracking(路径,选择列表); // 递归
    回溯,撤销处理结果
}


for循环就是遍历集合区间,可以理解一个节点有多少个孩子,这个for循环就执行多少次。

backtracking这里自己调用自己,实现递归。

大家可以从图中看出for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。

分析完过程,回溯算法模板框架如下:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}
相关文章
|
11月前
|
人工智能 IDE 数据可视化
携手中国科学院青年科学家,我们上线了这款AI科研助手
中国科学院大学他山协会推出AI科研助手「他山科研IDE」,已登陆阿里云云工开物平台及云市场。该工具支持文献检索、数据分析、论文撰写等全流程,助力科研自动化。同期,“Agent for Science”实训营将于12月启动,提供系统课程与前沿讲座,由阿里云提供模型与算力支持,推动AI赋能科研创新。
855 0
|
人工智能 IDE API
AI驱动的开发者工具:打造沉浸式API集成体验
本文介绍了阿里云在过去十年中为开发者提供的API服务演变。内容分为两大部分:一是从零开始使用API的用户旅程,涵盖API的发现、调试与集成;二是回顾阿里云过去十年为开发者提供的服务及发展历程。文中详细描述了API从最初的手写SDK到自动化生成SDK的变化,以及通过API Explorer、IDE插件和AI助手等工具提升开发者体验的过程。这些工具和服务旨在帮助开发者更高效地使用API,减少配置和调试的复杂性,提供一站式的解决方案。
|
存储 缓存 固态存储
优化Elasticsearch 硬件配置
优化Elasticsearch 硬件配置
947 5
|
JSON API 数据格式
亚马逊获取商品评论的API接口
本文详细介绍如何通过亚马逊Product Advertising API(PAAPI)获取商品评论数据,涵盖API配置、认证签名、Python调用示例及响应解析。适用于开发价格比较、口碑分析等应用,强调合规使用与频率限制。
|
存储 人工智能 自然语言处理
无影AgentBay来了!给AI智能体装上“超级大脑”
阿里云在WAIC上发布专为AI Agents打造的“超级大脑”——无影AgentBay。该云端电脑支持多系统切换,集成视觉理解、自然语言控制等多项AI能力,提供高性能算力与企业级安全保障,助力AI开发者高效构建智能应用。
1128 1
无影AgentBay来了!给AI智能体装上“超级大脑”
|
网络协议 网络安全 数据中心
|
人工智能 弹性计算 监控
分布式大模型训练的性能建模与调优
阿里云智能集团弹性计算高级技术专家林立翔分享了分布式大模型训练的性能建模与调优。内容涵盖四大方面:1) 大模型对AI基础设施的性能挑战,强调规模增大带来的显存和算力需求;2) 大模型训练的性能分析和建模,介绍TOP-DOWN和bottom-up方法论及工具;3) 基于建模分析的性能优化,通过案例展示显存预估和流水线失衡优化;4) 宣传阿里云AI基础设施,提供高效算力集群、网络及软件支持,助力大模型训练与推理。
|
Shell Go
Go 语言Air 工具使用入门
在Go开发中,频繁的手动重启应用以加载新代码既耗时又低效。为此,我们引入了Air——一款专为Go项目设计的自动重载工具。Air通过监听文件变化,实现代码更改后的自动编译与运行,极大提升了开发效率。本文将指导你完成Air的安装与配置,包括如何启动Air、忽略临时文件以及理解其工作原理,让Go项目开发更加流畅高效。
580 3
|
前端开发 安全
CSS基础常用属性之颜色(如果想知道CSS的颜色知识点,那么只看这一篇就足够了!)
CSS基础常用属性之颜色(如果想知道CSS的颜色知识点,那么只看这一篇就足够了!)