设计 郑宗汉郑晓明 第8章 分支与限界

第第8 8章章 分支与限界分支与限界 考： 1、分支限界的基本思想2、分支限界的方法3、算法流程4、具体实例，画图5、时间，空间复杂性第第8 8章章 分支与限界分支与限界 用回溯法求解问题时, 寻找第一个可行 解是盲目搜索, 只有在找到一个可行解 之后目标函数的界才有意义这种搜 索是盲目进行的 但从某个e_结点进行搜索时, 先估算目 标函数的界, 再确定是否向下搜索的方 法启发人们去寻求另一种搜索模式, 这 就是分支与限界法1) 在分支结点即e_结点上, 估算沿着其 各个子结点搜索时, 目标函数可能取 得的界;2) 把子结点和目标函数可能取得的界保 存在一张结点表中(优先队列或堆);// 费用矩阵 3) 从优先队列或堆中选取界最大(小)的 e_结点向下搜索, 直到叶结点;8.1 分支与限界法的基本思想 考简答： 1. 基本思想（4） 分支分支限界是先估算目标函数的界，再确定是否继续向下搜索的限界是先估算目标函数的界，再确定是否继续向下搜索的 方法4) 若叶结点的目标函数值是结点表中 的最大(小)值, 则该值为问题的最优 解值, 沿该叶结点到根结点的路径所 确定的解是问题的最优解; 若叶结点的目标函数值不是结点表 中的最大(小)值, 则继续搜索。

这样, 从根结点开始, 每遇到一个e_结点, 就对其各个子结点进行估算, 以此更新结 点表: 丢弃不需要的结点, 加入新结点 再选取界为极值的结点, 重复上述过程随着搜索过程的不断深入, 结点表中 目标函数的值越来越接近问题的解可见, 分支限界法不像回溯法那样盲 目地向前搜索, 也不是遇到死结点才 往回走, 而是根据结点表中不断更新 的信息来调整自己的搜索方向, 有选 择、有目标地向前搜索; 也不像回溯 法那样单纯地沿着父结点一层层地向 上回溯, 而是依据结点表中的信息进 行回溯2. 目标函数界的特性部分解:(x1,…xk); 界: bound(x1,…xk) (1)对最小值问题, 称为下界, 意思是向下 搜索取得的值不会小于这些下界, 即bound(x1)  bound(x1,x2)  …  bound(x1,x2,…,xk-1)  bound(x1,x2,…,xk) (2)对最大值问题, 称为上界, 意思是向下 搜索取得的值不会大于这些上界, 即 bound(x1)  bound(x1,x2)  …  bound(x1,x2,…,xk-1)  bound(x1,x2,…,xk)3. 分支与限界法的两种典型方式设解向量X=(x1,x2,…,xn), 其中 xi的取 值范围为有穷集Si, |Si|=ni,1in。

使用分支与限界法求解具体问题时, 可采用下述两种典型方式:(1)从根结点向下搜索时, 分别估算n1个子 结点的目标函数的值bound(x1), 把它 们保存在结点表中, 并删除根结点在结 点表中的登记项再从结点表中选取下界最小(大)的结点 , 作为下一次搜索的起点该过程一直持续到叶结点, 得到一个可 行解X=(x1,x2,…,xn)若结点表中某结点的下界大于 bound(x1,x2,…,xn), 则删除之2)从根结点向下搜索时, 预先通过某种 方式处理, 从所有子结点中挑选一个 作为一个分支结点, 目标函数值为 bound(x1); 其余子结点的集合作为另 一分支, 目标函数值为bound(x1)再选取界最小(大)的分支结点, 继续上 述处理, 直到得到界最小(大)的叶结点 为止该结点对应的解为问题的最优 解, 相应的解值为最优解值选择方式2时需先解决下述问题: 如何选 择分支? 如何计算目标函数的界？4. 复杂性分析方式1: 每棵子树ni个分支最坏情况下, 结点表空间为O(n1n2…nn-1)若为完 全n叉树, 则T(n)=O(nn); 若为完全二叉 树, 则T(n)=O(2n)··方式2: 每棵子树2个分支。

T(n)=O(2n)8.2.1 费用矩阵的特性及归约引理8.1 令G=(V,E)是一个有向赋权图, l是图G的一条Hamilton回路, c是图G的 费用矩阵, 则回路上的边对应于费用矩 阵中每行每列各一个元素8.2 TSP问题 例如, 5顶点TSP问题的费用矩阵如下 图所示, l=v0v3v1v4v2v0是Hamilton回路, 回路上的边对应于费用矩阵中元素 c03,c31,c14,c42,c20{每行每列各1元素} 25413228 5183126 201671 1051256 2397114321021043定义8.1 费用矩阵c的第i行中每个元素 减去一个正常数lhi, 得到一个新费用矩 阵, 使得新矩阵中第i行的最小元素为0, 该过程称为费用矩阵的行归约lhi称为 行归约常数 费用矩阵c的第j列中每个元素减去一个 正常数chj, 得到一个新费用矩阵, 使得 新矩阵中第j列的最小元素为0, 该过程 称为费用矩阵的列归约chj称为列归 约常数 25 41 32 28 5  18 31 26 20 16  7 1 10 51 25  6 23 9 7 11 4321021043 0 16 7 3 0  13 26 21 19 15  6 0 4 45 19  0 16 2 0 4 lh2=1lh1=5lh0=25lh4=7lh3=62104343210先做行归约，再做列归约ch3=4 0 16 7 3 0  13 26 21 19 15  6 0 4 45 19  0 16 2 0 4 2104343210  0 16 3 3 0  13 22 21 19 15  2 0 4 45 19  0 16 2 0 0 2104343210定义8.2 对费用矩阵c的每一行和每一 列进行行归约和列归约, 得到一个新 费用矩阵, 使得新费用矩阵中每一行 和每一列至少有一个元素为0, 该过程 称为费用矩阵的归约。

