第5章回溯法.ppt

1 第5章回溯法 2 理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架通过应用范例学习回溯法的设计策略 学习要点 3 回溯算法的基本思想 回溯算法也叫试探法 它是一种利用试探或回溯 Backtracking 的搜索技术求解的方法 回溯算法在问题的解空间中使用一种可以避免不必要搜索的穷举式搜索法 可以系统的搜索一个问题的所有解或任一解 4 回溯法的应用领域广泛 对于许多问题 当需要找出问题的全部解或者找出满足某些约束条件的 最优 解时 往往要使用回溯法 回溯法有 通用的解题法 之称 5 回溯法的搜索方式 通常将问题的解空间组织成树或图的形式 使得回溯法能方便地搜索整个解空间 回溯法在问题的解空间树中 按深度优先策略 或先序遍历 根 左 右顺序 从根结点出发搜索解空间树 注意 这棵解空间树不是遍历前预先建立的 而是隐含在遍历过程中 6 回溯法的搜索方式 为了避免不必要的搜索 算法搜索至解空间树的任意一点时 先判断该结点是否包含问题的解 如果肯定不包含 则跳过对该结点为根的子树的搜索 逐层向其祖先结点回溯 否则 进入该子树 继续按深度优先策略搜索 7 5 1回溯法的算法框架1 问题的解空间 问题的解向量 回溯法希望一个问题的解能够表示成一个n元式 x1 x2 xn 的形式 如 对于有n个可选择物品的0 1背包问题 其解空间由长度为n的0 1向量组成 对于n元式 x1 x2 xn 形式的解 对分量xi的取值约束条件 xi 0or1 8 5 1回溯法的算法框架1 问题的解空间 解空间 对于问题的一个实例 满足约束条件的所有多元组 解向量 构成了该实例的一个解空间 9 5 1回溯法的算法框架1 问题的解空间 0 1背包问题的解空间包含了对变量的所有可能的0 1赋值 向量总数有2n个 如 当n 3时 0 1背包问题的解空间为 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 共23个解向量 10 1 问题的解空间 在此将解空间组织成树的形式 对于n 3时的0 1背包问题 其解空间用一棵完全二叉树表示 如下图 解空间树的第i层到第i 1层边上的标号给出了变量xi的值 从树根到叶的任一路径表示解空间中的一个元素 解向量 例如 从跟结点A到结点K的路径对应于解空间中的元素 1 0 0 11 5 1回溯法的算法框架2 回溯法的基本思想 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间 确定了解空间的组织结构后 回溯法就从开始结点 根结点 出发 以深度优先的方式搜索 动态产生 整个解空间 12 5 1回溯法的算法框架2 回溯法的基本思想 从开始结点 根结点 出发 这个开始结点就成为一个活结点 同时也成为当前的扩展结点 活结点 一个自身已生成但其儿子还没有全部生成的节点称做活结点 扩展结点 一个正在产生儿子的结点称为扩展结点 13 5 1回溯法的算法框架2 回溯法的基本思想 在当前扩展结点处 搜索向纵深方向移至一个新结点 这个新结点就成为一个新的活结点 并成为当前扩展结点 如果在当前扩展结点处不能再向纵深方向移动 则当前扩展结点就成为死结点 死结点 一个所有儿子已经全部产生的结点称做死结点 14 5 1回溯法的算法框架2 回溯法的基本思想 当前扩展结点成为死结点时 应往回移动 回溯 至最近的一个活结点处 并使这个活结点成为当前的扩展结点 回溯法即以这种工作方式递归地在解空间中搜索 直至找到所要求的解 或解空间中已无活结点时终止 15 2 回溯法的基本思想例1 0 1背包 以n 3时的0 1背包为例 考虑如下实例 w 16 15 15 p 45 25 25 c 30 从其解空间树的根结点开始搜索其解空间 开始时 根结点A是唯一的活结点 也是当前扩展结点 在当前扩展结点A处 可纵深移至B或C 16 2 回溯法的基本思想例1 0 1背包 在当前扩展结点A处 可纵深移至B或C 选择先移至B 即选取物品w1 此时 A B均为活结点 B成为当前扩展结点 在B处剩余背包容量是r 30 16 14 获取价值45 从B可纵深移至D或E 先考虑移至D 但现仅有的背包容量容不下物品w2 故移至D导致一个不可行解 而从B移至E不占用背包容量 因而可行 从而我们选择移至E 此时E成为新的扩展结点 17 2 回溯法的基本思想例1 0 1背包 此时 A B和E是活结点 在E处容量仍为14 所得价值仍为45 从E可以移至J和K 移至J会导致一个不可行解 而移向K是可行的 于是移至K K成为新的扩展结点 由于K是一个叶结点 所以我们得到一个可行解 1 0 0 v 45 18 2 回溯法的基本思想例1 0 1背包 由于从K已无法纵深扩展 故K成为一个死结点 所以返回 回溯 至E 离K最近的一个活结点 而E也没有可扩展的结点 也成为了死结点 接下来 再继续回溯 返回至B处 同样B也成为死结点 再返回A 从A可扩展移至C 从A移至C r 30 获取价值0 19 2 回溯法的基本思想例1 0 1背包 从C可移至F或G 令先移至F 则F成为新的扩展结点 此时有活结点A C F 在F有r 30 w2 15 获取价值25 从F向纵深移至L处 有r 0 获取价值25 25 50 L是叶结点 即获得一可行解 又获取了至今最高价值 因此记录该可行解 20 2 回溯法的基本思想例1 0 1背包 L不可扩展 返回F处 按此方式继续搜索 可搜索遍整个解空间 搜索结束后找到的最好解是相应0 1背包问题的最优解 21 2 回溯法的基本思想例2 旅行售货员问题 旅行售货员问题 某售货员要到若干城市去推销商品 已知各城市之间的路程 或旅费 他要选定一条从驻地出发 经过每个城市一次 最后回到驻地的路线 使总的路程最短 或旅费最少 该问题可以用图论的语言来进行形式化描述 22 2 回溯法的基本思想例2 旅行售货员问题 设G V E 是一个带权图 图中各边的费用 权 为一正数 图中一条周游路线是包括V中每个顶点在内的一条回路 其费用就是该路线上所有边的费用总和 所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线 23 2 回溯法的基本思想例2 旅行售货员问题 给定一个有n个顶点的带权图G 旅行售货员问题就是要找出G的费用 权 最小的周游路线 左图是一个4顶点无向带权图 如 顶点序列1 2 4 3 1 1 3 2 4 1和1 4 3 2 1是该图中3条不同的周游路线 24 2 回溯法的基本思想例2 旅行售货员问题 该问题的解空间可以组织成一棵树 树的第i层到第i 1层的边上的标号给出xi的值 城市标号 从树的根结点到任一叶结点的路径定义了图G的一条周游路线 如右图为当n 4时这种树结构的示例 25 2 回溯法的基本思想例2 旅行售货员问题 从根结点A到叶结点L的路径上边的标号组成了一条周游路线1 2 3 4 1 图G的每一条周游路线都恰好对应于解空间树中一条从根到叶的路径 因此 该解空间树中叶子个数为 n 1 即元素2 3 4的全排列个数 26 2 回溯法的基本思想例2 旅行售货员问题 对于图G 用回溯法找最小费用周游路线时 从A出发 搜索至B C F L 在叶子L处记录找到的周游路线1 2 3 4 1 该周游路线费用为59 从L处返回最近活结点F F已无可扩展结点 因此回到C 从C可移至G后又到达M 得到周游路线1 2 4 3 1 费用66 这个费用不比已有路线1 2 3 4 1的费用小 因此舍弃该结点 27 2 回溯法的基本思想例2 旅行售货员问题 算法又依次返回结点G C B 从结点B又可以继续搜索D H N 在N处 相应的周游路线1 3 2 4 1的费用为25 是迄今为止找到的最好的一条周游路线 依次继续搜索遍整个解空间 可找到两条最小费用周游路线 13241和14231 28 2 回溯法的基本思想 在用回溯法搜索解空间树时 通常采用两种策略来避免无效搜索 提高回溯法的搜索效率 a 用约束函数在扩展结点处剪去不满足约束的子树 b 用限界函数剪去得不到最优解的子树 这两类函数统称为剪枝函数 29 2 回溯法的基本思想 如在解0 1背包问题 在有限容量内得到最多价值 的回溯法中 用剪枝函数减去导致不可行解 超出容量限制 的子树 又如 在旅行售货员问题的回溯法中 如果从根结点到当前扩展结点处的部分周游路线的费用已超过当前找到的最少的周游路线费用 则可断定该结点为根的子树中不含最优解 即可减去该子树 约束函数 限界函数 30 2 回溯法的基本思想 运用回溯法解题通常包含以下三个步骤 1 定义问题的解空间 2 确定易于搜索的解空间结构 3 以深度优先方式搜索解空间 并在搜索过程中用剪枝函数避免无效搜索 31 3 递归回溯 由于回溯法对解空间作深度优先搜索 因此 在一般情况下用递归方法实现回溯法 回溯法也是设计递归过程的一种重要方法 voidbacktrack intt 形参t表示递归深度 n是问题规模if t n output x 搜索到一个叶结点elsefor inti f n t i g n t i x t h i if constraint t 其中 形参t表示递归深度 即当前扩展结点在解空间树中的深度 n为解空间树的深度 用来控制递归深度 Output x 对得到的可行解x进行记录或输出处理 f n t g n t 分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号 h i 表示在当前扩展结点处x t 的第i个可选值 函数Constraint t 和Bound t 表示在当前扩展结点处的约束函数和限界函数 Constraint t 为T时 表示当前扩展结点处x 1 t 的取值满足约束条件 否则不满足可减去相应子树 Bound t 为T时 表示当前扩展结点处x 1 t 的取值尚未使目标函数越界 还需Backtrack t 1 对其相应的子树作进一步搜索 否则 可以减去相应的子树 For循环结束后 已搜索遍当前扩展结点所有未搜索过的子树 Backtrack t 执行完毕 返回t 1层执行 对还没测试的x t 1 没搜索过的子树 的值继续搜索 当t 1时 若已测试完x 1 的所有可选值 外层调用就全部结束 32 3 递归回溯 通常情况下 调用一次Backtrack 1 即可完成整个回溯搜索 深度优先方式进行的 过程 特殊问题 如旅行售货员 地点1不参与全排列 因此调用Backtrack 2 即可 33 4 迭代回溯 将回溯法表示为一个非递归迭代过程 voiditerativeBacktrack intt 1 while t 0 if f n t g n t for inti f n t i g n t i x t h i 取第i个可选值if constraint t 返回t 1层 该算法中h f g constraint bound等的含义同递归回溯中的含义 34 4 迭代回溯 该算法描述中 函数Solution t 用来判断在当前扩展结点处是否已经得到了一个可行解 若返回T 表示在当前扩展结点处x 1 t 是问题的一个可行解 此时 由output对可行解x进行记录或输出 否则 x 1 t 还只是问题的一个部分解 还需向纵深方向继续搜索 35 小结 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间 在任何时刻 算法只保存从根结点到当前扩展结点的路径 由x 1 t 保存该路径上边的取值 36 小结 如果解空间树中从根结点到叶结点的最长路径的长度为n 则回溯法所需的计算空间通常为O n 而显式地存储整个解空间则需要O 2n 0 1背包问题 或O n 旅行售货员问题 的内存空间 37 5 子集树与排列树 下面两图是两棵解空间树 也是回溯法解题时常见的两类解空间树 0 1背包问题的解空间树子集树 旅行售货员问题的解空间树排列树 38 5 子集树 当所给问题是从n个元素的集合S中找出满足某种性质的子集时 相应的解空间树称为子集树 例如 n个物品的0 1背包问题所对应的解空间树就是一棵子集树 这种树通常有2n个叶结点 树深为n 1 树结点总数为2n 1 1 遍历子集树的任何算法均需 2n 计算时间 39 5 排列树 当所给问题时确定n个元素满足某种性质的排列时 相应的解空间树称为排列树 排列树通常有n 个叶结点 因此 遍历排列树需要 n 计算时间 如旅行售货员问题的解空间树就是一棵排列树 40 5 子集树 voidbacktrack intt if t n output x elsefor inti 0 i 1 i 0 1两个分支x t i if legal t backtrack t 1 legal t 即剪枝函数 遍历子集树需 2n 计算时间 用回溯法搜索子集树的算法框架 41 5 排列树 voidbacktrack intt if t n output x elsefor inti t i n i swap x t x i if legal t backtrack t 1 swap x t x i 遍历排列树需要 n 计算时间 用回溯法搜索排列树的算法框架 42 5 排列树 在该算法中 注意在调用Backtrack 1 执行回溯搜索之前 要先将变量数组x初始化为单位排列 1 2 3 n 43 5 2装载问题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船 其中集装箱i的重量为wi 且装载问题要求确定是否有一个合理的装载方案可将这批集装箱装上这2艘轮船 如果有 找出一种装载方案 44 5 2装载问题 例如 当n 3 c1 c2 50 w 30 10 40 时 问题有解 1 将集装箱1和2装入第一艘轮船上 而3装入第二艘轮船上 2 将集装箱2和3装入第一艘轮船上 然后将1装入第二艘轮船上 若只将集装箱2装入第一艘轮船上 而1和3就不能都装入第二艘轮船 如果w 30 30 30 则无解 45 5 2装载问题 如果一个给定装载问题有解 则采用下面的策略可得到最优装载方案 1 首先将第一艘轮船尽可能装满 2 将剩余的集装箱装上第二艘轮船 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集 使该子集中集装箱重量之和最接近C1 由此可知 装载问题等价于以下特殊的0 1背包问题 46 5 2装载问题 用回溯法设计解装载问题的O 2n 计算时间算法 在某些情况下该算法优于动态规划算法 47 5 2装载问题 解空间 可行性约束函数 扩展左儿子结点时进行判断 引入cw 表示结点处的当前载重 如第i层结点的载重为 i 1则其左儿子结点的载重为 子集树 48 5 2装载问题 templateclassLoading 定义类LoadingfriendMaxLoading Type Type int int MaxLoading负责类Loading的私有变量的初始化private voidBacktrack inti Backtrack负责计算最优载重量intn 集装箱数目 x 当前解 bestx 当前最优解Type w 集装箱重量数组c 第一艘船的容量cw 当前装载的重量bestw 目前最优装载的重量 49 5 2装载问题 voidLoading Backtrack inti 搜索第i层结点if i n 到达叶结点if cw bestw bestw cw 更新bestx return 搜索子树if cw w i c 左子树x i 1 cw w i backtrack i 1 cw w i x i 0 右子树backtrack i 1 for intj 1 j n j bestx j x j 50 5 2装载问题 调用函数Backtrack 1 实现对整个解空间的回溯搜索 以例说明 例 集装箱个数n 3 第一艘船载重为c1 30 集装箱重量数组w 16 15 15 初始状态 cw 0 bestw 0 i 1 51 5 2装载问题 试画出以上实例的解空间树 n 3 c1 30 w 16 15 15 A B C D E F G H I J K 52 5 2装载问题 引入上界函数 限界函数 用于剪去不含最优解的子树 上界函数 扩展右儿子结点时进行判断 cw r bestwr 剩余集装箱的重量当前扩展结点处于第i层时 r的初始值 53 5 2装载问题 voidbacktrack inti 搜索第i层结点if i n 到达叶结点if cw bestw 更新最优解bestx bestw return r w i 向下一层时将物品i从r中去除if cw w i bestw 搜索右子树x i 0 backtrack i 1 r w i 回到本层时将r还原 54 5 2装载问题 试画出以下实例的解空间树 n 3 c1 30 w 16 15 15 A B C D E F G 55 5 3批处理作业调度 现在有n个作业需要处理 每个作业都是先计算后打印 计算任务由中央处理器完成 打印由打印机完成 问 以什么顺序处理能使这些作业的完成时间和达到最小 56 5 3批处理作业调度 给定n个作业的集合 J1 J2 Jn 每个作业必须先由机器1处理 后由机器2处理 作业Ji需要机器j的处理时间为tji 对于一个确定的作业调度 设Fji是作业i在机器j上完成处理的时间 所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和 57 5 3批处理作业调度 批处理作业调度问题要求对于给定的n个作业 制定最佳作业调度方案 使其完成时间和达到最小 58 5 3批处理作业调度 这3个作业的6种可能的调度方案是 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 它们所相应的完成时间和分别是 19 18 20 21 19 19 最佳调度方案是1 3 2 其完成时间和为18 因此 批处理作业调度的解空间树 排列树 59 5 3批处理作业调度 classFlowshop friendFlow int int int private voidBacktrack inti int M 各作业所需的处理时间 x 当前作业调度 bestx 当前最优作业调度 f2 机器2完成处理时间f1 机器1完成处理时间f 完成时间和bestf 当前最优值n 作业数 60 5 3批处理作业调度 对于实例来说 x 0 1 2 3 M 1 0 2 3 2 M 2 0 1 1 3 f2 0 0 0 0 bestf的初值32767 61 5 3批处理作业调度 voidFlowshop Backtrack inti if i n for intj 1 jf1 f2 i 1 f1 M x j 2 f f2 i if f bestf Swap x i x j Backtrack i 1 Swap x i x j f1 M x j 1 f f2 i else for end 62 5 3批处理作业调度 画出以下实例的解空间树 63 5 5n后问题 n后问题 在n n格的棋盘上放置彼此不受攻击的n个皇后 64 5 5n后问题 按照国际象棋的规则 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子 n后问题等价于在n n格的棋盘上放置n个皇后 任何2个皇后不放在同一行或同一列或同一斜线上 65 5 5n后问题 解向量 x1 x2 xn xi表示皇后i放在棋盘的第xi列显约束 xi 1 2 n隐约束 1 不同列 xi xj2 不处于同一正 反对角线 i j xi xj 另外 n是偶数时才有可行解 n是奇数时无解 66 5 5n后问题 boolQueen Place intk place函数测试皇后互不攻击 for intj 1 jn sum sum为可行方案数elsefor inti 1 i n i x t i if Place t Backtrack t 1 67 5 60 1背包问题 解空间 可行性约束函数 上界函数 r是尚未考虑的剩余物品价值总和 子集树 cp r bestp 68 VoidKnap backtrack inti 搜索第i层结点if i n 到达叶结点bestp cp return if cw w i bestp 搜索右子树 x i 0backtrack i 1 69 5 60 1背包问题 上界函数 templateTypepKnap Bound inti 计算上界Typewcleft c cw 剩余容量Typepb cp 当前价值while i n 70 实例 0 1背包实例 设有四件物品 其重量分别为4 8 6 2 价值分别为8 7 18 5 且背包最大容量为16 问 背包内装入哪些物品可以不超重并且达到最大价值 分别用动态规划法和回溯法 71 解答 W 4 8 6 2 V 8 7 18 5 按单位重量先将物品排序 排序后如下 W 6 2 4 8 V 18 5 8 7 S 3 4 1 2 对应的原物品序号 72 cw 8cp 23 cw 0cp 0 解空间树 W 6 2 4 8 V 18 5 8 7 C 16 A B C D E cw 6cp 18 cw 12cp 31 cw 12cp 31Bestp 31 Bound 3 18 8 7 6 8 31 25 bestp Bound 4 23 7 30 30 bestp 剪枝 Bound 5 cp bestp cw w 4 19 c 剪枝 F 73 cw 0cp 0 解空间树 A B C D E cw 6cp 18 Bound 2 0 5 8 7 20 bestp 剪枝 F cw 6cp 18 G cw 10cp 26 cw w 4 18 16 剪枝 Bound 5 cp bestp 剪枝 Bound 4 18 7 25 bestp 剪枝 W 6 2 4 8 V 18 5 8 7 C 16 74 解空间树 A B C D E F G 从解空间树知最优值为