回溯法基本思想_计算机五大算法之四，回溯算法
一、基本思想和策略
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标，但当搜索到某一步时，发现原来选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的算法为回溯法，而满足回溯条件某个状态的点称为"回溯点"。
基本思想：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。搜索至解空间树任一点时，先判断该点是否包含问题的解，如果肯定不包含(剪枝过程)，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯，否则，进入该子树，继续按深度优先策略搜索。
回溯法就是对隐式图的深度优先搜索算法，
为了避免生成那些不可能产生最优解的问题状态，要不断的利用限界函数，来剪枝那些实际上不可能产生最优解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。(回溯法=穷举+剪枝)
二、回溯法一般步骤
1) 针对所给问题，定义问题的解空间
2) 确定易搜索的解空间结构
3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
两个常用的剪枝函数：
1) 约束函数：在扩展结点中剪去不满足约束的子树
2) 限界函数：剪去得不到最优解的子树
三、算法特点总结
回溯法一个显著特征是在搜索过程中动态产生问题的解空间，在任何时间，算法只保存从根结点到当前扩展结点的路径。
四、实际场景
八皇后问题、全排列、0-1 背包、正则表达式匹配等。
8皇后问题
8皇后问题