s-第6章_heaven-14

1、智能信息处理研究中心（RCIIP）Pan1第第6 6章章 分支限界法分支限界法潘海为潘海为Birds of a feather flock together物以类聚、一丘之貉物以类聚、一丘之貉http:/http:/智能信息处理研究中心（RCIIP）PanPan2 理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架掌握分支限界法的算法框架 队列式队列式(FIFO)分支限界法分支限界法 优先队列式分支限界法优先队列式分支限界法 通过应用范例学习分支限界法的设计策略通过应用范例学习分支限界法的设计策略 单源最短路径问题单源最短路径问题 装载问题；装载问题； 0-1背

2、包问题；背包问题； 最大团问题；最大团问题； 旅行售货员问题旅行售货员问题 批处理作业调度问题批处理作业调度问题智能信息处理研究中心（RCIIP）Pan3分支限界法的背景分支限界法的背景理查德理查德.卡普卡普在在IBMIBM期间，深入研究了与实际应用有密切联系的一系列数学问题，如期间，深入研究了与实际应用有密切联系的一系列数学问题，如路径问题路径问题、背包问题背包问题、覆盖问题覆盖问题、匹配问题匹配问题、分区问题分区问题、调度问题调度问题等，取得了许多出色的成等，取得了许多出色的成果。这些问题有一个共同的特点，即如果用图来表示问题，那么当图中增加一个果。这些问题有一个共同的特点，即如果用图来表

3、示问题，那么当图中增加一个结点时，需要考察的可能的解的数目就急剧增加，形成所谓结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸组合爆炸” (combinatorial explosion)(combinatorial explosion)，使计算机的计算工作量大大增加，到一定程度就，使计算机的计算工作量大大增加，到一定程度就根本无法实现。根本无法实现。以路径问题中最著名的以路径问题中最著名的旅行商问题为例旅行商问题为例，在卡普以前，最好的结果是，在卡普以前，最好的结果是RandRand公司的公司的丹齐格丹齐格(George Benard Dantzig)(George Benar

4、d Dantzig)、福格森、福格森(R(RFulkerson)Fulkerson)和约翰逊和约翰逊(S(SJohnson)Johnson)用手工和计算机相结合的办法，求出了包含用手工和计算机相结合的办法，求出了包含4949个城市个城市的旅行商的最佳路线。卡普的旅行商的最佳路线。卡普和他的同事海尔特和他的同事海尔特(M(MHeld)Held)经过反复研究，终于提出了一种称为经过反复研究，终于提出了一种称为“分支限界分支限界法法”(branch(branchandandbound method)bound method)的新方法，用这种新方法实现的算法使旅行的新方法，用这种新方法实现的算法使旅行

5、推销员能周游的城市数达到推销员能周游的城市数达到6565个个，从而打破了由，从而打破了由RandRand公司保持的记录。公司保持的记录。 1955 1955年年文学学士学位文学学士学位 19561956年年理科硕士学位理科硕士学位 19591959年年应用数学博士学位应用数学博士学位( (哈佛大学哈佛大学) ) Yorktown Heights Yorktown Heights的的IBMIBM沃森研究中心沃森研究中心 1985年获得年获得ACM的图灵奖的图灵奖智能信息处理研究中心（RCIIP）Pan4 分支限界法常以分支限界法常以广度优先广度优先或以最小耗费（最大效益）优或以最小耗费（最大效益

6、）优先的方式搜索问题的解空间树。先的方式搜索问题的解空间树。分支限界法的基本思想分支限界法的基本思想智能信息处理研究中心（RCIIP）Pan5 分支限界法常以分支限界法常以广度优先广度优先或以最小耗费（最大效益）优或以最小耗费（最大效益）优先的方式搜索问题的解空间树。先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点在分支限界法中，每一个活结点只有一次机会只有一次机会成为扩展成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿

7、子结点被舍弃，其余儿子结点被加入活结点表中。解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。或活结点表为空时为止。 分支限界法的基本思想分支限界法的基本思想智能信息处理研究中心（RCIIP）Pan6 分支限界法常以分支限界法常以广度优先广度优先或以最小耗费（最大效益）优或以最小耗费（最大效益）优先的方式搜索问题的解空间树。先的方式搜索问题的解空间树。 在分支限界法中，每一个

8、活结点在分支限界法中，每一个活结点只有一次机会只有一次机会成为扩展成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。或活

