算法设计与分析-6分支限界法

第6章分支限界法,分支限界法原理与算法框架分支限界法vs回溯法应用范例（1）旅行商问题（2）单源最短路径问题（3）0-1背包问题应用范例（略）（4）多段图最短路径（5）装载问题（6）批处理作业调度问题,6.1分支限界法原理,与回溯法类似，一种基于解空间搜索的问题求解策略回溯法原理：1）利用某种数据结构解向量，形式化地表示问题解e.g.n个城市旅行商问题(TSP)解向量表示为长度为n的向量x1:n=2）问题的各种解组成了问题解空间最优解、次优解/可行解、错误/不可行解、部分解,3）问题解应满足各种约束约束，包括:显约束：对解空间中分量xi的取值限定e.g.TSPxi1,2,3,n隐约束：为满足问题的解而对不同分量之间施加的约束e.g.TSP，各个城市只能遍历一次4）解空间中各个解根据相互间关系和解的构造顺序，组成解空间树,e.g.4个城市的旅行商问题,1）非叶结点对应部分解2）叶节点对应最优解、可行解,5）对解空间中的解，引入定量指标，作为优化依据e.g.旅行商问题：旅游路径总长最短6）问题求解过程带有回溯的深度优先树搜索以深度优先的方式，从树根结点开始，依次扩展树结点，直到达到叶结点搜索过程中动态产生解空间深度优先目的：尽可能快地获得可行解,扩展过程中，碰到可行非叶结点（部分解），可进一步扩展e.g.结点C对应部分解可进一步扩展为:F=G=,碰到不可行非叶/叶结点（不可行（部分）解），需要返回到上一层结点回溯e.g.对C结点，下一步的扩展有4种可能选择：3、4、1、2，每种选择都可以继续扩展子树；但只有其中2种选择是合理的，对后2种选择不再继续扩展，而是返回C结点,4,7）为了提高搜索效率，用剪枝函数（面向具体问题）避免无效搜索，即避免不可行解对应的子树或结点e.g.剪枝条件/约束1：如果当前正在考虑的顶点j与当前路径中的末端结点i没有边相连，即wi,j=,则不必搜索j所在分支E.g.当前已有的部分路径为,路径末端结点为2,下一步可考虑将顶点3、4加入到部分路径中。但是，顶点2与4间无边，w(2,4)=,因此在解空间树中，可以不必考虑顶点4所在分支,剪枝条件2：假设：已经知道直到第i-1层的部分解,从第i-1层结点选择顶点xi，并向该分支往下搜索的界限函数为：B(i)=cw(i-1)+w(xi-1,xi)由此得到剪枝/约束条件2：如果B(i)bestw,则停止搜索xi分支及其下面的层，其中，bestw代表到目前为止,在前面的搜索中，从其它已经搜索过的路径中，找到的最佳回路的权和（总长度）,分支限界法（branchandbound）原理：1）按宽度优先策略遍历解空间树。2）在遍历过程中，对处理的每个结点vi，根据界限函数，估计沿该结点向下搜索所可能达到的完全解的目标函数的可能取值范围界限bound(vi)=downi,upi3）从中选择使目标函数取的极值（最大、最小）的结点优先进行宽度优先搜索，从而不断调整搜索方向，尽快找到问题解关键：各结点的界限函数bound(vi)=downi,upi,依据具体问题而定e.g.4个城市的TSP搜索树中的界限函数,bound(G),bound(D),bound(E),子树,子树,子树,一、与回溯法类似，解向量、解空间、解空间树二、解空间树中的结点分为4种类型活结点，死结点，扩展结点，待处理结点,扩展结点,未处理结点,活结点当前满足约束条件、未来有可能产生最优解的结点；对应部分解,e.g.结点G、D、E所有活结点组成活结点表ANT(AliveNodeTable),扩展结点从活结点表ANT中取出来，当前准备进行扩展的结点，即当前进行处理的结点1）评估每个活结点价值，按照价值最大化/最小化原则，从ANT中选取扩展结点e_node2）e_node扩展方式：宽度优先，生成e_node的全部子节点；评估这些子节点，满足界限约束、有可能产生更优解的结点被作为活结点，加入ANT；不满足约束、或无法产生最优解的子节点被舍弃剪枝3）e_node结点被扩展后，该结点转换为死结点，以后将不会被再搜索活结点扩展结点死结点,e.g.如下图i)从上图中的3个活结点G、D、E中，选择价值最大的结点D，作为扩展结点,ii)生成D的全部2个子结点H、I，经评估后，作为活结点加入ADT表中iii)D变为死结点,B,C,F,E,L,2,3,4,4,A,1,4,G,3,第1步,第2步,第3步,第4步,H,I,D,2,4,死结点：1）已经处理过（搜索过）、不再处理的结点;e.g.A,B,C,F,L2）不满足约束条件、无法产生最优解的结点.e.g.结点G,对应部分解,而w(4,3)=,未处理结点解空间树中位于活结点之下，还没有被搜索/处理到、不属于上述三类结点的其它结点在后续的搜索过程中，通过结点扩展会逐步生成,三、解空间树的扩展选定扩展结点e_node，生成其全部子结点采取宽度优先进行扩展e.g.结点D对应于，考察它的2个子结点和,四、对扩展结点e_node，生成其全部儿子结点后，判断评估每个儿子结点：i)是否满足约束条件。如不满足，则作为死结点ii）估算沿着儿子结点向下搜索时，目标函数可能取得的“界”，即沿着儿子结点向下构造出的最终解可能取得的目标函数的范围；-极大化目标，估计子节点目标函数上界-极小化目标，估计子节点目标函数下界iii）将全部活结点组织在活结点表ANT中利用活结点的“界”值，对活结点进行价值评估是否有可能得到最优解？关键：目标函数界限函数！,五、扩展结点e_node选取扩展树时，需要从活结点表ANT中选取合适的活结点，将其转化为扩展结点e_node1)对最小化问题（如TSP），选取具有最小“界”的活结点e.g.前图中，部分解D的最小界：经过D的最短路径长度至少（下界）是多少2)对最大化问题（如背包问题），选取具有最大“界”的活结点，物品装入方案的最大价值e.g.3)当到达1个叶结点时，得到1个可行解，该可行解对应的最优值bound(x1,x2,xn)可作为当前最优解的1个“界”,六、结点界限函数及剪枝进行结点/树扩展时，利用界限函数估计每个结点可能达到的最优解，进行剪枝1)估计e_node的每个儿子结点ci的“界”bound(ci)-极大化目标，估计子结点目标函数上界-极小化目标，估计子结点目标函数下界2)比较bound(ci)与活结点表ANT中现有活结点*的最优界限值bound(*)对最小化问题，e.g.最短路径，如果bound(ci)bound(*)，沿ci搜索得到可行解不可能小于目前已经得到的最优解，则结点ci不应加入活结点表剪枝，不考虑该结点,e.g.已知的路径总和=20；结点G对应如果路径1-2-4的总长=21，则结点G被舍弃对最大化问题，e.g.背包问题，如果bound(ci)=down），将x加入ANT表/*对最大化问题，要求沿x分支搜索到的完全解的目标值（上界）估计必须大于现有已知的目标函数的下界down,循环，直到某个叶结点的目标函数值在表ANT中最大/*找到1个具有最大值的完全解4.1从表ANT中选择bound(vi)值最大的结点vi，扩展其子结点/*从活结点表中，选择1个具有最大可能目标值的扩展结点vi4.2对结点vi的每个子结点c，执行下列操作4.2.1估算c的目标函数值bound(c)-上界4.2.2如果（bound(c)=down），将c加入ANT表/*子结点c有可能产生更优的解，将其加入活结点表，以后考虑对其进行扩展4.2.3如果（c是叶结点andbound(c)在表ANT中最大），则将结点c对应的完全解输出，算法结束/*结点c对应了1个新找到的、具有最大目标函数值的完全解最优解,4.2.4如果（c是叶结点andbound(c)在表ANT中不是最大），则：/*结点c对应了1个新找到的完全解，但该完全解的目标函数值与已经找到的、或未来可能找到完全解相比，并非更优i)令down=value(c)/*利用新找到的完全解的实际目标函数，更新问题的下界ii)对表ANT中所有满足bound(vj)bound(c)的结点vj，从表ANT中删除该结点！/*利用新找到的完全解的目标函数bound(c)，进行剪枝，从ANT表中去掉那些目标函数值不可能大于结点c的bound(c)的结点vj，即去掉那些目标函数值小于由于当前新找到的完全解c的目标值bound(c)的结点,分支限界法是一种高效、通用的问题求解方法。此方法发明者曾获计算机界最高奖项图灵奖。分支限界法三个关键技术1.如何确定合适的限界函数面向具体问题而定2.如何合理组织活结点表决定了结点扩展顺序1）FIFO队列：按照先进先出（FIFO）原则，选取下一个节点为扩展节点2）优先队列：按照优先队列中规定的优先级选取优先级最高的节点，成为当前扩展节点。3）堆,3.如何确定最优解中的各个分量对解空间树中的结点处理是根据结点的bound值进行的，有可能是跳跃式的，回溯也不是单纯沿着双亲结点一层层向上回溯。因此，当在某个叶结点上搜索到全局最优值时，有可能无法得到组成该最优解的各个分量。为此，可采用下述处理方法：1）对每个扩展结点，保存从根结点到该结点的路径2）在搜索过程中，构建搜索经过的树结构。当求得最优解后，从叶结点回溯到根结点，得到最优解各个分量问题：用于存储搜索树的存储空间可能会很大，增大了算法的空间复杂性,B,C,F,D,L,2,3,4,4,A,1,4,G,3,E,H,I,2,4,根据活结点表中各节点具体bound值，先处理D，后处理E，基本符合宽度优先序序,根据活结点表中各节点具体bound值，先处理E，后处理D，不符合宽度优先序序,分支限界法vs回溯法,求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有（？或多个）解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,2.搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,3.解空间树的扩展对扩展结点e_node，生成其全部子结点采取宽度优先或以最小耗费（最大效益）优先进行扩展，需要维护活结点表，因此占用的空间比回溯法大，但计算速度一般比回溯法快以空间换时间！,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,6.2最短路径问题,问题描述：在下图所给的有向图G中，每一边都有一个非负边权。要求：求出从源点s到目标点t之间的最短路径。,用优先队列式分支限界法，解空间树：1）树中边上的字母代表每一步经过的结点间路径2）树节点上的数字表示从源点s到该结点所对应的当前路长3）以经历过的边表示路径e.g.以图中顶点表示的路径s-1-2-5,边表示的路径sa:u:f,算法思想,1.解空间树中的结点v对应1条从源点s到图中某个顶点的路径；叶节点对应1条s到目标点t的路径；每个结点v需要记录本路径从s开始、经过的全部边或顶点e.g.树结点，当前路长14，对应的路径sa:u:f,各树结点v的限界函数1）上界up：可利用贪心法，求出1个上界方法：每步选择离当前结点最近的下一结点书上没有给出每条边的长度？！2）dist(v)下界树结点所对应路径的长度：从源点s至路径中最后一个顶点的总长e.g.对以顶点表示的路径s-1-2-5,或以边表示的路径sa:u:f，对应的树中结点？（红色），dist(?)=143.活结点表的组织组织为极小堆，其优先级/目标函数是结点所对应的当前路径长度dist,说明：教科书上的下界函数只考虑了当前部分路径的现有长度，没有考虑未来结点可能带来的路径长度，下界函数不准确e.g.对部分路径s125,书上给出的下界值/优先级/目标函数只是取为当前路径长度14；但显然对该部分解，不管从结点5向后如何走，下界值肯定比14大,4.搜索过程1）从源顶点s、空优先队列开始，首先选择s作为扩展结点2）结点s被扩展后，它的儿子结点被依次插入活结点表堆中3）从堆中取出优先级最高(即：dist(v)/目标函数/下界最小）的树结点v，作为当前扩展结点v对应的路径为s-i1-i2-ik与堆中其它结点相比，该路径的长度dist(v)最小e.g.见下页，堆中有3个活结点，对应了三条路径s-1-2-5、s-1-5-6-9、s-2，路径长度dist分别为14、6、3应选择dist最小的路径s-2，即原图中的城市顶点2应作为扩展结点,4)生成扩展结点的子结点在G(V,E)中，依次检查与当前扩展结点相邻的所有顶点。e.g.如果城市顶点2被选为扩展结点，则需要考察经过边f、g可到达的城市顶点5、65)考察各子结点是否可作为活结点是否有必要进一步扩展?如果i)从当前选择的扩展城市顶点i到它的邻接城市顶点j有边可达，并且ii)从源s出发，途经城市顶点i再到顶点j的所相应的路径的长度小于当前已经得到的最优路径长度(或问题上界up),即：dist(i)+distance(i,j)mindist=8,被剪枝舍弃右子结点表示路径s-3-6-9，dist=7=8,结点j就成为死结点；只有dist(j)问题上界16，树结点5被作为死结点舍弃,Step4.从当前活结点表ANT=2,3,4中，以lb为依据，并兼顾结点生成顺序，选取lb最小的结点2作为扩展结点，生成结点6、7、8；计算这3个结点的lb，lb(6)=lb(7)=16,lb(8)=19;舍弃结点8，将结点6、7加入活结点表,变为ANT=3,4,6,7Step5.从ANT中，选择lb最小的结点3扩展，生成结点9、10、11,Step6.按照上述方法，依次扩展搜索树，得到最优解135421，最短路径长度=1+2+3+7+3=16TSP问题分支限界法算法描述：数组x1:n存储搜索路径上的树顶点,1.采用贪心法，计算上界up；根据目标函数公式，计算下界down2.将活结点表ANT初始化为空3.for(i=1;i=1)5.1i=k+1;5.2xi=1;5.3while(xiC),6,7,无效死结点(wC),9,8,剪枝条件:ub上界183.如果是，则该结点被剪枝舍弃e.g.结点2，对应路径01结点10，对应路径0357,问题完全解界限14,18,1.树结点编号对应了结点搜索/生成顺序2.表示被丢弃的死结点,2+7+5+3=17,3+4+5+3=15,2+8+5+7=22,2+7+6+3=18,2+8+5+3=18,4+8+5+3=20,3+4+6+3=16,3+7+5+3=18,3+4+8+7=22,3+4+6+3=16,1.采用贪心法，计算上界up；根据目标函数公式，计算下界down2.将活结点表ANT初始化为空3.for(i=1;i=1)5.1对顶点u的所有邻接点v5.1.1计算v的目标函数lb(v)5.1.2if(lb,lb(v)值存入活结点表ANT5.2如果i=k-1,即搜索到达叶节点，并且叶子结点的目标函数值lb在表ANT中最小，则输出该叶结点对应的最优解,5.3否则，若i=k-1，并且叶子结点的目标函数值lb在表ANT中不是最小，则5.3.1令up=表ANT中叶子结点所具有的最小的lb值5.3.2删除ANT表中目标函数值lb超出up的结点5.4u=表ANT中lb最小的结点的v值（顶点编号）/*选取lb最小的活结点v，作为扩展结点5.5i=表ANT中lb最小的结点的i值；/*扩展结点对应的段号5.6i+,批处理作业调度,给定n个作业的集合J=J1,J2,Jn,每个作业有3项任务需要在3台机器上完成，作业Ji需要机器j的处理时间为tij（1in,1j3）。每个作业需要依次在机器1、2、3上处理。要求：确定作业最优处理顺序，使得从第1个投入执行的作业在机器1上开始，到最后1个作业在机器3上结束为止，所需时间最短。最优调度：机器1上无空余时间，机器2、3上的空闲/等待时间最短可以证明：对最优调度，作业在机器1上的执行顺序与机器2、3上的执行顺序是一致的。,分支限界法的复杂性,与回溯法一样，分支限界法属于蛮力穷举法。最坏情况下，需要遍历指数阶个结点的解空间树，复杂性为指数阶。与回溯法不同：优先扩展上层结点，采用界限函数，利于大范围剪枝，缩小搜索空间；同时，利用限界函数，不断调整搜索方向，选择最优可能获得最优解的子树优先搜索性能密切依赖于限界函数对具体问题，很难预测分支限界法的搜索行为跳跃式搜索，构造完整解比较麻烦空间复杂性较高，最坏情况下，空间复杂性为指数阶,作业在机器上的处理时间矩阵T,83,M1,M2,M3,J2:10,J3:9,J1:5,J4:7,空闲:10,J2:5,J3:9,J1:7,J4:8,空闲:15,J2:2,J3:5,J1:9,J4:10,需要估计：问题上界，部分解下界剪枝条件：部分解下界问题上界理想情况下，机器1、2无空闲，最后处理的恰好是机器3上处理时间最短的作业例如，以作业Ji开始的处理顺序，估算处理所需的最短时间部分解下界为：ti1+tj2+mintk3,wherej=1,.,n,ki一般情况下，对1个已经安排的作业集合M，|M|=k，M为1,2,.,n的子集，设sum1k表示机器1完成k个作业的处理时间，sum2k表示机器2完成k个作业的处理时间，现在需要处理作业k+1，此时该部分解的目标函数的下界为：,当第k+1步恰好调度第k+1个作业时，(1)sum1k+1=sum1k+tk+1,1(2)lb=maxsum1k+1,sum2k+ti2/*i不在M中+mintj3,/*jk+1,j不在M中(3)sum2k+1=maxsum1k+1,sum2k+tk+1,2,1,2,3,4,5,6,7,8,9,10,11,取lb最小的结点优先扩展,6.3装载问题,1.问题描述,有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。,容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。,2.队列式分支限界法（FIFO）（略）,在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中将第k个物品装入。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)第k个物品不装入。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。,while(true)/检查左儿子结点if(Ew+wibestwthenbestwC(i)8.ifibestwandi0;j-)bestxj=bestE-LChild;bestE=bestE-parent;,6.3装载问题,5.优先队列式分支限界法,解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。,6.4布线问题,1.算法思想,解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。,接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。,6.4布线问题,Positionoffset4;offset0.row=0;offset0.col=1;/右offset1.row=1;offset1.col=0;/下offset2.row=0;offset2.col=-1;/左offset3.row=-1;offset3.col=0;/上,定义移动方向的相对位移,for(inti=0;i=m+1;i+)grid0i=gridn+1i=1;/顶部和底部for(inti=0;i=n+1;i+)gridi0=gridim+1=1;/左翼和右翼,设置边界的围墙,6.4布线问题,for(inti=0;ibestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。,6.6最大团问题,3.算法思想,算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。,6.7旅行售货员问题,1.问题描述,某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。,6.7旅行售货员问题,2.算法描述,算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。,算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：,6.7旅行售货员问题,2.算法描述,1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。,2、当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。,6.7旅行售货员问题,2.算法描述,算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。算法结束时返回找到的最小费用，相应的最优解由数组v给出。,6.8电路板排列问题,算法描述,算法开始时，将排列树的根结点置为当前扩展结点。在do-while循环体内算法依次从活结点优先队列中取出具有最小cd值的结点作为当前扩展结点，并加以扩展。,首先考虑s=n-1的情形，当前扩展结点是排列树中的一个叶结点的父结点。x表示相应于该叶结点的电路板排列。计算出与x相应的密度并在必要时更新当前最优值和相应的当前最优解。,当sn-1时，算法依次产生当前扩展结点的所有