《算法设计与分析-6分支限界法》由会员分享，可在线阅读，更多相关《算法设计与分析-6分支限界法（124页珍藏版）》请在金锄头文库上搜索。
1、第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. TSP
2、 xi 1,2,3,n隐约束：为满足问题的解而对不同分量之间施加的约束e.g. TSP，各个城市只能遍历一次4）解空间中各个解根据相互间关系和解的构造顺序，组成解空间树,e.g. 4个城市的旅行商问题,1） 非叶结点对应部分解 2）叶节点对应最优解、可行解,5）对解空间中的解，引入定量指标，作为优化依据e.g. 旅行商问题：旅游路径总长最短6）问题求解过程带有回溯的深度优先树搜索以深度优先的方式，从树根结点开始，依次扩展树结点，直到达到叶结点搜索过程中动态产生解空间 深度优先目的：尽可能快地获得可行解,扩展过程中，碰到可行非叶结点（部分解），可进一步扩展e.g. 结点C对应部分解可进一步扩展为
3、: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间
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代表到目前为止,在前面的搜索中，从其它已经搜索过的路径中，找到的最佳回路的权和（总长度）,分支限界法（branch and bound）原理： 1）按宽度优先策略遍历解空间树。 2）在遍历过程中，对处理的每个结点vi，根据界限函数，估计沿该结点向下搜索所可
5、能达到的完全解的目标函数的可能取值范围界限bound(vi)=downi, upi 3）从中选择使目标函数取的极值（最大、最小）的结点优先进行宽度优先搜索，从而不断调整搜索方向，尽快找到问题解关键：各结点的界限函数bound(vi)=downi, upi, 依据具体问题而定e.g. 4个城市的TSP搜索树中的界限函数,bound(G),bound(D),bound(E),子树,子 树,子 树,一、与回溯法类似，解向量、解空间、解空间树二、解空间树中的结点分为4种类型活结点，死结点，扩展结点，待处理结点,扩展结点,未处理结点, 活结点当前满足约束条件、未来有可能产生最优解的结点；对应部分解, e
6、.g. 结点G、D、E所有活结点组成活结点表ANT (Alive Node Table), 扩展结点从活结点表ANT中取出来，当前准备进行扩展的结点，即当前进行处理的结点1）评估每个活结点价值，按照价值最大化/最小化原则，从ANT中选取扩展结点 e_node2）e_node扩展方式：宽度优先，生成e_node的全部子节点；评估这些子节点，满足界限约束、有可能产生更优解的结点被作为活结点，加入ANT；不满足约束、或无法产生最优解的子节点被舍弃剪枝3） e_node结点被扩展后，该结点转换为死结点，以后将不会被再搜索活结点扩展结点死结点,e.g. 如下图i) 从上图中的3个活结点G、D、E中，选择
7、价值最大的结点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
8、，生成其全部子结点采取宽度优先进行扩展e.g. 结点D对应于，考察它的2个子结点和,四、对扩展结点e_node，生成其全部儿子结点后，判断评估每个儿子结点：i) 是否满足约束条件。如不满足，则作为死结点ii）估算沿着儿子结点向下搜索时，目标函数可能取得的“界”，即沿着儿子结点向下构造出的最终解可能取得的目标函数的范围；-极大化目标，估计子节点目标函数上界-极小化目标，估计子节点目标函数下界iii）将全部活结点组织在活结点表ANT中利用活结点的“界”值，对活结点进行价值评估是否有可能得到最优解？关键：目标函数界限函数！,五、扩展结点e_node选取扩展树时，需要从活结点表ANT中选取合适的活结点
9、，将其转化为扩展结点e_node1) 对最小化问题（如TSP），选取具有最小“界”的活结点e.g. 前图中，部分解D的最小界：经过D的最短路径长度至少（下界）是多少2) 对最大化问题（如背包问题），选取具有最大“界”的活结点，物品装入方案的最大价值e.g. 3) 当到达1个叶结点时，得到1个可行解，该可行解对应的最优值bound(x1,x2,xn)可作为当前最优解的1个“界”,六、结点界限函数及剪枝进行结点/树扩展时，利用界限函数估计每个结点可能达到的最优解，进行剪枝1) 估计e_node的每个儿子结点ci的“界”bound(ci)-极大化目标，估计子结点目标函数上界-极小化目标，估计子结点目
10、标函数下界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,循环，直到某个叶结点的目标函数值在
11、表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是叶结点 and bound(c)在表ANT中最大），则将结点c对应的完全解输出，算法结束/* 结点c对应了1个新找到的、具有最大目标函数值的完全解最优解,4.2.4
12、 如果（c是叶结点 and bound(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)的结点,分支限界法是
13、一种高效、通用的问题求解方法。此方法发明者曾获计算机界最高奖项图灵奖。分支限界法三个关键技术 1. 如何确定合适的限界函数面向具体问题而定2. 如何合理组织活结点表决定了结点扩展顺序1）FIFO队列：按照先进先出（FIFO）原则，选取下一个节点为扩展节点2）优先队列：按照优先队列中规定的优先级选取优先级最高的节点，成为当前扩展节点。3）堆,3. 如何确定最优解中的各个分量对解空间树中的结点处理是根据结点的bound值进行的，有可能是跳跃式的，回溯也不是单纯沿着双亲结点一层层向上回溯。因此，当在某个叶结点上搜索到全局最优值时，有可能无法得到组成该最优解的各个分量。为此，可采用下述处理方法：1）对
14、每个扩展结点，保存从根结点到该结点的路径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 回溯法,求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有（？或多个）解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满
15、足约束条件的解中找出在某种意义下的最优解。,2. 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,3. 解空间树的扩展对扩展结点e_node，生成其全部子结点采取宽度优先或以最小耗费（最大效益）优先进行扩展，需要维护活结点表，因此占用的空间比回溯法大，但计算速度一般比回溯法快以空间换时间！,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,6.2 最短路径问题,问题描述：在下图所给的有向图G中，每一边都有一个非负边权。要求：求出从源点s到目标点t之间的最短路径。,