9、结点表为空时为止。 分支限界法的基本思想分支限界法的基本思想分支限界方法找最优解的效率比回朔法高。分支限界方法找最优解的效率比回朔法高。原因在于原因在于它采用了它采用了最小代价估值函数最小代价估值函数指导搜索，在活节点指导搜索，在活节点表中，选择有最小代价估值的节点作为扩展节点。即总是表中，选择有最小代价估值的节点作为扩展节点。即总是像最有可能获得最优解的子树上扩展。并且采用限界函数像最有可能获得最优解的子树上扩展。并且采用限界函数U U杀死活节点表中不可能成为最优解的节点，提高算法的效杀死活节点表中不可能成为最优解的节点，提高算法的效率。率。智能信息处理研究中心（RCIIP）Pan7 常见的

10、两种分支限界法常见的两种分支限界法（1 1）队列式分支限界法）队列式分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO）或者后进先出（）或者后进先出（LIFOLIFO）原则选取下一个结点为扩展结点。原则选取下一个结点为扩展结点。 （2 2）优先队列式分支限界法）优先队列式分支限界法 队列式分支限界法队列式分支限界法对结点的选择规则相当死板，具对结点的选择规则相当死板，具有一定的有一定的 “ “盲目盲目”性。这种选择规则不利于快速检索到性。这种选择规则不利于快速检索到一个能够到达答案的结点。一个能够到达答案的结点。 对活结点使用一个对活结点使用一个“有智能有智能”的的排序函数排序函

11、数C()C()来选取下来选取下一个结点，往往可以加快获取答案的速度。一个结点，往往可以加快获取答案的速度。 按照优先队列中规定的优先级选取优先级最高的结点按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。常用方法是成为当前扩展结点。常用方法是LC(Least Cost)LC(Least Cost)方法方法。分支限界法的基本思想分支限界法的基本思想智能信息处理研究中心（RCIIP）Pan8 实例8-拼块游戏问题输入输入: 具有具有8 个编号小方块的魔方个编号小方块的魔方输出输出: 移动系列移动系列, 经过这些移动经过这些移动, 魔方达到目标状态魔方达到目标状态分支限界法的基本思想分

12、支限界法的基本思想28316475初始状态12384765目标状态智能信息处理研究中心（RCIIP）Pan9 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 . 4765智能信息处理研究中心（RCIIP）Pan10 优先队列式分支限界法优先队列式分支限界法 “有智能有智能”的排序函数的排序函数C()C()最小代价估计函数：最小代价估计函数：C C(X)(X)从初始状态到从初始状态到X X

13、所移动的次数还未到位的数字方块数。所移动的次数还未到位的数字方块数。从初始状态到从初始状态到X X所移动的次数是实际耗费的代价，还未到位的数字方所移动的次数是实际耗费的代价，还未到位的数字方块数表示至少还要移动的次数。块数表示至少还要移动的次数。分支限界法的基本思想分支限界法的基本思想28316475初始状态12384765目标状态C(X)=C(1)=0+4=4C(X)=s+0=s智能信息处理研究中心（RCIIP）Pan11283164751238476514263446556576869710511712513C(X)= C(13) =5+0=528316475283147652831647

