《s第6章heaven14分析》由会员分享，可在线阅读，更多相关《s第6章heaven14分析（46页珍藏版）》请在金锄头文库上搜索。
1、智能信息处理研究中心（RCIIP）Pan第第6 6章章 分支限界法分支限界法潘海为潘海为Birds of a feather flock together物以类聚、一丘之貉物以类聚、一丘之貉http:/http:/1智能信息处理研究中心（RCIIP）PanPan理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架掌握分支限界法的算法框架队列式队列式(FIFO)分支限界法分支限界法优先队列式分支限界法优先队列式分支限界法 通过应用范例学习分支限界法的设计策略通过应用范例学习分支限界法的设计策略单源最短路径问题单源最短路径问题装载问题；装载问题；0-1背包问题；背包问题
2、；最大团问题；最大团问题；旅行售货员问题旅行售货员问题批处理作业调度问题批处理作业调度问题学习要点学习要点2智能信息处理研究中心（RCIIP）Pan 分支限界法的背景分支限界法的背景理查德理查德.卡普卡普在在IBMIBM期间，深入研究了与实际应用有密切联系的一系列数学问题，如期间，深入研究了与实际应用有密切联系的一系列数学问题，如路径问题路径问题、背包问题背包问题、覆盖问题覆盖问题、匹配问题匹配问题、分区问题分区问题、调度问题调度问题等，取得了许多出色的成等，取得了许多出色的成果。这些问题有一个共同的特点，即如果用图来表示问题，那么当图中增加一个果。这些问题有一个共同的特点，即如果用图来表示问
3、题，那么当图中增加一个结点时，需要考察的可能的解的数目就急剧增加，形成所谓结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸组合爆炸” (combinatorial explosion)(combinatorial explosion)，使计算机的计算工作量大大增加，到一定程度就根，使计算机的计算工作量大大增加，到一定程度就根本无法实现。本无法实现。以路径问题中最著名的以路径问题中最著名的旅行商问题为例旅行商问题为例，在卡普以前，最好的结果是，在卡普以前，最好的结果是RandRand公司的公司的丹齐格丹齐格(George (George BenardBenard DantzigDa
4、ntzig) )、福格森、福格森(R(RFulkerson)Fulkerson)和约翰逊和约翰逊(S(SJohnson)Johnson)用手工和计算机相结合的办法，求出了包含用手工和计算机相结合的办法，求出了包含4949个城市个城市的旅行商的最佳路线。卡普的旅行商的最佳路线。卡普和他的同事海尔特和他的同事海尔特(M(MHeld)Held)经过反复研究，终于提出了一种称为经过反复研究，终于提出了一种称为“分支限界法分支限界法”(branch(branchandandbound method)bound method)的新方法，用这种新方法实现的算法使旅行推销的新方法，用这种新方法实现的算法使旅行
5、推销员能周游的城市数达到员能周游的城市数达到6565个个，从而打破了由，从而打破了由RandRand公司保持的记录。公司保持的记录。 19551955年年文学学士学位文学学士学位 19561956年年理科硕士学位理科硕士学位 19591959年年应用数学博士学位应用数学博士学位( (哈佛大学哈佛大学) ) Yorktown Heights Yorktown Heights的的IBMIBM沃森研究中心沃森研究中心 1985年获得年获得ACM的图灵奖的图灵奖3智能信息处理研究中心（RCIIP）Pan 分支限界法常以分支限界法常以广度优先广度优先或以最小耗费（最大效益）优或以最小耗费（最大效益）优先
6、的方式搜索问题的解空间树。先的方式搜索问题的解空间树。 分支限界法的基本思想分支限界法的基本思想4智能信息处理研究中心（RCIIP）Pan 分支限界法常以分支限界法常以广度优先广度优先或以最小耗费（最大效益）优或以最小耗费（最大效益）优先的方式搜索问题的解空间树。先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点在分支限界法中，每一个活结点只有一次机会只有一次机会成为扩展成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的结点。在这些儿子结点中，导致不可行解或导致非最优解的儿
7、子结点被舍弃，其余儿子结点被加入活结点表中。儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。结点表为空时为止。 分支限界法的基本思想分支限界法的基本思想5智能信息处理研究中心（RCIIP）Pan 分支限界法常以分支限界法常以广度优先广度优先或以最小耗费（最大效益）优或以最小耗费（最大效益）优先的方式搜索问题的解空间树。先的方式搜索问题的解空间树。 在分支限界法中，每一个活结
8、点在分支限界法中，每一个活结点只有一次机会只有一次机会成为扩展成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。结点
9、表为空时为止。 分支限界法的基本思想分支限界法的基本思想分支限界方法找最优解的效率比回朔法高。分支限界方法找最优解的效率比回朔法高。原因在于原因在于它采用了它采用了最小代价估值函数最小代价估值函数指导搜索，在活节点表指导搜索，在活节点表中，选择有最小代价估值的节点作为扩展节点。即总是像最中，选择有最小代价估值的节点作为扩展节点。即总是像最有可能获得最优解的子树上扩展。并且采用限界函数有可能获得最优解的子树上扩展。并且采用限界函数U U杀死杀死活节点表中不可能成为最优解的节点，提高算法的效率。活节点表中不可能成为最优解的节点，提高算法的效率。6智能信息处理研究中心（RCIIP）Pan 常见的两种
10、分支限界法常见的两种分支限界法（1 1）队列式分支限界法）队列式分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO）或者后进先出）或者后进先出（LIFOLIFO）原则选取下一个结点为扩展结点。）原则选取下一个结点为扩展结点。 （2 2）优先队列式分支限界法）优先队列式分支限界法 队列式分支限界法队列式分支限界法对结点的选择规则相当死板，具对结点的选择规则相当死板，具有一定的有一定的 “盲目盲目”性。这种选择规则不利于快速检索到性。这种选择规则不利于快速检索到一个能够到达答案的结点。一个能够到达答案的结点。 对活结点使用一个对活结点使用一个“有智能有智能”的的排序函数排序函数C()
11、C()来选取来选取下一个结点，往往可以加快获取答案的速度。下一个结点，往往可以加快获取答案的速度。 按照优先队列中规定的优先级选取优先级最高的结按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。常用方法是点成为当前扩展结点。常用方法是LC(LeastLC(Least Cost) Cost)方法方法。 分支限界法的基本思想分支限界法的基本思想7智能信息处理研究中心（RCIIP）Pan 实例8-拼块游戏问题输入输入: 具有具有8 个编号小方块的魔方个编号小方块的魔方输出输出: 移动系列移动系列, 经过这些移动经过这些移动, 魔方达到目标状态魔方达到目标状态 分支限界法的基本思想分支限
12、界法的基本思想28316475初始状态12384765目标状态8智能信息处理研究中心（RCIIP）Pan FIFO队列式分支限界法 分支限界法的基本思想分支限界法的基本思想. 2 31 8 476512384765目标状态2 . 31 8 47651 2 3. 8 47652 3 .1 8 47652 8 31 . 47651 2 37 8 4.651 2 38 . 47659智能信息处理研究中心（RCIIP）Pan 优先队列式分支限界法优先队列式分支限界法 “有智能有智能”的排序函数的排序函数C()C()最小代价估计函数：最小代价估计函数：C C(X)(X)从初始状态到从初始状态到X X所移
13、动的次数还未到位的数字方块数。所移动的次数还未到位的数字方块数。从初始状态到从初始状态到X X所移动的次数是实际耗费的代价，还未到位的数字方所移动的次数是实际耗费的代价，还未到位的数字方块数表示至少还要移动的次数。块数表示至少还要移动的次数。 分支限界法的基本思想分支限界法的基本思想28316475初始状态12384765目标状态C(X)=C(1)=0+4=4C(X)=s+0=s10智能信息处理研究中心（RCIIP）Pan283164751238476514263446556576869710511712513C(X)= C(13) =5+0=5283164752831476528316475
14、2831476523184765283147658321476528371465231847652318476512384765L=(3,2,4)L=(5,6,2,4,7)L=(6,2,4,7,8,9)L=(10,2,4,7,8,9,11)L=(12,2,4,7,8,9,11)L=(2,4,7,8,9,11)优先队列优先队列L=(1)1 2 3847 6 511智能信息处理研究中心（RCIIP）Pan 分支限界法与回溯法比较（1 1）求解目标）求解目标回溯法的求解目标是找出解空间树中满足约束条件的所回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件
15、有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。下的最优解。 （2 2）搜索方式的不同）搜索方式的不同回溯法以深度优先的方式搜索解空间树，而分支限界法回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。则以广度优先或以最小耗费优先的方式搜索解空间树。 分支限界法的基本思想分支限界法的基本思想12智能信息处理研究中心（RCIIP）Pan 问题描述问题描述下面以一个例子来说明单源最短路径问题：在下图所给下面以一个例子来说明单源最短路径问题：在下图所
16、给的有向图的有向图G G中，每一边都有一个非负边权。要求图中，每一边都有一个非负边权。要求图G G的从的从源顶点源顶点s s到目标顶点到目标顶点t t之间的最短路径。之间的最短路径。 单源最短路径问题单源最短路径问题13智能信息处理研究中心（RCIIP）Pan 单源最短路径问题单源最短路径问题 问题描述问题描述下图是用优先队列式分支限界法解有向图下图是用优先队列式分支限界法解有向图G G的单源最短路径问题产生的解的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。AB14智能信息处理研究中心（RC
17、IIP）Pan 单源最短路径问题单源最短路径问题 问题描述下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。AB15智能信息处理研究中心（RCIIP）Pan 单源最短路径问题单源最短路径问题 结点结点A控制结点控制结点B如果解空间树中以结点如果解空间树中以结点A A为根的子树中所含的解优于以结点为根的子树中所含的解优于以结点B B为根的子树为根的子树中所含的解，则称中所含的解，则称结点结点A A控制结点控制结点B B，以结点，以结点B B为根的子树可以剪去。为根的子树可以剪去。AB16智能信息处理研究中心（RCIIP）
18、Pan 算法思想算法思想解此问题的优先队列式分支限界法用一解此问题的优先队列式分支限界法用一极小堆极小堆来存储来存储活结点表。其优先级是结点所对应的当前路长。活结点表。其优先级是结点所对应的当前路长。算法从图算法从图G G的源顶点的源顶点s s和空优先队列开始。结点和空优先队列开始。结点s s被扩被扩展后，它的儿子结点被依次插入堆中。此后，算法从展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点当前扩
19、展结点i i到顶点到顶点j j有边可达，且从源出发，途经有边可达，且从源出发，途经顶点顶点i i再到顶点再到顶点j j的所相应的路径的长度小于当前最优的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。队列为空时为止。 单源最短路径问题单源最短路径问题17智能信息处理研究中心（RCIIP）Pan 剪枝策略剪枝策略在在算算法法扩扩展展结结点点的的过过程程中中，一一旦旦发发现现一一个个结结点点的的下下界界不不小小于于当当
20、前前找找到到的的最最短短路路长长，则则算算法法剪剪去去以以该结点为根的子树。该结点为根的子树。在在算算法法中中，利利用用结结点点间间的的控控制制关关系系进进行行剪剪枝枝。从从源源顶顶点点s s出出发发，2 2条条不不同同路路径径到到达达图图G G的的同同一一顶顶点点。由由于于两两条条路路径径的的路路长长不不同同，因因此此可可以以将将路路长长长长的的路径所对应的树中的结点为根的子树剪去。路径所对应的树中的结点为根的子树剪去。 单源最短路径问题单源最短路径问题18智能信息处理研究中心（RCIIP）Pan 0-1背包问题背包问题 给定给定n n种物品和一背包。物品种物品和一背包。物品i i的重量是的
21、重量是w wi i，其价值为，其价值为v vi i，背包的容量为，背包的容量为C C。问应如何选择装入背包的物品，使得。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大装入背包中物品的总价值最大? ? 输入：输入：C0, wi0, vi0, 1 in 输出：输出：(x1, x2, , xn), xi0, 1, 满足满足19智能信息处理研究中心（RCIIP）Pan 0-1背包问题背包问题FIFO队列式分支限界法的基本思想实例实例 n=3n=3，C=30C=30，w=16w=16，1515，1515，p=45p=45，2525，2525可行性约束函数：可行性约束函数：P=45P=45 P
22、=50P=50P=25P=25 P=25P=25P=0P=0AB,CE,F,GFIFO队列队列K,L,M,N,O20智能信息处理研究中心（RCIIP）Pan结点的优先级结点的优先级由已装袋的物品价值加上剩下的最大单由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的算法首先检查当前扩展结点的左儿子结点的可行性可行性。如果该左儿子结点是可行结点如果该左儿子结点是可行结点，则将它加入到子集树和，则将它加入到子集树和活结点优先队列中。活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点当前扩展结点的右
23、儿子结点一定是可行结点，仅当右儿，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。队列。当扩展到叶节点时为问题的最优值。 0-1背包问题背包问题优先队列式分支限界法的基本思想优先队列式分支限界法的基本思想首先，要对输入数据进行预处理，将各物品依其单位首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。重量价值从大到小进行排列。21智能信息处理研究中心（RCIIP）Pan 0-1背包问题背包问题优先队列式分支限界法的基本思想实例实例 n=3n=3，C=30C=30，w=16w=16，
24、1515，1515，p=45p=45，2525，2525 使用最大堆使用最大堆 上界上界 up = 68.38 Bound(int i)实现实现下界下界 L = 45 贪心算法实现贪心算法实现 bestp为当前最优值，则为当前最优值，则 L=45 bestp up=68.3822智能信息处理研究中心（RCIIP）Pan 0-1背包问题背包问题优先队列式分支限界法的基本思想优先队列优先队列实例实例 n=3n=3，C=30C=30，w=16w=16，1515，1515，p=45p=45，2525，2525P=45P=45 P=50P=50A, level=1K, level=450,4568.38
25、,4568.38,4550,45B, level=2C, level=2C, level=2E, level=3F, level=3K, level=4L, level=423智能信息处理研究中心（RCIIP）Pan while (i != n+1) / 非叶结点非叶结点 / 检查当前扩展结点的左儿子结点检查当前扩展结点的左儿子结点 Typew wt = cw + wi; if (wt bestp) bestp = cp+pi; AddLiveNode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1); / 检查当前扩展结点的右儿子结点检查当前扩展结点
26、的右儿子结点 if (up = bestp) / 右子树可能含最优解右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); / 取下一个扩展节点（略）取下一个扩展节点（略） 0-1背包问题背包问题分支限界搜索过程分支限界搜索过程24智能信息处理研究中心（RCIIP）Pan 0-1背包问题背包问题分支限界搜索过程分支限界搜索过程 实例实例 (1)(1)物品个数为物品个数为 n=4n=4 (2)(2)背包的容量为背包的容量为 C=7C=7 (3)(3)物品的重量分别为物品的重量分别为 w=3w=3，5 5，2 2，11 (4)(4)物品的价值分别为物品的价值分
27、别为 p=9p=9，1010，7 7，4425智能信息处理研究中心（RCIIP）Pan 装载问题装载问题有一批共有一批共n n个集装箱要装上个集装箱要装上2 2艘载重量分别为艘载重量分别为c c1 1和和c c2 2的轮船，的轮船，其中集装箱其中集装箱i i的重量为的重量为w wi i，且，且装载问题装载问题确定是否有一个合理的装载方案可将这确定是否有一个合理的装载方案可将这n n个集装箱装上这个集装箱装上这2 2艘艘轮船。如果有，找出一种装载方案。轮船。如果有，找出一种装载方案。容易证明，如果一个给定装载问题有解，则采用下面的策略容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优
28、装载方案。可得到最优装载方案。(1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。26智能信息处理研究中心（RCIIP）Pan队列式分支限界法队列式分支限界法在算法的在算法的whilewhile循环中，首先检测当前扩展结点的左儿子循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中中。然后将其右儿子结点加入到活结点队列中( (右儿子结右儿子结点一定是可行结点点一定是可行结点) )。2 2个
29、儿子结点都产生后，当前扩展个儿子结点都产生后，当前扩展结点被舍弃。结点被舍弃。 装载问题装载问题27智能信息处理研究中心（RCIIP）Panwhile (true) / 检查左儿子结点检查左儿子结点 if (Ew + wi = c) / xi = 1 EnQueue(Q, Ew + wi, bestw, i, n); / 右儿子结点总是可行的右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); / xi = 0 Q.Delete(Ew); / 取下一扩展结点取下一扩展结点 装载问题装载问题队列式分支限界法28智能信息处理研究中心（RCIIP）Pan 装载问题装载问题算
30、法的改进算法的改进节点的左子树表示将此集装箱装上船，右子树表示不将节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。此集装箱装上船。设设bestwbestw是当前最优解；是当前最优解；ewew是当前扩展结点所相应的重量；是当前扩展结点所相应的重量；r r是剩余集装箱的重量。则当是剩余集装箱的重量。则当ew+rew+r bestwbestw时，可将其右子时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的
31、时候更新入左子树的时候更新bestwbestw的值。的值。29智能信息处理研究中心（RCIIP）Pan/ 检查左儿子结点检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列加入活结点队列 if (i bestw & i n) Q.Add(Ew); / 可能含最优解可能含最优解 Q.Delete(Ew); / 取下一扩展结点取下一扩展结点右儿子剪枝右儿子剪枝 装载问题装载问题算法的改进30智能信息处理研究中心（RCIIP）Pan 装载问题装载问题构造最优解构造最优解为了在算法结束后能方便
32、地构造出与最优值相应的最为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。点的指针，并设置左、右儿子标志。找到最优值后，可以根据找到最优值后，可以根据parentparent回溯到根节点，找到回溯到根节点，找到最优解。最优解。 31智能信息处理研究中心（RCIIP）Pan 装载问题装载问题优先队列式分支限界法优先队列式分支限界法解装载问题的优先队列式分支限界法用最大优先队列解装载问题的
33、优先队列式分支限界法用最大优先队列存储活结点表。活结点存储活结点表。活结点x x在优先队列中的优先级定义在优先队列中的优先级定义为从根结点到结点为从根结点到结点x x的路径所相应的载重量再加上剩的路径所相应的载重量再加上剩余集装箱的重量之和。余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中优先级最大的活结点成为下一个扩展结点。以结点以结点x x为根的子树中所有结点相应的路径的载重量为根的子树中所有结点相应的路径的载重量不超过它的优先级。不超过它的优先级。在优先队列式分支限界法中，一旦有一个叶结点成为在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以
34、断言该叶结点所相应的解即为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。最优解。此时可终止算法。 32智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题 问题描述问题描述给定给定n n个顶点的带权图个顶点的带权图G=(V, E),G=(V, E),图中各边的权为正数，图图中各边的权为正数，图中的中的一条周游路线一条周游路线是包括是包括V V中的每个顶点在内的一条回路，中的每个顶点在内的一条回路，一条周游路线的费用一条周游路线的费用是这条路线上所有边的权之和。是这条路线上所有边的权之和。 旅行商问题旅行商问题( (Traveling Salespers
35、on) )是要在图是要在图G G中找出一中找出一条有最小费用的周游路线。此问题是条有最小费用的周游路线。此问题是NPNP完全问题。完全问题。33智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题实例FIFO队列式AB1C2F3L4G4M3DH2N4I4O2EJ2P3K3Q2341342306105420C,D,EC,D,EF,G,H,I,J,KF,G,H,I,J,KB BL,M,N,P,QL,M,N,P,Q595966662525262634智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题实例优先队列式(1)AB1C2DH2N4EJ2K33413423
36、06105420E E,D,C,D,CB B2525J J,K,K,N N,I,C,I,CK K, ,N N,I,C,I,CN N,I,C,I,CI4D D,J,K,J,K,CH H,J,K,I,C,J,K,I,C35智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题实例优先队列式(2)1342306105420AB1C2DH2N4EJ2P3K33425252525I436智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题实例归约矩阵法-10-2-2-3-421行约数行约数 = =-1-0-3-0 -04列列约约数数| 矩阵约数矩阵约数r=r=行约数行约
37、数+ +列约数列约数=25=25 最小代价函数最小代价函数C(1)=25C(1)=2537智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题实例归约矩阵法134230610542038智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题4139智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题413240智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题41321341智能信息处理研究中心（RCIIP）Pan 旅行售货员问题旅行售货员问题41321324周游路径：最小耗费：2542智能信息处理研究中心（RCIIP）P
38、an 批处理作业调度问题批处理作业调度问题 问题的描述问题的描述 给定给定n n个作业的集合个作业的集合JJ1 1,J,J2 2, , ,J Jn n 。 每个作业必须先由机器每个作业必须先由机器1 1处理，然后由机器处理，然后由机器2 2处理。处理。 作业作业J Ji i需要机器需要机器j j的处理时间为的处理时间为t tjiji。 对于一个确定的作业调度，设对于一个确定的作业调度，设F Fjiji是作业是作业i i在机器在机器j j上完成处上完成处理的时间。所有作业在机器理的时间。所有作业在机器2 2上完成处理的时间和称为该作业上完成处理的时间和称为该作业调度的完成时间和。调度的完成时间和
39、。批处理作业调度问题批处理作业调度问题 对于给定的对于给定的n n个作业，制定最佳作业调度方案，使其完成时个作业，制定最佳作业调度方案，使其完成时间和达到最小。间和达到最小。43智能信息处理研究中心（RCIIP）Pan 批处理作业调度问题批处理作业调度问题 实例 最佳调度方案是最佳调度方案是1,3,2，其完成时间和为，其完成时间和为18。BC1F2L3G3M2DH1N3I3O1EJ1P2K2Q1231918202119193 32 2作业作业3 31 13 3作业作业2 21 12 2作业作业1 1机器机器2 2机器机器1 1t tji44智能信息处理研究中心（RCIIP）Pan 注意到如果选择Pk，使t1pk在k=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。 这可以作为优先队列式分支限界法中的限界函数。 批处理作业调度问题批处理作业调度问题限界函数在结点E处相应子树中叶结点完成时间和的下界是45智能信息处理研究中心（RCIIP）PanPan总结总结理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架队列式(FIFO)分支限界法优先队列式分支限界法46
