什么是回溯算法
- 回溯法采用试错的思想，它尝试分步的去解决一个问题；
- 在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案；
- 回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确的答案；
- 在尝试了所有可能的分步方法后宣告该问题没有答案；
回溯算法与深度优先遍历密不可分
回溯算法也叫 回溯搜索算法 ，「搜索」的意思是「搜索所有的解」；
回溯算法从初始状态出发，采用 深度优先遍历 的方式，得到问题的 所有 的解；因为采用遍历的方式，所以可以得到所有的解；
回溯法的效率
虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法；
因为回溯的本质是穷举，穷举所有可能，然后选出想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质；
那么既然回溯法并不高效为什么还要用它呢？因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法；
回溯法解决的问题
组合问题：N 个数里面按一定规则找出 k 个数的集合（组合是不强调元素顺序）；
切割问题：一个字符串按一定规则有几种切割方式；
子集问题：一个 N 个数的集合里有多少符合条件的子集；
排列问题：N 个数按一定规则全排列，有几种排列方式（排列是强调元素顺序）；
棋盘问题：N 皇后，解数独等等；
回溯算法模板
void backtracking(参数) {
if (终止条件) {
return; // 存放结果
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
css🌰 相邻兄弟选择器之常用场景
上一篇
评论
