【算法】回溯
2021/8/14 1:05:46
本文主要是介绍【算法】回溯,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
回溯
1.概念
回溯是很经典的一个算法,什么是回溯,回溯其实是一种暴力枚举的方式,为啥都暴力了还是很经典的一种方法呢,其实是因为有些问题我们能暴力出来就不错了,就别要其他自行车了。常见的回溯类问题:组合;排列;切割;子集;棋牌;
其实回溯算法就是常说的DFS,本质上是一种暴力枚举算法;
回溯算法常用于解决的问题:
组合
排列
切割
子集
棋盘:N皇后
2.过程
这是回溯的第一道题,回溯是很经典的一个算法,什么是回溯,回溯其实是一种暴力枚举的方式,为啥都暴力了还是很经典的一种方法呢,其实是因为有些问题我们能暴力出来就不错了,就别要其他自行车了。常见的回溯类问题:组合;排列;切割;子集;棋牌;
比如最经典的排列。从1,2,3,4,5中取3个数组成排列有多少种,我们肯定会解决这种问题,但是程序怎么写呢。想一下我们解决这个问题的过程,我们先选1,然后第二个数可以选2,第三个数可以选3,这是一种答案了,然后呢,换第三个数,第三个数选4,又一种答案,再换,第三个数选5,没得选了,所以以12打头的数都选完了,得到三种答案.然后再换第二个数,第二个数选3,然后第三个数选4,注意是组合问题所以我们不能退往回选2了,不然就重复了。就是这样一种选择方案,一直到第3个数选成了3,得到答案345,就不用往后进行了。
你看,这其实就是一个多叉树啊!每走一步我们都要做出自己的选择,然后在该选择的基础上做下一步选择,直到这个选择达到了题目要求,然后我们放弃我们上一步做的选择,去换另外一种选择试一试。这个换掉我们上一步做的选择就是回溯的过程,也就是“撤销选择”。因为只有把上一步的选择撤销了我们才能够得到新的选择,比如123,只有把3撤销了我们才能去选择4.
这个过程中有递归吗?当然有啊,我们把问题缩小一点,比如123三个数字的全排列,首先1打头,得到123,132,这其实就是1+[2,3]的全排列;递归体现在这里!
回溯和递归相辅相成,前面也说过了这就是一颗树,而树就一定会用到递归。这棵树我们起了一个名字叫做决策树,每走一步都是在做一次选择一次决策,就和我们的人生一样。想象一下回溯、深度优先搜索(DFS),递归,都有一种“不撞南墙不死心" 的意思,而这个南墙就是我们的结束条件。 。
3.模板
解决一个回溯问题,实际上就是一个决策树的遍历过程
主要需要思考三个问题:
- 路径:记录我们做出了的选择(走过的决策树上的路径,我们一般都是在最后的叶子节点上去收集结果);【比如我们选的123,124】;
- 选择列表:当前情况下我们可以做出的选择;【比如在第三步我们可以选3.4.5】
- 结束条件:也就是到达了决策树的底层叶子节点,选择列表为空了,无法再做出别的选择了。【比如我们的树选完了123达到题目中的要求3个元素了,就不能够再做选择了】
回溯算法的模板:
result = [] //结果集 def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) //把已经做出的选择添加到结果集; return //一般的回溯函数返回值都是空; for 选择 in 选择列表: //其实每个题的不同很大程度上体现在选择列表上,要注意这个列表的更新, //比如可能是搜索起点和终点,比如可能是已经达到某个条件,比如可能已经选过了不能再选; 做选择 //把新的选择添加到路径里;路径.add(选择) backtrack(路径, 选择列表) //递归; 撤销选择 //回溯的过程;路径.remove(选择)
核心就是for循环里的递归,在递归之前做选择,在递归之后撤销选择;
在这个过程中还有一点很重要,就是我们其实是在做两种遍历;
- 横向遍历(for):其实就是我们在不停的做着的选择;
- 纵向遍历(递归):其实就是在做完选择后面临的下一轮选择;
其实不同的情境下最大的不同就在于决策列表的更新,比如说搜索起点和终点,比如说是否已经被选过,比如说是否达到某个条件(只要求k个数或者和为目标值);;
4.样例
比如说下面的从4个数中选2个树组合,这就是对应的决策树。
其实每一个节点都是在做着同样的事情,只不过选择列表不一样了,而这也是每道里最大的不一样。
再换个角度去看这决策树:
- 横向遍历(for):从左到右做决策;
- 纵向遍历(递归):在做完决策后开始下一轮决策;
这个样例就是我们的下面这道题目
77. 组合
39. 组合总和
40. 组合总和 II
216. 组合总和 III
46. 全排列
47. 全排列 II
51. N 皇后
5.体会
- 1.只要是涉及到做选择的,尤其是提到的五个类型:组合、排序、分割、子集、棋盘。这种都可以构建一颗决策树,那就都可以用回溯算法去解。解之前先自己把决策树画出来。
- 2.整体上套用模板,最大的不同就在于选择列表的更新,要能够根据题目中的要求来更新选择列表,比如到达某个深度了,比如和为某个值了等等;
- 3.在求和问题中,排序之后加上剪枝是很常见的操作,能够舍弃无关的操作(和已经到达某一值了,因为排过序,其后的值就更大了);
这篇关于【算法】回溯的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)