1 回溯算法

1.1 用回溯算法解决问题的一般步骤

1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解
2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间
3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索

1.1.1 基本思想：能进则进

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
回溯算法实际上一个类似枚举的搜索尝试过程。
主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

1.1.2 八皇后问题

八皇后问题就是回溯算法的典型：
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？

第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。
回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。