回溯策略

回溯法介绍

回溯法，又叫试探法，是一种寻找最优解的暴力搜寻法。但是，由于暴力，回溯法的时\间复杂度较高****，因此在比较一些数字较大的问题时，比如上次我们提到的最短路径问题等，运行时间一般比较长。在回溯法中，深度优先搜索是一种很重要的工具。

回溯法基本思想是：

（1）针对具体问题，定义问题的解空间；

（2）确定易于搜索的解空间结构（数据结构的选择）。

（3）一般以DFS的方式搜索解空间。

（4）在搜索过程中，可以使用剪枝函数等来优化算法。（剪枝函数：用约束函数和限界函数剪去得不到最优解的子树，统称为剪枝函数。）

解空间：顾名思义，就是一个问题的所有解的集合。（但别忘了，这离我们要求的最优解还差很远！）

约束条件：有效解的要求，即题目的要求。

约束函数：减去不满足约束条件的子树的函数

限界函数：去掉得不到最优解的结点的函数

扩展结点：当前正在产生子结点的结点称为扩展结点

回溯搜索的算法

(1) PS（path states）表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。

(2) NPS（new path states）表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展 。

(3) NSS（no solvable states）表：不可解状态集，列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。