回溯法-总览
概念思想
回溯法有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法，它在问题的解空间中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，转而逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍历才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统地搜索问题解的算法称为回溯法，它适用于解组合数较大的问题。
算法框架
知道了什么叫回溯法，了解了回溯法的基本思想之后，我们就可以定义一个通用的回溯法算法框架，使我们更加方便透彻的在程序中实现它。它包含以下几个必要的步骤：
- **定义问题的解空间：**用回溯法解决问题时，应该明确定义问题的解空间。问题的解空间中应该至少包含问题一种（最优）解。
- **确定解空间结构：**确定易于搜索的解空间结构，使得能用回溯法方便地搜索整个解空间 。通常将解空间组织成树或者图的形式。
- **搜索解空间：**以深度优先方式搜索解空间，并在搜索过程中使用剪枝函数，避免无效搜索。剪枝函数的作用是终止当前结点搜索其子树，转而回溯到父节点。