将解空间看做树形结构，即状态空间树。进行深度优先遍历+跳跃式搜素。不满足约束条件的截枝并且回溯父节点。逐步建立和修改子集树（排列树）的过程--“走不通回头”。
适合求解：组合数较大的问题。1、搜索问题：在搜索空间找一个或全部可行解（n皇后问题、图的m着色问题和装载问题等）
2、组合优化问题找该问题的一个或全部最优解[贪心法（最优子结构和最优亮度标准）、动态规划法（最优子结构）]（背包问题，子集和树问题和货郎问题等）
解空间：
问题候选解的集合，表示为一n元组（x1，x2，...xn）
状态空间树&显式约束
状态空间树：
用树形表示解空间，无需事先生成。
每一个节点对应一个 问题状态。
从根节点到叶节点，每条路径对应一个候选解的n-元组。叶结点叫 解状态。
从根状态到某个解状态的路径代表一个可行解的n-元组，则称该解状态为答案状态。
-
对于组合优化问题时，必须使用目标函数衡量每一个答案结点，从中找出使目标函数取得最优值的最优答案状态。
状态空间树
两类状态空间树：
- 子集树：遍历时间为O（2^n）
- 排列树：遍历时间O（n！）
显式约束
- 规定了每个分量的范围，规定待求解问题的所有可能的候选解，决定状态空间树的规模。（在问题描述中直接获得）
隐式约束&判定函数
隐式约束
- 判定候选解是否可行的条件。
判定函数
- 从隐式约束出发，设计判定函数使当且仅当函数为真时，n-元组是问题实例的满足
隐式约束的一个可行解。（候选解是否可行）
最优解&目标函数
最优解
- 不是唯一的
目标函数 / 代价函数
- 衡量每个可行解的优劣
- 组合优化问题的最优解是使用目标函数取极值（最大、最小）的一个或多个可行解。
部分向量&约束函数
部分解向量
- 每一个结点对应一个部分解向量。
- 每个叶子节点对应一个候选解。
约束函数
- 源自问题的约束条件。
- 结点Y是状态空间树中的一个问题状态，从根结点到Y的一条路径代表正在构造中的k元组，是解的一部分，称为部分向量。关于部分向量的函数Bk（x0,x1,x2...x（k-1））有满足或不确定的为true，没有为false则将子树剪掉。
（排序问题一般不用回溯法求解，用回溯法排列时间复杂度为O（n!）,内排序算法快排归并排序的时间复杂度为O（nlogn）或冒泡排序O（n²））
搜索策略&剪枝函数
搜索策略
- 三类策略
1、深度优先，
2、广度优先，
3、函数优先，宽深结合
但使用1或2的搜索法属于蛮力算法或穷举法，搜索效率较为低下。
剪枝函数
提高搜索效率
1、跳跃式搜索（隐含遍历）、
2、剪去不必要的搜索子树-
两类剪枝函数
1、约束函数- 源自带球解问题的隐式约束条件，即关于部分向量的函数Bk。
- 避免搜索不可能包含答案状态的子树
2、限界函数
对于组合优化问题（搜索问题涉及不到）要找最优解而不是可行解，避免搜索不可能包含最优答案结点的子树。
回溯法VS分支限界法
是否满足多米诺性质
可通过变换变得符合多米诺性质，求解后再换回原式
回溯法的效率估计
方法：蒙特卡洛法（计算搜索树中平均遍历的结点数）
选择路径：
1、从根开始，随机选择一条路径，直到不能分支为止（叶子结点或被截枝的节点[约束函数/限界函数]），即从x1，x2，，依次对xi赋值，每个xi的值是从当时的Si中随机选择，直到向量不能扩张为止。
2、假定搜索树中其他|si|-1个分支与上述随机选出的路径一样，计算搜索树的结点数。
3、重复步骤1、2将结点进行概率平均。
装载问题（组合优化问题）
只需要考虑如何装能使第一艘船装到最满。
用回溯法设计解装载问题的O（2^n）计算时间算法，在某些情况下优于动态规划算法。
0/1背包问题（组合优化问题）
（贪心法、动态规划法、图解法、回溯法）
问题描述：
回溯法运用贪心策略，减小r（i），提高剪枝概率。
算法时间复杂度为O（ 2^(n+1) ）。
n-皇后问题（组合问题）
图m着色问题（组合问题）
对于可着色优化问题经验证明最多四种。
这里我们只考虑着色组合问题
子集和数问题
TSP(旅行商问题，货郎问题)（组合优化极小化）
哈密顿环问题
TSP问题要求为完全图，而哈密顿环没有要求完全图
回溯算法效率的影响因素以及改进途径：
n皇后问题--解空间对称性
影响因素：
1.搜索树的结构：
- 分支情况（分支是否均匀）
- 树的深度（1/3解空间）
- 对称程度 (对称适合裁剪)
2.解的分布： - 在不同子树中，分布多少，是否均匀。
- 分布深度
3.约束条件判断：计算简单
改进途径
1.根据树分支设计改进策略
- 结点少的分支优先
- 解多的分支优先
2.利用搜索树对称性裁剪子树
3.分解为子问题 - 分解时间f（n）=c2^n,组合时间T=O（f（n））
-
如果分解为k个子问题，每个子问题大小为n/k则求解时间为image.png
实际缩短了程序运行的时间，理论上时间复杂度还是原来的2^n
