回溯法
一种通过探索所有可能的候选解来找出所有的解的算法。 如果候选解被确认不是一个解（或者至少不是最后一个解）， 回溯算法会通过在上一步进行一些变化抛弃该解， 即回溯并且再次尝试。
回溯算法实际上一个类似枚举的搜索尝试过程， 主要是在搜索尝试过程中寻找问题的解， 当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯法是一种选优搜索法， 按选优条件向前搜索， 以达到目标。但当探索到某一步时， 发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法， 而满足回溯条件的某个状态的点称为“回溯点”
步骤
- 针对所给问题, 定义问题的解空间, 它至少包含问题的一个(最优)解
- 确定易于搜索的解空间结构, 使得能用回溯法方便地搜索整个解空间
- 以深度优先的方式搜索解空间, 并且在搜索过程中用剪枝函数避免无效搜索
确定了解空间的组织结构后, 回溯法就从开始节点(根节点)出发, 以深度优先的方式搜索整个解空间. 这个开始节点就称为了一个活结点, 同时也成为当前的扩展节点. 在当前的扩展节点处, 搜索向纵向移至一个新结点. 这个新结点就成为了一个新的活结点, 并成为当前扩展结点. 如果在当前的扩展结点处不能再向纵深方向移动, 则当前扩展结点就成为死结点. 此时, 应往回移动(回溯)至最近的一个活结点处, 并使这个活结点成为当前的扩展结点. 回溯法即以这种方式递归地再解空间中搜索, 直至找到所要求的解活解空间中已没有活结点时为止
基本思想
从一条路先前走, 能进则进, 不能进则退回来, 换一条路再试.