一、回溯法概述
回溯法和分枝限界法都是基于搜索的算法，是对枚举法的改进，避免无效的搜索。回溯法实际上是一个类似穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”（即回退），尝试别的路径。 回溯法有“通用解题法”之称。 它适合于解一些组合数较大的最优化问题。
二、问题的解空间
1、解空间概念
一个问题可能解的表示方式和它相应的解释隐含了解空间及其大小。
比如：0/1背包问题
- 可能解的表示为一个向量{x1, x2, …, xn}，其中xi={0,1}
- 则当n=3时，其解空间是：
{ (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) }
关键在于：解空间应该如何组织，才能使用回溯法方便地搜索整个解空间？
2、解空间树(状态空间树，状态空间图)
一个解向量往往对应问题的某个状态，所以解空间又称为问题的状态空间。
解空间的组织：
- 树的根结点位于第1层，表示搜索的初始状态
- 第2层的结点表示对解向量的第1个分量做出选择后到达的状态，第1层到第2层的边上标出对第1个分量选择的结果
- 依此类推，从树的根结点到叶子结点的路径（也可能是根结点到任何一个树中结点，但不含搜索失败的结点），就构成了解空间的一个可能解。
在解空间树中求解可以看成是从初始状态出发搜索目标状态的过程
（1）子集树
（2）排列树
解空间树的特点
- 树中的结点：求解过程的一个状态。
- 树中的边：表示从一个状态转换到另外一个状态的操作，标示 xi 的一个可能的值。
- 问题解：问题的解可以认为是一类特殊的状态，即目标状态。用从根结点到任意（或叶）结点的路径定义解向量。
- 解空间：对于问题的一个实例，所有满足约束条件的解向量就构成该问题实例的解空间。
关键在于：在解空间树中按什么方式搜索？结点如何扩展到下一层的结点，扩展规则是什么？
三、回溯法的设计思想
回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。当搜索至树中的任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界限，也就是判断该结点是否可能包含问题的可行解：
- 如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝；
- 否则，进入以该结点为根的子树，继续按照深度优先策略搜索并进行判断。
注意：
在算法运行时并不需要构造一棵真正的解空间树结构，只需要存储从根结点到当前结点的路径。
回溯算法需要设计合适的剪枝策略，尽量避免不必要的搜索。
常用的剪枝策略包括两大类：
- 约束函数剪枝：根据约束条件，状态空间图中的部分状态可能是不合法的。 因此，在状态空间图中以不合法状态为根的子树是不可能包含可行解的，故其子空间不需要搜索。
- 限界函数剪枝：这种策略一般应用于最优化问题。假设搜索算法当前访问的状态为????，且存在一个判定函数：它能判定以????为根的子树不可能包含最优解， 因此该子树可以剪除而无需搜索。
用约束函数在扩展结点处剪除不满足约束的子树，即剪除不可行解；
用限界函数剪去得不到问题解或最优解的子树。
所以，回溯算法 = 深度优先搜索 + 剪枝策略
比如：
回溯算法定义问题的解空间及解空间结构， 包括以下四个方面：
- 问题的状态表示：一般用k元组表示，即???? = [????1, ????2, ⋯ , ????k]，其中向量的维度，以及每一个分量的值域是状态表示的关键问题；
-
约束条件： X中每一个分量自身的取值约束； 分量之间的取值约束。
注意：约束条件是剪枝策略的基础，需要深入分析和挖掘 - 操作符集合：从一个状态转换到另外一个状态的操作，在解空间树中它构成边集。
- 问题解和解空间：问题的解可以认为是一类特殊的状态，即目标状态。对于问题的一个实例，所有满足约束条件的解向量就构成该问题实例的解空间。
回溯法解题的一般步骤如下：
1、针对所给问题，定义问题的状态表示，确定问题的解空间树；
2、确定结点的扩展搜索规则。
3、以深度优先方式搜索解空间树，并在搜索过程中采用剪枝函数来避免无效搜索。
四、回溯法的算法框架
1、递归回溯 (由于递归算法的形参具有自动回退（回溯）的能力，设计更简便。)
两类典型的解空间树：子集树和排列树
（1）解空间为子集树的递归回溯
（2）解空间为排列树的递归回溯
2、迭代回溯
五、回溯法算法的时空性能
1、时间性能分析
2、空间性能分析