算法-回溯法
算法框架
在问题的解空间(范围)树(数据结构)中,按深度优先搜索策略,
从根节点出发搜索,算法到任意点时判断包含解,若不包含则跳过回溯,
否则进入子树继续深度优先搜索
解空间:
可行解:满足约束条件、一个解空间子集(八皇后问题)
最优解:目标函数达到极值的可行解(TSP旅行商问题)
- 首先确定求解范围为n元式(X1,X2,X3,…Xn)解向量
- 确定显约束:对分量Xi的取值限定
- 定义解空间(树):满足显约束的所有多元组构成解空间
- 隐约束:不同分量之间的约束
基本思想:确定解空间树后,回溯法从根节点出发,深度优先搜索
深度优先状态生成法:扩展节点:正在产生儿子节点、死节点:儿子节点已经产生、活结点:没有产生全部儿子节点,递归搜索
可解决问题:n皇后、图m着色、迷宫、01背包、子集和、装载
回溯法(试探法):
将问题候选解按某一顺序逐一枚举和试探的过程
可能出现三种情况:
- 回溯:当前候选解不可能是最优或可行的,选择下一个候选解
- 试探:当满足要求仍可扩大范围时
- 解:满足所有要求
回溯类型、剪枝函数
剪枝函数(约束函数、限界函数):减少计算量
剪去得不到最优解的子树
步骤:
- 定义解空间
- 确定解空间结构(一般是树)
- 深度优先搜索,在这个过程剪枝函数避免无效搜索
递归回溯:给定最终条件自动回溯
迭代回溯:
树类型
子集树:找出集合S的满足条件的子集(01背包)O(2n次方)
排列数:TSP问题
区别:子集树每次选择是有顺序的,排列数每次选择都是无序的O(n!)