回溯法
在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。
利用深度优先在空间树中找出满足条件的所有解
剪枝函数
剪枝函数包括两类:
- 约束函数:用于去除不满足条件的
- 限界函数:用于获取最优解
解题框架步骤
也是利用了递归,其实本质上也是一种“在所有情况中遍历出解”的方法
1 | void backtrack(int t) //t表示递归深度,即当前扩展节点在解空间树的深度 |