所得新费用矩 阵称为费用矩阵c的归约矩阵称为矩阵c的归约常数（行归约，列归约 的和） 归约常数h = (25+5+1+6+7)+4 = 48 25413228 5  183126 2016  7 1 105125  6 23 9 7 11 4321021043 0 16 7 3 0  132621 1915  6 0 4 4519  0 16 2 0 4 2104343210  0 16 3 3 0  132221 1915  2 0 4 4519  0 16 2 0 0 2104343210定理8.1 令G=(V,E)是一个有向赋权图, l 是图Ｇ的一条Hamilton回路, c是图G的 费用矩阵, w(l)是以费用矩阵c计算的回 路l的费用c是c的归约矩阵, 归约常数 为h, w(l)是以归约矩阵c计算的回路l的 费用, 则有: w(l) = w(l) + h 定理8.2 令G=(V,E)是一个有向赋权图, l 是图G的一条最短Hamilton回路, c是图 G的费用矩阵, c是c的归约矩阵, 令c是 图G的费矩阵用, 则 l是图G的一条最 短Hamilton回路。

先求图G的费用矩阵c的归约矩阵, 得到 归约常数h, 再求与归约矩阵对应的图G 的最短Hamilton回路, 则w(l) = w(l) + h可见, 图G的最短Hamilton回路的费用 最少不会少于h因此, h是TSP问题中 根结点X的下界8.2.2 界限的确定和分支的选择 1. 界限的确定 {方式2} 选取沿某一边出发的路径, 作为搜索 的一个分支结点, 称为结点Y; 不沿该 边出发的所有其它路径的集合, 作为 另一分支结点, 称为结点Y下面以5顶点TSP问题的费用矩阵及其 归约矩阵为例, 说明结点Y及结点Y的 下界的确定方法  25 41 32 28 5  18 31 26 20 16  7 1 10 51 25  6 23 9 7 11 4321021043 0 16 3 3 0  1322 21 19 15  2 0 4 4519  0 16 2 0 0 2104343210若选取从v1出发, 沿边(v1,v0)前进, 则该 回路的边包含费用c10由于回路中包 含c的每行每列元素各一个, 故c中第1 行和第0列的所有元素在后面计算中将 不起作用, 可删去。

由于回路中肯定不包含边 (v0,v1), 否则会构成一个小回 路, 故可把边(v0,v1)断开, 即 置c01=得如下4×4矩阵:0 16 3 3 15  2 0 4519  0 2 0 0 32044321 16 3 3 15  2 0 4519  0 2 0 0 32044321继续对降阶后的4×4矩阵进行归约: 16 3 3 15  2 0 4519  0 2 0 0 32044321  13 0 0 13  2 0 4319  0 0 0 0 32044321归约常数为: 3+2=5 初始费用矩阵的归约常数为48 这表明从v1出发, 经边(v1,v0)的回路 费用不会小于48+5 = 53 结点Y下界的确定方法:当搜索深度为m, 并选取(vi,vj) 作为一 个分支结点时, 可按下法确定其下界: (1)删去费用矩阵第i行及第j列所有元 素, 把n-m阶费用矩阵降阶为n-m-1 阶矩阵c; (2)把此后不可能经过的有向边的权 值置为这需要和已选择的有向 边一起考虑, 有以下几种情况:1) vivj不与已选边相连, 置cji为; 2) vivj与已选边连成vivjvkvl, 置cli为; 3) vivj与已选边连成vkvivjvl, 置clk为; 4) vivj与已选边连成vkvlvivj, 置cjk为;(3)对降阶后的矩阵c进行归约, 得 归约常数h。

• 令X表示Y的父结点, 则结点Y的 下界w(Y)可由下式确定: w(Y) = w(X)+h结点Y下界的确定方法: {不降阶}(1) 因Y是沿其它边(非vivj边)向下搜索 的分支结点, 该分支对应的回路中不 包含边vivj, 故可以把Y结点相应的费 用矩阵中的cij置为 (2)该分支对应的回路中必包含第i行的 某个元素及第j列的某个元素令dij 表示第i行中除cij外的最小元素与第j 列中除cij外的最小元素之和, 即(3)结点Y的下界: w(Y) = w(X)+dij 25 41 32 28 5 18 31 26 20 16 71 10 51 25 6 23 97 11 4321021043 0 16 3 3 0  13 22 21 19 15  2 0 4 45 19  0 16 2 0 0 2104343210考虑上述5顶点TSP问题:归约常数h=48, 根结点w(X)=48 从v1出发, 选择非(v1,v0)边向下搜索, 则 Y的下界: w(Y)=w(X)+dij=65(1)沿cij=0的方向选择, 使所选择的路 线尽可能短; (2)沿dij最大的方向选择, 使w(Y)尽可 能大。

2. 分支的选择归约矩阵c中每行每列至少包含一个0 元素于是, 选择分支的基本方法:令S是归约矩阵中cij=0的元素集合, dkl是S中使dij最大的元素, 即dkl=maxS{dij} 则边(vk,vl)为所选择的分支方向注: dij为第i行除cij外的最小元素与 第j列除cij外的最小元素之和考虑上述5顶点TSP问题, 其归约矩阵如右所示: 0 16 3 3 0  13 22 21 19 15  2 0 4 45 19  0 16 2 0 0 2104343210dij最大的元素为d10=17, 由此确定所选 择的方向为v1v0, 建立分支结点Y和Y: w(Y)。