回溯与搜索初步.ppt

回溯与搜索初步 第一部分　回溯 一、回溯的概念 从问题的某种可能情况出发，搜索所有能到达的可能情况，然后以其中一种可能的情况为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。 一、回溯的概念 回溯算法是一种有条不紊的搜索问题答案的方法，是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。常用于查找问题的解集或符合某些限制条件的最佳解集。 一、回溯的概念 回溯算法常被用来解决自然数排列问题、皇后问题、迷宫问题、数的拆分、0/1背包问题、骑士问题、货船装箱问题和图形覆盖问题等。 下面我们来看一段走迷宫的演示，初步体会一下回溯的思路。 二、回溯的一般描述 二、回溯的一般描述 三、回溯的一般步骤 首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解； 然后我们需要组织解空间，以便它能被容易地搜索。典型的组织方法是图或树。 最后对这个空间即可按深度优先的方法从开始节点进行搜索。 三、回溯的一般步骤 开始节点既是一个活节点又是一个E-节点（expansion node、扩展节点）。 从E-节点可移动到一个新节点。 如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。 如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。 当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。 三、回溯的一般步骤 定义一个解空间，它包含问题的解； 用适于搜索的方式组织该空间； 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。 四、应用举例—n皇后问题 我们在前面已经讨论过n皇后问题，现在我们用回溯的思路来分析一下n皇后问题，看看是否能枚举较少的排布。 我们仍旧规定第k个皇后位于第k行。 既然回溯算法是由一个节点开始扩展的，因此我们现在一个一个的把皇后放到棋盘上。 n皇后问题 首先要把第一个皇后放到棋盘上由于第一个皇后有n列可以放，因此可扩展出n种情况。先选其中一列放下这个皇后； 然后开始放第二个皇后。同样第二个皇后也有n列可以放，因此也能扩展出n种情况，但第二个皇后可能会和第一个皇后发生攻击，而一旦发生攻击，就没有必要往下扩展第三个皇后，而如果没有发生攻击，则继续放第三个皇后； 依此类推，直到n个皇后全都放下后，即得到一组可行解。 扩展全部完成后即可得到结果。 n皇后问题 n皇后问题 n皇后问题的解空间就应该是1～n全排列的一部分。 解空间的长度是n。 解空间的组织形式是一棵n叉树，一个可行的解就是从根节点到叶子节点的一条路径。 控制策略则是当前皇后与前面所有的皇后都不同列和不同对角线。 n皇后问题（边界判定） n皇后问题（递归） n皇后问题（非递归） 四、应用举例—跳马问题 在n×m棋盘上有一中国象棋中的马： 马走日字； 马只能往右走。 请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）。 跳马问题 输入：9 5 输出：(1,1)-(3,2)-(5,1)-(6,3)-(7,1)-(8,3)-(9,5) 跳马问题 马走日字，当马一开始在黄点时，它下一步可以到达的点有以下的八个，但由于题目规定了只能往右走的限制，所以它只能走到四个绿色点之一。 跳马问题 当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。 跳马问题 当到达A1点后，又有三条线路可以选择，于是再任意选择一条，到达B1。 从B1再出发，又有两条线路可以选择，先选一条，到达C1。 跳马问题 从C1出发，可以有三条路径，选择D1。但到了D1以后，我们无路可走且D1也不是最终目标点，因此，选择D1是错误的，我们退回C1重新选择D2。同样D2也是错误的。再回到C1选择D3。D3只可以到E1，但E1也是错误的。返回D3后，没有其他选择，说明D3也是错误的，再回到C1。此时C1不再有其他选择，故C1也是错误的，退回B1，选择C2进行尝试。 跳马问题 从C2出发，有四条路径可以选择，选择D4，从D4出发又有两条路径，选择E1错误，返回D4选择E2，从E2出发有两条路径，先选择F1错误，返回E2选择B，而B恰好是我们要到达的目标点，至此，一条路径查找成功。 跳马问题 从上面的分析我们可以得知： 在无法确定走哪条线路的时候，任选一条线路进行尝试； 当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进