回溯
回溯算法是对树形或者图形结构执行一次深度优先遍历,实际上类似枚举的搜索尝试过程,在遍历的过程中寻找问题的解。
深度优先遍历有个特点:当发现已不满足求解条件时,就返回,尝试别的路径。此时对象类型变量就需要重置成为和之前一样,称为「状态重置」。
许多复杂的,规模较大的问题都可以使用回溯法,有「通用解题方法」的美称。实际上,回溯算法就是暴力搜索算法,它是早期的人工智能里使用的算法,借助计算机强大的计算能力帮助我们找到问题的解。
模版
1 |
|
需要注意的点
- 递归的结束条件,构造解
- 选择列表时,该怎么选择元素, backtrack(路径,选择元素的索引)
- 该怎么撤销
- 循环体的遍历
学习资源
- 回溯算法套路详解 - labuladong 的文章 - 知乎
https://zhuanlan.zhihu.com/p/93530380
回溯问题的特性
探索,尝试,n 种方案
排列,组合,多解 ,比如- 求子集,ip 地址复原,排列组合,n 个数字二叉树生成,n 皇后,图的搜索遍历,
或者是求多少种解决方案的个数
等等,可以观察看问题的求解事多种组合。
高级别的回溯 (未掌握)
- 选择,递归条件都很难构造