回溯法介绍

回溯法介绍

一、回溯法

1. 定义

有一类问题，我们不知道它明确的计算法则。而是先进行试探，试探到最终状况，发现不满足问题的要求，则回溯到上一个状态继续试探。这种不断试探和回溯的思想，称为回溯法（Back Track Method）
回溯法是在包含问题的所有可能解的解空间树中，从根结点出发，按照深度优先的策略进行搜索，对于解空间树的某个结点，若满足约束条件，则进入该子树继续搜索，否则将以该结点为根结点的子树进行剪枝。
此类问题包括：求最优解、一组解、全部解。例如八皇后问题

举个小例子
我们肯定都玩过迷宫游戏吧，比较复杂的迷宫，肯定是不可能第一遍就直接过了，只能一步一步地进行尝试。当走到一个死胡同时，只能退回到上一个分岔口进行重新选择。数独游戏也是这样的，对于一个不确定的方格，我们就会先将这个方格可能出现的问题记录下来，一个一个地尝试，直到得到正确解。有着“通用解”称呼所以，回溯算法就是类似于枚举的算法，将这一步的所以可能性一个一个地进行尝试。上边迷宫中的分岔口和数独中的可能出现多个数字的方格就是“回溯点”

2. 回溯的算法思想

一直往下走，然后再一步步往回走。
面对一个问题，每一步有多种做法。先做其中一个做法，然后再此基础上一直做下去，把这个做法的所有可能全部做完，再回来，做第二种做法。

3. 回溯法实质

它的求解过程实质上是先序遍历一棵“状态树”的过程。只不过，这棵树不是遍历前预先建立的，而是隐含在遍历过程中。如果认识到这点，很多问题的递归过程设计也就迎刃而解了。

4. 例子

深度优先搜索
求一个序列的幂集
八皇后问题
涂色问题

二、回溯与递归的区别

回溯这个算法思想可以由递归这个算法结构来实现