第5 章 回溯与分支限界 5.1 内容提要 1.基本概念 解空间 搜索问题的解所在的集合,又称搜索空间.解空间通常可以安排成树结构,常 用解空间有子集树、排列树等. 回溯算法 遵照某种策略搜索解空间从而找出解的过程.常用的搜索策略有深度优 先、宽度优先、规则优先等. 分支限界算法 回溯算法的一种特例.在回溯算法运行过程中,为加快算法的速度,尽 可能多地在解空间中进行剪枝,设立新的约束条件———代价函数和界.当代价函数值小于 (对于最大化问题)界时即进行剪枝,这种回溯算法称为分支限界算法. 代价函数 以搜索树的任何的结点v 开始搜索以v 为根的子树,在这个范围可能得到 可行解,代价函数f (v)表示在该子树中可行解的目标函数值的一个上界(对于最大化 问题). 界函数 函数在搜索树中某结点的函数值是算法搜索到该结点时,已经得到的可行解 的目标函数的最大值. 多米诺性质:P(x1,x2,…,xi+1)为真蕴涵P(x1,x2,…,xi)为真. 2.算法 n 皇后问题的回溯算法 n 皇后问题是指,在n×n 的棋盘上放置n 个皇后,使得任何 两个皇后不能相互攻击,即棋盘的同一行、同一列、主对角线的平行线、副对角线的平行线上 都不能有两个及以上的皇后,给出所有的放置方法.该问题的回溯算法的解空间是一个树 高为n 的n 叉完全正则树,树中第k 层的边表示棋盘中第k 行的皇后位置,搜索策略是深度 优先,在每个结点处检查是否有皇后冲突,若有则回溯,若无则向下分支.若以检查两皇后 是否冲突作为基本运算,该算法的最坏情形复杂性为O(3n×2nn)=O(nn+1). 0-1背包问题的回溯算法 0-1背包问题的描述详见主教材第3章.该问题的回溯算法 的解空间是一个树高为n 的2叉完全正则树,即子集树,树的第k 层中,关联每个顶点的两 条边分别表示第k 个物品放入或不放入背包中(分别标记为1和0),搜索策略是深度优先, 在每个结点处检查放入背包物品重量之和是否大于背包的承载量,若是则回溯,否则向下分 支.若以数的大小比较作为基本运算,则该算法的最坏情形复杂性为O(2n). 算法设计与分析习题解答与学习指导(第3 版) 7 4 货郎问题(TSP)的回溯算法 货郎问题是指,某售货员要到若干城市去推销商品,各城 市之间的距离为已知,他要选定一条从驻地出发经过所有城市最后回到驻地的一条周游路 线,使得总的路程最短.其数学模型是:已知一个带权图完全图(结点代表城市,边代表城市 之间的道路,权代表城市之间的距离,如两个城市之间无直接连接的道路,设其权为∞,所以 权为正数或无穷),求权和最小的一条哈密顿回路.该问题的回溯算法的解空间是一个树高 为n 的排列树,树中关联根结点的第1层的边只有一条,表示该售货员所在的城市编号,第 2层有n-1条边(n 为城市的个数),分别表示下一步要到达的城市编号,第k(k≥2)层中 每个顶点有n-(k-1)条边,分别表示下一步要到达的城市编号.搜索策略是深度优先,在 每个结点处计算所经过的路径的长度.若以数的加法作为基本运算,该算法的最坏情形复 杂性为O((n-1)!). 装载问题的回溯算法 装载问题是指,设有重量分别为wi 的n 个集装箱,将其装上 两艘载重分别为c1 和c2 的轮船,已知Σn i=1 wi ≤c1+c2,问是否存在一种合理的装载方案将 n 个集装箱装上轮船? 该问题的回溯算法的解空间是一个子集树,搜索策略是深度优先,在 每个结点处检查装入的集装箱重量之和是否超过第一艘船的承载量.遍历整个解空间后得 到使得装入第一艘船的集装箱的重量最大.最后检查剩下集装箱的重量之和是否小于第二 条船的承载量,如是则回答“是”,否则回答“否”.若以数的加法作为基本运算,该算法的最 坏情形复杂性为O(2n). 图的m 着色问题 图的m 着色问题是指,给定无向连通图G 和m 种颜色,用这些颜色 给图的顶点着色,每个顶点一种颜色.如果要求G 的每条边的两个顶点是不同颜色,给出所 有可能的着色方案;如果不存在着这样的方案,则回答“No”.该问题的回溯算法的解空间是 一个m 叉完全正则树,搜索策略还是深度优先.若以颜色比较作为基本运算,该算法在最坏 情形下的复杂性为O(nmn). 背包问题的分支限界算法 问题的描述详见主教材第3章.该问题的分支限界算法是 在回溯算法的基础上,定义如下代价函数:结点的代价函数值是:在 中,无论xk+1,…,xn 取何值,为Σn i=1 vixi 的一个上界;界函 数在结点处的函数值是在此结点之前已经找到的方案中,放入背包物品 的最大总价值.若以数的加法作为基本运算,该算法在最坏情形下的复杂性依然为O(2n). 最大团问题的分支限界算法 该问题为求无向图的顶点个数最多的团.该问题的分支 限界算法中的解空间是一棵子集树,代价函数是F=cn +n-k,其中,cn 为目前形成的团的 顶点数(初始为0),k 为目前检索的子集树的结点的层数,即已经检索过的顶点数.以检查 两个结点是否相邻作为基本运算,该算法在最坏情形下的复杂性为O(n2n). 货郎问题(TSP)的分支限界算法 在回溯算法的基础上,定义如下代价函数:L= Σk j=1 cj+ Σij .B lij +lik ,其中,Σk j=1 cj为已选定巡回路线的长度,Σij .B lij +lik 为经过剩余结点回到结点1的 最短距离的一个下界,界函数值为当前得到的最短巡回路线长度.若以数的加法作为基本运 算,该算法在最坏情形下的复杂性依然为O((n-1)!). 回溯与分支限界 圆排列问题的分支限界算法圆排列问题是指,给定 n 个圆,已知每个圆的半径ri.现将 它们放到矩形框中,各圆与矩形底边相切,求具有最小长度ln 的圆排列.该问题的分支限界算 法中的解空间是一个排列树,搜索策略是深度优先,代价函数Lk 为xk +(2n-k+1) 2r+r1, 其中, r 为后面待选的n- k 个圆以及第 k 个圆中最小半径的值,xk 表示第 k 个圆的圆心的 横坐标.界函数在处的值是当前已得到的最小圆排列长度. i2,…, n+1)!) 若以数的加法 作为基本运算,该算法在最坏情形下的复杂性依然为O(( . 连续邮资问题的回溯算法连续邮资问题是指,设有 n 种不同面值的邮票,每个信封 至多贴 m 张邮票,试给出邮票面值的最佳设计(面值为正整数值), 使得到从1开始,增量为 1的连续邮资区间最大.该问题的回溯算法中的解空间并不是算法一开始就能确定下来,需 要边搜索边构造.设在结点处, 2,…,i}, 则xi+1 x2,…,邮资最大连续区间为{ 的取值范围为{xi+1,xi+1+1,…,i+1} 1,r r. 5.习题 2 要求:对于回溯法,要说明解向量、搜索树结构、搜索策略、代价函数(如果存在)等,并 给出最坏情况下的时间复杂度函数.对于给定的数的输入实例,求出所有的可行解(或一个 最优解) . 5.1 用回溯法求下列不等式的所有的整数解.要求给出伪码和解 . 3x1+4x2+2x3≤12 x1,x3 为非负整 数 x2, 5.2 最小重量机器设计问题.某设备需要4种配件,每种1件.有三个供应商提供这些 配件,表5.试从中选择这4种配件, 1给出了相关配件的价格和每种配件的重量 . 使得总价 值不超过120,总重量最轻 . 表5.产品和供应商信息表 1 配件编号 供应商 1 供应商 2 供应商 3 价格重量价格重量价格重量 1 10 5 8 6 12 4 2 20 8 21 10 30 5 3 40 5 42 4 30 10 4 30 20 60 10 45 15 5.如图5.一个4阶Lai在它的每个方格内填入1, 3 1所示, tn方是一个4×4 的方格, 2, 3或4,并使得每个数字在每行、每列都恰好出现一次.用回溯法求出所 有第1行为1,2,3,4的4阶Latin方.将每个解的第2行至第4行的数字 从左到右写成一个序列.例如,图51中的Ln方对应于解<3,1,4,2,2,4,给出所有可能的4 . 阶Lnat 方 i. 4,2,3, 1,1,3> . ati 5.4 应用回溯算法给出{1,3,的所有置换. 2,4} 5.给出8皇后问题的一个广度优先回溯算法,并分析该算法的时图5.1 Latin方 5 第 章 75 76 算法设计与分析习题解答与学习指导(第3版) 间复杂度 . 5.子集和问题 . 求出使得和为某数 M 的 S 的所有子集. 6 设 n 个不同的正数构成集合S, 给 n 个人分配 n 件工作, i, 5.7 分派问题 . 给第 i 个人分配第 j 件工作的成本是C(j) . 试求成本最小的工作分配方案 . 5.电路板排列问题.设B={1,2,…,是 n 块电路板的集合,L={N1,N2,…,Nm } 8 n} 是 m 块连接块的集合.对j=1,2,…,m,连接块 Nj . B 相当于一条导线,把属于Nj 的所有电路 板连起来.如图5.B={1,8}, 其中位 2所示,2,…, 置1,2,…,8是插槽,每个插槽可以插入一块电路 板.当电路板按照某种排列顺序全部插入后,一些 图5.2 电路板问题的实例连接块的导线有可能从一块电路板插槽跨到相邻 的另一个插槽.例如,2中的5块连接块是: 图5. N1={4,5,6}, N2={2,3}, N3={1,3}, N4={3,6}, N5={7,8} 如果电路板按照3,4,6,1,8,那么横跨插槽1和插槽2的连线数是3, 5,7,2的顺序排列, 即 连接块N2,N3 和N4;横跨插槽2和插槽3的连线数是4,即连接块N1,N2,N3 和N4…… 横跨插槽7和插槽8的连线数是1,即连接块N2.其中最大连线数是4,称4是排列X=< 3,4,6,5,1,7,8,2> 的排列密度,记作density(X).对于电路板的不同排列 X 和X' ,其排列 密度值可能是不一样的.电路板问题是指,给定集合 B 和L,求使得排列密度最小的电路板 排列 . (1)对上述电路板问题的实例,求出该实例的最优解 . (2)不遍历搜索树,用数学方法证明你的解是最优的 . 5.9 设有 n 项任务由 k 个可并行操作的机器完成,完成任务 i 所需要的时间是ti,求 一个最佳任务分配方案,使得完成时间(即从时刻0开始计时到最后一台机器停止的时间) 达到最短 . 5.10 在5.假设每个任务有个完成期限Bi, 试求一 9题中, 以及超出期限的罚款数fi. 个最佳任务分配方案,使得完成所有任务的总罚款最少 . 5.哨兵布置问题 . 需要在陈列 11 一个博物馆由排成m×n 个矩形阵列的陈列室组成, 室中设立哨位,每个哨位上的哨兵除了可以监视自己所在陈列室外,还可以监视自己所在陈 列室的上、下、左、右4个陈列室,试给出一个最佳哨位安排方法,使得所有陈列室都在监视 之下,但使用的哨兵最少 . 5.习题解答与分析 3 5.即 1 34 个解 . (0,0),(0,0,2),(0,0,4),(0,0,6), 0,0,1),(0,0,3),(0,0,5),(0, (0,0),(1,0,2),(1,0,4),(2,0,1), 1,0,1),(1,0,3),(1,0,0),(2, (2),(0),(0),(1),(2),(3),(4), 0,2,0,3,1,0,1,0,1,0,1,0,1,0, (0),(1),(2),(0),(0),(1),(2), 1,1,1,1,1,1,1,2,2,0,2,0,2,0, (2,3),(1,2,1),(0,3,1),(0,0) 0,2,0),(1,3,0),(0,4, 回溯与分支限界 第5章 7 7 5.2 按照价格从小到大对配件排序.设解向量为,xi=j 表示第i 号 配件由j 号供应商供货.1≤xj ≤m .结点表示已经选择了前k 号配件的 供应商,正在处理第k+1号配件. 约束条件:选择了下一个配件后总价格不超过120. 代价函数: Σk i=1 wixi + Σn j=k+1 min l=1,2,…,m{wjl} 其中wjl表示第l 个供应商j 号配件的重量. 解:对实例<3,1,2,3>,总重量为31,价值为119. 5.3 有24个Latin方,如图5.3所示. 图5.3 24个Latin方 5.4 解向量为,搜索空间是排列树.有24个置换. 5.5 解向量为,搜索空间是8叉树.在代表部分向量 的结点处,下一步分支条件是xk+1与x1,x2,…,xk 相容(不在同一行、同一列,也不在同一 条斜线上).搜索是按广度优先顺序遍历这棵树.对于n 后问题,最坏情况下的时间复杂度 为O(nn). 5.6 设S={a1,a2,…,an}.求S 满足条件Σai∈A ai =M 的所有的子集A .用回溯算法. 解向量为,xi=0,1.其中xi=1当且仅当ai∈A .搜索空间为子集树.部 分向量表示已经考虑了对a1,a2,…,ak 的选择.结点分支的约束条件是: B(i)=Σk i=1 aixi 解向量是分配成本是搜索空间是排列x,x,…,x, x,=12i. n 12k<>树部分向量表示已经考虑了对人的工作分配结点分支的约x,x,x,…,,…,12k. . ΣΣ({)(){}{}} 2i1∈CiiC|tt+ nm,,,…,x,…,x,nx,x=-21ik B界是已得到的最好可行解的分配成本如果代价函数大于界则回溯,. . (!)O算法最坏情况下的时间复杂度是nn. 58X<><搜索空间为排列树叶结点对应排列结点x,xx,11... n {B><>表示部分排列搜索策略为深度优先在结点令=x,…,xx,x,…,x, x,2121ii. . },:下一步选择其约束条件是x,…,xx2+1ii.(n) ?[]lttj在电路板和之间如何计算横跨插槽和的连线数令是连接oaxx, xx+1 +1 iiii[] Njj是中的电路板数块所连接的电路板总数中已经包含在那么ownx,x,,x,…,12ij [[]1l0Niij的连线跨越位置和的电路板>+.nowoaj ([]); >0Nj中的电路板另一部分连线连接除即的部分连线连接因为ownx,…,x,x21ij ([[l之外的其他电路板owoaxi. 1:di从位置为到的电路板的最大排列密度,i{[],[}1S|jjjnowoaow,m==1i+ {},{},{},{},{}45623133678NNNNN针对本题给出的实例=====,,,,,,,12345. [][][][][]1234150nownownownownow,===== 23NNNN<>因此的连线跨越位置为和的电路板在分支点选择xxx,,,,,…,123412i. :后的估计是x+1 i{}ddS||max,=11iii++ (!)O算法在最坏情况下的时间复杂度是mn. 112295kk个处理器的标号分别为设个任务的标号分别为n,, n ,,…,,…,. . i=1 束条件是 : xk+1∈{1,n}x1,xk } 2,…,-{x2,… , 可以设立代价函数 : Fx1,xk (x2,…,) kn i=1 i=k+1 x2,…,在第 i 层, 2,…,- B 界为目前得到的最小排列密度 . xi+1∈{1,n} j]0,2,… , 如果排列是3,4,6,5,1,7,8,2,当i=2时, 有 total[1]= 3 total[2]=total[3]=total[4]=total[5]= 2 density(X)=dn 算法主要步骤如下: 回溯与分支限界 1.给出将 n 个任务分到 k 个处理器上的分配方法 . 2.在每个分配方法下,算出每个处理器上所分配到的任务的执行时间,并求这些执行 时间的最大值,该最大值即为这个分配方法的执行时间 . 3.求出所有分配方法的执行时间的最小值 . 步骤1可以用深度优先策略遍历如图5. 4所示的 k 元完全正则树实现 . 图5. 4 k 元完全正则树 树的根结点分支出来的 k 个条边分别标记 k 个处理器的标号,表示任务1所分配的处 理器标号;树的第一层每个结点所分支出的 k 条边也分别标记 k 个处理器的标号,表示任务 2所分配的处理器标号,以此类推. i2,…, n >( 从根到叶结点路径上的边的标记序列下,如ik =il,则表明任务 k 和 l 被分配到同一个处理器ik i2,…,, w2,…,, 上执行.遍历序列i1,in 找到每个处理器上分配到的所有任务w1,wu 则在 这个分配方案下,该处理器的执行时间为tw1+tw2+…+twu.再在所有处理器的执行时间 中求出最大值,则该最大值即为分配方案的执行时间 . O(nkn ) . 执行时间是O( n )至此算法结束. 步骤3是在kn 个分配方案的执行时间中求最小值, k. 总的执行时间是O(nkn ) . 2,…,2,…, 5.同上题,设 n 个任务的标号分别为1,n, k 个处理器标号分别为1,k. 10 算法基本步骤如下: 1.如5.给出将 n 个任务分到 k 个处理器上的分配方法. 9题, 2.在每个分配方法下,找到每个处理器上所分配到的任务并计算该分配方法的罚款 . 2.w2,…,用回溯算法计算出以不同 1 设某个处理器上分配到的所有任务是w1,wu , 顺序在该处理器上执行任务w1,w2,…,wu 时,每个任务是否超时以及超时的罚款数,再得 出以该顺序执行这些任务时的总罚款数,最后找到总罚款数最小的执行顺序.该回溯算法 执行过程如下:可行解是w1,w2,…,wu 的一个排列,因此解空间是一棵排列树,与根结点 关联的 u 条边表示从任务w1,w2,…,wu 中选择哪个任务执行;对于第一层每个结点,向下 分解出u-1条边,表示从剩下的u-1任务中选择哪一个执行,以此类推.在某个结点处, 如果从根结点到该结点的路径中边的标号顺序为wi1,wi2,…,wi,则任务wi的执行时间 vv 第 章 79 80 算法设计与分析习题解答与学习指导(第3版) 是twi1+twi2+…+twiv ,若twi1+twi2+…+twiv >Bwi1,则增加罚款fwiv .在每个叶结点处 即能得到在该顺序下执行w1,w2,…,wu 的罚款数.遍历整棵树后计算出所有叶结点的罚 款数,在所有这些罚款数中找到最小值和相应的执行顺序(最优执行顺序), 则最小值即为该 处理器执行w1,w2,…,wu 时罚款的最小值 . 2 将每个处理器罚款的最小值相加,即为该分配方法按最优顺序执行时的罚款值 . 合并每个处理器按上述顺序执行的任务,即可得到针对这个分配方法的解 . 2. 3.比较步骤2针对每个分配方法的罚款值,找到其中最小罚款值所对应任务分配方法 及其在不同处理器上的执行顺序,即可得到该问题的解 . 算法在步骤1的执行时间依然是O( n ); 步骤2的执行时间是O( n ); 步骤3 的执行时间是O( n ). nkn×n!×nk! n ×) n×k k故该算法最坏情形下的时间复杂度是O( 5.11 本题的解是一个 m ×n 的01矩阵X[j],i,=i,当(.) -i,X[j]1当且仅陈列室(j) 有哨兵.初始令所有的X[j]1,1,m,j=2,…,算法从(1) i,=i=2,…,1,n. 1,开始直到 (m,为止, 有m×n 层 . 如果令X[j]= n) 搜索树是二叉树, 每个结点对应一个陈列室位置.i, 0,则取消(j) 进入左子树; 进入右子树 . 需要检查房 i,位置的哨兵, 否则, 在进入左子树时, 间被监视的情况.即当取消(j)位置的哨兵时, 下、左、右位置是否被监视. i,此位置及其上 、 如果有不被监测的情况出现,则该分支不再搜索.最坏情况下的时间复杂度是O(2nm ) . 第6 章 线性规划 6.1 内容提要 1.数学模型与基本概念 线性规划的一般形式 min(max)z =Σn j=1 cjxj 目标函数 s.t.Σn j=1 aijxj ≤ (=,≥)bi, 1≤i ≤m 约束条件 xj ≥0, j ∈J . {1,2,…,n} 非负条件 xj 任意, j ∈ {1,2,…,n}-J 自由变量 满足约束条件和非负条件的x 称作可行解,使z 取到最小值(对于min)或最大值(对于 max)的可行解称作最优解. 线性规划的标准形 minz =Σn j=1 cjxj s.t.Σn j=1 aijxj =bi ≥0, 1≤i ≤m xj ≥0, 1≤j ≤n 标准形的矩阵形式 minz =cTx s.t.Ax =b x ≥0 设A 的秩等于m ,A 的m 个线性无关的列称作基,对应的m 个变量称作基变量,其余 的变量称作非基变量.基变量记作xB ,非基变量记作xN .满足约束条件Ax=0且所有非基 变量都等于0的x 称作基本解,满足非负条件的基本解称作基本可行解,对应的基称作可 行基. 2.标准形的可行解的性质 主要公式 设可行基为B,则对应的基本可行解xB =B-1b,xN =0,简化的目标函数 82 算法设计与分析习题解答与学习指导(第3版) z=z0+λTx 其中,cT1b 是该基本可行解的目标函数值,cT-BB z0=BB-λT=cT1A 是检验数 . 记B-1A=(j)β=B-1 αim×n ,b. 6.1 如果标准形有解,则必有基本可行解 . 6.如果标准形有最优解,则必存在一个基本可行解是最优解. 2 6.设基本可行解为x,对于mix), λj ≤0),1≤j≤ 3 n(ma如果所有检验数λj ≥0( 则 x 是最优解.如果存在λk <0(且所有α则目标函数无界 . n, λk >0), ik ≤0(1≤i≤m), 3. 对偶 性 对偶线性规 划 原始规划(P) 对偶规划(D) maxcTx minbTy s..s.tATy ≥c tAx ≤ b . x ≥ 0 y ≥ 0 6.对偶规划的对偶规划是原始规划. 4 6.设 x 和 y 分别是原始规划(P)和对偶规划(D)的可行解,则恒有 5 cTx ≤bTy 6.设 x 和 y 分别是原始规划(P)和对偶规划(的可行解,如果cTx=bTy,则 6 D) x 和 y 分别是它们的最优解 . 6.如果原始规划(有最优解, D) 且它们的最优值 7 P) 则对偶规划(也有最优解, 相等;反之亦然 . 原始规划和对偶规划的解只有下述3种可能 : (1)原始规划和对偶规划都有最优解,且最优值相等 . (2)原始规划有可行解且目标函数无界,则对偶规划无可行解;对偶规划有可行解且 目标函数无界,则原始规划无可行解 . (3)原始规划和对偶规划都没有可行解 . 6. 8(互补松弛性) 设 x 和 y 分别是原始规划(P)和对偶规划(D)的可行解,则 x 和 y 分别是它们的最优解当且仅当 n bi-Σaijxj yi =0,1≤ i ≤ m j=1 xj Σ(m) aijyi -cj =0,1≤ j ≤ n i=1 4. 算法 单纯形法取初始可行解x.对于mx), 若所有λj ≥0(则 x 是 in(maλj ≤0),1≤j≤n, 最优解,计算结束 . λk >0), ik ≤0(1≤i≤m), 则无最优解 , 否则取λk <0(若所有α计算结束 . 如果存在αlk >0,则做基变换,重复进行 . 两阶段法阶段一引入人工变量构造辅助问题,用单纯形法解辅助问题.若辅助问题 的最优值 w *>0,则原问题无可行解,计算结束.若 w *=0,则删去人工变量得到原问题的 一个可行解,进入阶段二用单纯形法解原问题 .