开始学习了,希望我可以尽快成功上岸!
一、回溯理论基础
- 什么是回溯法?
回溯法也可以叫做回溯搜索法,它是一种搜索的方式。
回溯是递归的副产品,只要有递归就会有回溯。
- 回溯法的效率
回溯法的本质是穷举,穷举所有可能,然后找出我们想要的答案。如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。
组合无序,排列有序。
-
回溯法模板
回溯三部曲,可以按照如下步骤:
-
回溯函数模板返回值以及参数
-
回溯函数终止条件
-
回溯搜索的遍历过程
回溯函数遍历过程伪代码如下:
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果
}
for循环就是遍历集合区间,可以理解一个节点有多少个孩子,这个for循环就执行多少次。
backtracking这里自己调用自己,实现递归。
大家可以从图中看出for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。
分析完过程,回溯算法模板框架如下:
void backtracking(参数) {if (终止条件) {存放结果;return;}