14、52831476523184765283147658321476528371465231847652318476512384765L=(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 5智能信息处理研究中心（RCIIP）Pan12 分支限界法与回溯法比较（1 1）求解目标）求解目标回溯法的求解目标是找出解空间树中满足约束条件的所回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条

15、件有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。下的最优解。 （2 2）搜索方式的不同）搜索方式的不同回溯法以深度优先的方式搜索解空间树，而分支限界法回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。则以广度优先或以最小耗费优先的方式搜索解空间树。 分支限界法的基本思想分支限界法的基本思想智能信息处理研究中心（RCIIP）Pan13 问题描述问题描述下面以一个例子来说明单源最短路径问题：在下图所给下面以一个例子来说明单源最短路径问题：在下图

16、所给的有向图的有向图G G中，每一边都有一个非负边权。要求图中，每一边都有一个非负边权。要求图G G的从的从源顶点源顶点s s到目标顶点到目标顶点t t之间的最短路径。之间的最短路径。 单源最短路径问题单源最短路径问题智能信息处理研究中心（RCIIP）Pan14 单源最短路径问题单源最短路径问题 问题描述问题描述下图是用优先队列式分支限界法解有向图下图是用优先队列式分支限界法解有向图G G的单源最短路径问题产生的解的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。AB智能信息处理研究中心（RCI

17、IP）Pan15 单源最短路径问题单源最短路径问题 问题描述下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。AB智能信息处理研究中心（RCIIP）Pan16 单源最短路径问题单源最短路径问题 结点结点A控制结点控制结点B如果解空间树中以结点如果解空间树中以结点A A为根的子树中所含的解优于以结点为根的子树中所含的解优于以结点B B为根的子树为根的子树中所含的解，则称中所含的解，则称结点结点A A控制结点控制结点B B，以结点，以结点B B为根的子树可以剪去。为根的子树可以剪去。AB智能信息处理研究中心（RCIIP）P

18、an17 算法思想算法思想 解此问题的优先队列式分支限界法用一解此问题的优先队列式分支限界法用一极小堆极小堆来存储来存储活结点表。其优先级是结点所对应的当前路长。活结点表。其优先级是结点所对应的当前路长。 算法从图算法从图G G的源顶点的源顶点s s和空优先队列开始。结点和空优先队列开始。结点s s被扩被扩展后，它的儿子结点被依次插入堆中。此后，算法从展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点

19、当前扩展结点i i到顶点到顶点j j有边可达，且从源出发，途经有边可达，且从源出发，途经顶点顶点i i再到顶点再到顶点j j的所相应的路径的长度小于当前最优的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。队列为空时为止。 单源最短路径问题单源最短路径问题智能信息处理研究中心（RCIIP）Pan18 剪枝策略剪枝策略在算法扩展结点的过程中，一旦发现一个结点的在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找

20、到的最短路长，则算法剪去以下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从在算法中，利用结点间的控制关系进行剪枝。从源顶点源顶点s s出发，出发，2 2条不同路径到达图条不同路径到达图G G的同一顶点。的同一顶点。由于两条路径的路长不同，因此可以将路长长的由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。路径所对应的树中的结点为根的子树剪去。 单源最短路径问题单源最短路径问题智能信息处理研究中心（RCIIP）Pan19 0-1背包问题背包问题 给定给定n n种物品和一背包。物品种物品和一背包。

21、物品i i的重量是的重量是w wi i，其价值为，其价值为v vi i，背包的容量为背包的容量为C C。问应如何选择装入背包的物品，使得装。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大入背包中物品的总价值最大? ? 输入：输入：C0, wi0, vi0, 1 in 输出：输出：(x1, x2, , xn), xi0, 1, 满足满足智能信息处理研究中心（RCIIP）Pan20 0-1背包问题背包问题 FIFO队列式分支限界法的基本思想 实例实例 n=3n=3，C=30C=30，w=16w=16，1515，1515，p=45p=45，2525，2525可行性约束函数：可行性约束函数

22、：P=45P=45 P=50P=50P=25P=25 P=25P=25P=0P=0AB,CE,F,GFIFO队列队列K,L,M,N,O智能信息处理研究中心（RCIIP）Pan21结点的优先级结点的优先级由已装袋的物品价值加上剩下的最大单由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的算法首先检查当前扩展结点的左儿子结点的可行性可行性。如果该左儿子结点是可行结点如果该左儿子结点是可行结点，则将它加入到子集树和，则将它加入到子集树和活结点优先队列中。活结点优先队列中。当前扩展结点的右儿子结点一定是可

23、行结点当前扩展结点的右儿子结点一定是可行结点，仅当右儿，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。队列。当扩展到叶节点时为问题的最优值。 0-1背包问题背包问题 优先队列式分支限界法的基本思想优先队列式分支限界法的基本思想首先，要对输入数据进行预处理，将各物品依其单位首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。重量价值从大到小进行排列。智能信息处理研究中心（RCIIP）Pan22 0-1背包问题背包问题 优先队列式分支限界法的基本思想 实例实例 n=3n=3，C=30

24、C=30，w=16w=16，1515，1515，p=45p=45，2525，2525 使用最大堆使用最大堆 上界上界 up = 68.38 Bound(int i)实现实现下界下界 L = 45 贪心算法实现贪心算法实现 bestp为当前最优值，则为当前最优值，则 L=45 bestp up=68.38智能信息处理研究中心（RCIIP）Pan23 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, l

25、evel=450,4568.38,4568.38,4550,45B, level=2C, level=2C, level=2E, level=3F, level=3K, level=4L, level=4智能信息处理研究中心（RCIIP）Pan24 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背包问题背包问题 分支限界搜索过程分支限界搜索过程智能信息处理研究中心（RCIIP）Pan25 0-1背包问题背包问题 分支限界搜索过程分支限界搜索过程 实例实例 (1)(1)物品个数为物品个数为 n=4n=4 (2)(2)背包的容量为背包的容量为 C=7C=7 (3)(3)物品的重量分别为物品的重量分别为 w=3w=3，5 5，2 2，11 (4

27、)(4)物品的价值分别为物品的价值分别为 p=9p=9，1010，7 7，44智能信息处理研究中心（RCIIP）Pan26 装载问题装载问题有一批共有一批共n n个集装箱要装上个集装箱要装上2 2艘载重量分别为艘载重量分别为c c1 1和和c c2 2的轮船，的轮船，其中集装箱其中集装箱i i的重量为的重量为w wi i，且，且装载问题装载问题确定是否有一个合理的装载方案可将这确定是否有一个合理的装载方案可将这n n个集装箱装上这个集装箱装上这2 2艘艘轮船。如果有，找出一种装载方案。轮船。如果有，找出一种装载方案。容易证明，如果一个给定装载问题有解，则采用下面的策略容易证明，如果一个给定装载

28、问题有解，则采用下面的策略可得到最优装载方案。可得到最优装载方案。(1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。智能信息处理研究中心（RCIIP）Pan27 队列式分支限界法队列式分支限界法 在算法的在算法的whilewhile循环中，首先检测当前扩展结点的左儿子循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中中。然后将其右儿子结点加入到活结点队列中( (右儿子结右儿子结点一定是

29、可行结点点一定是可行结点) )。2 2个儿子结点都产生后，当前扩展个儿子结点都产生后，当前扩展结点被舍弃。结点被舍弃。 装载问题装载问题智能信息处理研究中心（RCIIP）Pan28while (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); / 取下一扩展结点取下一扩展结点 装载问题装载问题 队列式分支限界法智能信息处理研究中心（

30、RCIIP）Pan29 装载问题装载问题 算法的改进算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。此集装箱装上船。设设bestwbestw是当前最优解；是当前最优解；ewew是当前扩展结点所相应的重量；是当前扩展结点所相应的重量；r r是剩余集装箱的重量。则当是剩余集装箱的重量。则当ew+rew+r bestwbestw时，可将其右子时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进另外，为了

31、确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新入左子树的时候更新bestwbestw的值。的值。智能信息处理研究中心（RCIIP）Pan30/ 检查左儿子结点检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列加入活结点队列 if (i bestw & i n) Q.Add(Ew); / 可能含最优解可能含最优解 Q.Delete(Ew); / 取下一扩展结点取下一扩展结点右儿子剪枝右儿子剪枝 装载问题装载问题 算法的改进智能信息处理研究中心（RCIIP）Pan31

32、装载问题装载问题 构造最优解构造最优解为了在算法结束后能方便地构造出与最优值相应的最为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。点的指针，并设置左、右儿子标志。找到最优值后，可以根据找到最优值后，可以根据parentparent回溯到根节点，找到回溯到根节点，找到最优解。最优解。 智能信息处理研究中心（RCIIP）Pan32 装载问题装载问题 优先队列式分支限界法优先队列式分支限

33、界法解装载问题的优先队列式分支限界法用最大优先队列解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点存储活结点表。活结点x x在优先队列中的优先级定义在优先队列中的优先级定义为从根结点到结点为从根结点到结点x x的路径所相应的载重量再加上剩的路径所相应的载重量再加上剩余集装箱的重量之和。余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中优先级最大的活结点成为下一个扩展结点。以结点以结点x x为根的子树中所有结点相应的路径的载重量为根的子树中所有结点相应的路径的载重量不超过它的优先级。不超过它的优先级。在优先队列式分支限界法中，一旦有一个叶结点成为在优

34、先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。最优解。此时可终止算法。 智能信息处理研究中心（RCIIP）Pan33 旅行售货员问题旅行售货员问题 问题描述问题描述给定给定n n个顶点的带权图个顶点的带权图G=(V, E),G=(V, E),图中各边的权为正数，图图中各边的权为正数，图中的中的一条周游路线一条周游路线是包括是包括V V中的每个顶点在内的一条回路，中的每个顶点在内的一条回路，一条周游路线的费用一条周游路线的费用是这条路线上所有边的权之和。是这条路线上所有边的权之和。 旅

35、行商问题旅行商问题( (Traveling Salesperson) )是要在图是要在图G G中找出一中找出一条有最小费用的周游路线。此问题是条有最小费用的周游路线。此问题是NPNP完全问题。完全问题。智能信息处理研究中心（RCIIP）Pan34 旅行售货员问题旅行售货员问题 实例FIFO队列式AB1C2F3L4G4M3DH2N4I4O2EJ2P3K3Q2341342306105420C,D,EC,D,EF,G,H,I,J,KF,G,H,I,J,KB BL,M,N,P,QL,M,N,P,Q5959666625252626智能信息处理研究中心（RCIIP）Pan35 旅行售货员问题旅行售货员问题 实例优先队列式(1)AB1C2DH2N4EJ2K3341342306105420E 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,C智能信息处理研究中心（RCIIP）Pan36 旅行售货员问题旅行售货员问题 实例优先队列式(2)1342306105420AB1C2DH2N4EJ2P3K33425252525I4智能信息处理研究中心（RCIIP）Pan37 旅行售