回溯法

定义：

回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

1、回溯法适用：有许多问题，当需要找出它的解集（全部解）或者要求回答什么解是满足某些约束条件的最优解时，往往要使用回溯法。

2、有组织的穷举式搜索：回溯法的基本做法是搜索或者有的组织穷尽搜索。它能避免搜索所有的可能性。即避免不必要的搜索。这种方法适用于解一些组合数相当大的问题。

3、搜索解空间树：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

为了实现回溯，我们先弄明白以下两个问题：

1）首先应该明确问题的解空间。

2）其次是组织解空间以便它能用以被搜索

回溯法