回溯法

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

回溯法就是对隐式图的深度优先搜索算法

基本思路

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

回溯法 = 穷举 + 剪枝

框架

针对所给问题，定义问题的解空间
确定易于搜索的解空间结构
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

实例

路径是否包含指定字符串问题
机器人的运动范围问题