1.  能举例说明回溯算法思想

2.  能使用回溯法设计算法，进行问题求解

3.  能使用回溯算法分析问题，绘制Raptor流程图、编写Python代码

1、不撞南墙不回头、不见棺材不掉泪。

2、走迷宫之回溯——勇于尝试，每走一步就越靠近胜利一步

（1）概念

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

（2）基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

（3）回溯算法的步骤

①针对所给问题，定义问题的解空间

②确定解空间树

③深度优先方式搜索解空间树

示例1：全排列问题

请输出1~3的全部排列数（数字不重复）

解析：1~3的全排列

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

步骤：

（1）构造n=3的解空间搜索树，其中，第一行全是问号，一个数都没填，第二行有个标记0，表示还没有排列任何数。

（2）当第一位选1时，此时m=1，还剩两个数没有填。这时发现第二个数只能填2或3。

（3）填上2后，又到了下层一个节点，该节点的状态m=2，再扩展下去，第三位只能填3，于是到了最下面的黄色节点。

（4）此时，再想扩展黄色节点时，发现m已经是3了，这表明它是一个最终的节点，无法再扩展了，于是得到了一个排列。

示例2：N皇后问题（以四皇后为例）

在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。以n=4为例。

解析：

根据国际象棋规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，即任何两个皇后不放在同一行或同一列或同一斜线上。

解决方案：按行来摆放棋子，下一行的摆放满足于与上一行的棋子没有冲突，否则就返回上一步走其他的路线，这就是所谓的回溯法。

详细说明：

（1）在第一行有四种可能，选择第一个位置放上皇后

（2）第二行原本可以有四种可能摆放，但是第一第二个已经和第一行的皇后冲突了，因此只剩下第三第四个格子了，先选择第三个格子

（3）接下来是第三行，根据规则可以看出，第三行已经没有位置放了，因为都跟第一第二行的皇后冲突，此时返回到第二行第四个。

（4）继续来到第三行，发现只有第二个满足条件

（5）然后发现第四行已经不能放了，只能继续返回，返回到第一行，开始下一种可能

（6）按照 1-5 的步骤，可以找到下面的其中一种解法

总而言之，回溯法就是开始一路到底，碰到南墙了就返回走另外一条路。4皇后最后的解空间树如下图所示。