第5章回溯法.ppt.ppt

回溯算法 一 什么是回溯 回溯 回溯 入口 出口 回溯 迷宫游戏 什么是回溯法 回溯法是一个既带有系统性又带有跳跃性的的搜索算法 回溯法是以深度优先的方式系统地搜索问题的解 它适用于解一些组合数较大的问题 回溯 为什么回溯 回溯 trackback 是什么 怎样回溯 what why how 一 回溯的概念 像走迷宫这样 遇到死路就回头的搜索思路就叫做 回溯 从问题的某种可能情况出发 搜索所有能到达的可能情况 然后以其中一种可能的情况为新的出发点 继续向下探索 当所有可能情况都探索过且都无法到达目标的时候 再回退到上一个出发点 继续探索另一个可能情况 这种不断回头寻找目标的方法称为 回溯法 一 回溯的概念 回溯算法是一种有条不紊的搜索问题答案的方法 是一种能避免不必要搜索的穷举式的搜索算法 其基本思想就是穷举搜索 常用于查找问题的解集或符合某些限制条件的最佳解集 一 回溯的概念 回溯算法常被用来解决自然数排列问题 皇后问题 迷宫问题 数的拆分 0 1背包问题 骑士问题 货船装箱问题和图形覆盖问题等 实例 n皇后问题 在一个n n的棋盘上放置n个国际象棋中的皇后 要求所有的皇后之间都不形成攻击 请你给出所有可能的排布方案数 n皇后问题 对于n皇后问题而言 我们很难找出很合适的方法来快速的得到解 因此 我们只能采取最基本的枚举法来求解 但我们知道 在n n的棋盘上放置n个棋子的所有放置方案有种 而这个数字是非常庞大的 直接枚举肯定会超时 n皇后问题 考虑到皇后攻击的特性 所有的皇后不能同行 同列 那么不妨我们先人为规定第k个皇后在第k行 这样的话我们只要给出每个皇后所处的列号就可以描述皇后的位置了 如图放置方式就可以被表示为 3 1 4 2即第1个皇后在第3列 第2个皇后在第1列 n皇后问题 既然回溯算法是由一个节点开始逐步扩展的 因此我们采用把皇后一个一个的放到棋盘上的方式来分析问题 n皇后问题 首先要把第一个皇后放到棋盘上由于第一个皇后有n列可以放 因此可扩展出n种情况 先选其中一列放下这个皇后 然后开始放第二个皇后 同样第二个皇后也有n列可以放 因此也能扩展出n种情况 但第二个皇后可能会和第一个皇后发生攻击 而一旦发生攻击 就没有必要往下扩展第三个皇后 而如果没有发生攻击 则继续放第三个皇后 依此类推 直到n个皇后全都放下后 即得到一组可行解 扩展全部完成后即可得到结果 n皇后问题 二 回溯的一般描述 可用回溯法求解的问题p 通常要能表达为 对于已知的由n元组 x1 x2 xn 组成的一个状态空间e x1 x2 xn xi si i 1 2 n 给定关于n元组中的一个分量的一个约束集d 要求e中满足d的全部约束条件的所有n元组 其中si是分量xi的定义域 且 si 有限 i 1 2 n 我们称e中满足d的全部约束条件的任一n元组为问题p的一个解 二 回溯的一般描述 解问题p的最朴素的方法就是枚举法 即对e中的所有n元组逐一地检测其是否满足d的全部约束 显然 其计算量是相当大的 二 回溯的一般描述 对于许多问题 所给定的约束集d具有完备性 即i元组 x1 x2 xi 满足d中仅涉及到x1 x2 xi的所有约束意味着j j i 元组 x1 x2 xj 一定也满足d中仅涉及到x1 x2 xj的所有约束 二 回溯的一般描述 一旦某个j元组 x1 x2 xj 违反d中仅涉及x1 x2 xj的一个约束 就可以肯定 以 x1 x2 xj 为前缀的任何n元组 x1 x2 xj xj 1 xn 都不会是问题p的解 三 回溯的一般步骤 回溯法正是针对这类问题 利用这类问题的上述性质而提出来的比枚举法效率更高的算法 n皇后问题的解空间就应该是1 n全排列的一部分 解空间的长度是n 解空间的组织形式是一棵n叉树 一个可行的解就是从根节点到叶子节点的一条路径 控制策略则是当前皇后与前面所有的皇后都不同列和不同对角线 三 回溯的一般步骤 开始节点既是一个活节点又是一个e 节点 expansionnode 扩展节点 从e 节点可移动到一个新节点 如果能从当前的e 节点移动到一个新节点 那么这个新节点将变成一个活节点和新的e 节点 旧的e 节点仍是一个活节点 如果不能移到一个新节点 当前的e 节点就 死 了 即不再是一个活节点 那么便只能返回到最近被考察的活节点 回溯 这个活节点变成了新的e 节点 当我们已经找到了答案或者回溯尽了所有的活节点时 搜索过程结束 实例 跳马问题 在n m棋盘上有一中国象棋中的马 马走日字 马只能往右走 请你找出一条可行路径 使得马可以从棋盘的左下角 1 1 走到右上角 n m 跳马问题 输入 9 5输出 1 1 3 2 5 1 6 3 7 1 8 3 9 5 跳马问题 马走日字 当马一开始在黄点时 它下一步可以到达的点有以下的八个 但由于题目规定了只能往右走的限制 所以它只能走到四个绿色点之一 跳马问题 当马一开始位于左下角的时候 根据规则 它只有两条线路可以选择 另外两条超出棋盘的范围 我们无法预知该走哪条 故任意选择一条 到达a1 a1 a2 跳马问题 当到达a1点后 又有三条线路可以选择 于是再任意选择一条 到达b1 从b1再出发 又有两条线路可以选择 先选一条 到达c1 a a1 a2 b1 b2 b3 c1 c2 跳马问题 从c1出发 可以有三条路径 选择d1 但到了d1以后 我们无路可走且d1也不是最终目标点 因此 选择d1是错误的 我们退回c1重新选择d2 同样d2也是错误的 再回到c1选择d3 d3只可以到e1 但e1也是错误的 返回d3后 没有其他选择 说明d3也是错误的 再回到c1 此时c1不再有其他选择 故c1也是错误的 退回b1 选择c2进行尝试 a a1 a2 b1 b2 b3 c1 c2 d1 d2 d3 e1 跳马问题 从c2出发 有四条路径可以选择 选择d4 从d4出发又有两条路径 选择e1错误 返回d4选择e2 从e2出发有两条路径 先选择f1错误 返回e2选择b 而b恰好是我们要到达的目标点 至此 一条路径查找成功 a a1 a2 b1 b2 b3 c2 e2 b d4 e1 f1 跳马问题 从上面的分析我们可以得知 在无法确定走哪条线路的时候 任选一条线路进行尝试 当从某点出发 所有可能到达的点都不能到达终点时 说明此点是一个死节点 必须回溯到上一个点 并重新选择一条新的线路进行尝试 跳马问题 为了描述路径 我们最直接的方法就是记录路径上所有点的坐标 但比较繁琐 如果我对马可以走到的四个点都编上号 方向 那么我们很容易得到每一个方向上两个坐标和原位置的关系 同时 四个方向都有了编号 那么在选择路径的时候也就可以不采用任选的方式了 只需按照编号依次尝试就可以了 跳马问题 增量数组 dx 1 2 2 1 dy 2 1 1 2 若马所处的位置为 x y 则其下一步可以到达的四个位置分别是 x 1 y 2 x 2 y 1 x 2 y 1 x 1 y 2 在使用增量数组后 只要知道方向t 下一步的位置就是 x dx t y dy t 跳马问题 为了判断棋子是否落在棋盘上 我们还必须知道当前棋子 扩展节点 的位置信息 而用一系列的方向来表示就比较麻烦 因此 我们另外使用两个变量来保存当前棋子的坐标 但这时千万要注意的是一定要在回溯的时候 修改当前棋子的坐标 跳马问题 骑士遍历问题的解空间是从左下角到右上角的所有路径 解空间的长度是所有路径中最长的路径的长度 解空间的组织形式是一棵四叉树 一个可行的解就是从根节点到叶子节点的一条路径 控制策略则是马必须在棋盘内 跳马问题 voidsearch intk 递归查找 for i 1 i0 恢复扩展节点坐标 作业1 对于n m的棋盘 从 1 1 开始是否存在一条不重复的跳完所有棋盘格的路径 若存在请给出该路径的描述 对任意的n m是否总是存在这样一条路径 若不是 能否给出其存在的充要条件 四色问题 四 四色问题 四色问题也称 四色猜想 或 四色定理 它于1852年首先由一位英国大学生f 古色利提出 他在为一张英国地图着色时发现 为了使任意两个具有公共边界的区域颜色不同 似乎只需要四种颜色就够了 但是他证明不了这一猜想 于是写信告诉他的弟弟弗雷德里克 弗雷德里克转而请教他的数学老师 杰出的英国数学家德 摩根 希望帮助给出证明 德 摩根很容易地证明了三种颜色是不够的 至少要四种颜色 下图就表明三种颜色是不够的 但德 摩根未能解决这个问题 就又把这个问题转给了其他数学家 其中包括著名数学家哈密顿 但这个问题当时没有引起数学家的重视 直到1878年 英国数学家凯莱对该问题进行了一番思考后 认为这不是一个可以轻易解决的问题 并于当年在 伦敦数学会文集 上发表了一篇 论地图着色 的文章 才引起了更大的注意 1879年 一位英国律师肯泊在 美国数学杂志 上发表论文 宣布证明了 四色猜想 但十一年后 一位叫希伍德的年轻人指出 肯泊的证明中有严重错误 一个看来简单 且似乎容易说清楚的问题 居然如此困难 这引起了许多数学家的兴趣 体现了该问题的魅力 实际上 对于地图着色来说 各个地区的形状和大小并不重要 重要的是它们的相互位置 下图中的三个地图对地图着色来说都是等价的 从数学上看 问题的实质在于地图的 拓扑结构 合理的退让 不得已而求其次加强命题的条件或者减弱命题的结论 希伍德证明了 五色定理 一百多年来许多数学家对四色问题进行了大量的研究 获得了一系列成果 1920年弗兰克林证明了 对于不超过25个国家的地图 四色猜想是正确的 1926年雷诺兹将国家的数目提高到27个 1936年弗兰克林将国家的数目提高到31个 1968年挪威数学家奥雷证明了 不超过40个国家的地图可以用四种颜色着色 但是 他们都没有最终证明 四色猜想 四色问题的解决 直到1972年 美国依利诺大学的哈肯和阿佩尔在前人给出算法的基础上 开始用计算机进行证明 到1976年6月 他们终于获得成功 他们使用了3台ibm360型超高速电子计算机 耗时1200小时 终于证明了四色猜想 这是一个惊人之举 当这项成果在1977年发表时 当地邮局特地制作了纪念邮戳 四色足够 fourcolorssuffice 加盖在当时的信件上 拓展了人们对 证明 的理解 由于这是第一次用计算机证明数学定理 所以哈肯和阿佩尔的工作 不仅是解决了一个难题 而且从根本上拓展了人们对 证明 的理解 引发了数学家从数学及哲学方面对 证明 的思考 四 应用举例 四色问题 有形如下列图形的地图 图中每一块区域代表一个省份 现请你用红 1 兰 2 黄 3 绿 4 四种颜色给这些省份填上颜色 要求每一省份用一种颜色 且任意两个相邻省份的颜色不能相同 请给出一种符合条件的填色方案 地图用无向图的形式给出 每个省份代表图上的一个顶点 边代表两个省份是相邻的 四色问题 输入70100001101111101010000110100010101001001011100010输出1213134 四色问题 要得到一种可行的填色方案 比较直接的做法就是一个省一个省的填色 在填色的过程中去检查是否和周围省份的颜色存在冲突 从第一个省份开始 对每个省份依次尝试四种颜色 判断当然选择的颜色是否和相邻的省份相同 若都不相同 则将此省份填上当前的颜色 若存在相同 则取下一种颜色继续尝试 若四种颜色都不能填上 则退回上一个省份并选择下一种颜色继续尝试 当最后一个省份也被填色后就找到一组可行解 四色问题 四色问题的解空间是所有的填色方案 解空间的长度是n 解空间的组织形式是一棵四叉树 一个可行的解就是从根节点到叶子节点的一条路径 控制策略则是当前颜色与相邻省份颜色不能相同 作业1 选择中国地图 或者中国某个省的地图 通过回溯算法实现 给出它的一个至多4种颜色的着色方案 分析 设m为图的邻接矩阵 按照涂色的先后顺序将方案存入堆栈s中 其中s k 为区域k的颜色码 区域k为第k个涂色的区域 在计算过程中 我们必须记住当前涂色的区域号i 该区域称之为栈顶 区域准备涂颜色j 1 j 4 首先将区域1涂红色 s 1 1 并准备涂区域2 i 2 从颜色1开始试探 j 1 区域i能否涂颜色j 关键取决于区域i的周边是否有同色区域 搜索已涂色的区域1 区域i 1中与区域i相邻的区域k 看一看这些区域是否涂了颜色j 若与区域i相邻的区域k已经涂了颜色j 按照颜色码递增顺序换一种颜色 j j 1 若区域i的周边没有涂颜色j的区域 则区域i可以涂颜色j s i j 入栈 准备涂区域i 1 也从颜色1开始试探 i i 1 j 1 对区域i 按照颜色码递增顺序试探颜色 如果区域i找不到合适的颜色 j 4 则应该出栈 按照颜色码递增顺序调整区域i 1的颜色 i i 1 j s i 1 如此 从区域1出发 依次类推 直至区域n涂好颜色为止 i n 五 小结与思考 通过前面的分析和讨论 我们可以得到回溯算法的一些特