分支限界法——TSP问题

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,分支限界法旅行售货员问题（TSP）,小燕子,1,6.1分支限界法的基本思想,1. 分支限界法与回溯法的不同,（1）求解目标：,回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,（2）搜索方式的不同：,回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,2,6.1分支限界法的基本思想,2. 分支限界法基本思想,分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,3,6.1分支限界法的基本思想,3. 常见的两种分支限界法,（1）队列式(FIFO)分支限界法,按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。,（2）优先队列式分支限界法,按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,最大优先队列：使用最大堆，体现最大效益优先,最小优先队列：使用最小堆，体现最小费用优先,4,旅行售货员问题（TSP）,某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。,该问题是一个NP完全问题， 有(n-1)!条可选路线 。,路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。,5,问题陈述,:,旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。,即：,设G(V,E)是一带权有向图,V=,1,2,n,其耗费矩阵C=(c,i,j,)，当(i,j),E时, 记 c,i,j,=,且c,i,j,=,.问如何选择周游路线使耗费最小？,TSP问题,6,算法思路,:设周游路线从结点1开始,解为等长数组X=(1,x,2,.x,n,),x,i,2,.,n.,则解空间树为排列树，在树中做广度优先搜索。,约束条件: x,i,x,j,i,j;,目标函数:解向量对应的边权之和C,ij,目标函数限界初值:U=,活结点队列：,C D E F G H,I J K,队列式分支限界法：,初始扩展结点为B，活结点队列为空。,7,C =,30,11,4,26,6,25,14,59,25,24,算法描述：,算法开始时创建一个最小堆，用于表示活结点优先队列,堆中每个结点的子树费用的下界lcost值是优先队列的优先级。,接着算法计算出图中每个顶点的最小费用出边并用minout记录。,如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。,如果每个顶点都有出边，则根据计算出的minout作算法初始化。,8,优先队列式分支限界法用极小堆存储活结点表,E,4,6,D,C,30,B被,扩展后，它的三个儿子结点C,D,E被依次插入堆中,D,6,C,30,D,6,C,30,J,K,14,24,E被,扩展后，它的儿子结点J,K被依次插入当前堆中,J,14,C,30,K,24,H,J,14,30,K,24,11,I,26,C,K,H,11,30,J,14,24,I,26,C,D被,扩展后，它的儿子结点H,I被依次插入当前堆中,初始扩展结点为B，优先队列为空。,9,；,B,E,D,C；,E,D, J,K, C；,D,H,J,K,I,C；,H,J,K,I,C；,J,K,I,C；,K,I,C；,I,C；,C,.,K被,扩展后，得到可行解费用为59，高于当前最优解25,H被,扩展后，得到一条旅行售货员回路（1,3,2,4,1），相应的费用为25,结点I本身的费用已高于当前最优解，故没必要扩展结点I,I,J,14,30,K,24,26,C,J被,扩展后，得到另一条费用为25的回路（1,4,2,3,1）,K,24,26,I,C,30,I,26,C,30,C,30,0,结点C本身的费用也已高于当前最优解，故没必要扩展结点C,此时，优先队列为空，算法终止。,10,算法的while循环体完成对排列树内部结点的扩展。,对于当前扩展结点，算法分2种情况进行处理：,首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。,当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。,11,算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到叶结点所相应的回路是一个最小费用旅行售货员回路，算法可结束。,算法结束时返回找到的最小费用，相应的最优解由数组v给出。,12,while(E.s n - 1) /非叶结点,if(E.s = n - 2)/当前扩展结点是叶结点的父结点,/再加2条边构成回路 所构成回路是否优于当前最优解,if(aE.xn - 2E.n - 1 !=,NoEdge & aE.xn - 11 != NoEdge & (E.cc +aE.xn - 2E.xn - 1 + aE.xn - 11, bestc | bestc = NoEdge) /,费用更小的回路,bestc = E.cc + aE.xn - 2E.xn - 1 + aE.xn - 1;,E.cc = bestc;,E.lcost = bestc;,E.s+;,H.Insert(E); ,else deleteE.x; /,舍弃扩展结点,else /产生当前扩展结点的儿子结点,for(int i = E.s + 1; i n; i+),if(aE.xE.sE.xi != NoEdge) ,/可行儿子结点,Type cc = E.cc + aE.xE.sE.xi;,Type rcost = E.rcost - MinOutE.xE.s;,Type b = cc + rcost; /下界,13,if(b bestc | bestc = NoEdge) /子树可能含最优解,结点插入最小堆,MinHeapNode N;,N.x = new intn;,for(int j = 0; j n; j+),N.xj = E.xj;,N.xE.s + 1 = E.xi;,N.xi = E.xE.s + 1;,N.cc = cc;,N.s = E.s + 1;,N.lcost = b;,N.rcost = rcost;,H.Insert(N); ,delete E.x; /,完成结点扩展,/*,取下一扩展结点*,/,try H.DeleteMin(E); catch(OutOfBounds) break; /,堆已空,if(bestc = NoEdge) return NoEdge; /,无回路,for(i = 0; i n; i+) vi + 1 = E.xi; /,将最优解复制到,v1:n,while(true) /,释放最小堆中所有结点,delete E.x;,tryH.DeleteMin(E);catch(OutOfBounds)break; ,return bestc;,14,面试题1,有一根27厘米长的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米这五个位置上各有一只蚂蚁，木杆很细，不能同时通过两只蚂蚁，开始时，蚂蚁的头朝向左还是右是任意的，他们只会朝前走或掉头，但不会后退，当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走，假设蚂蚁们每秒钟可以走1厘米的距离. 求所有蚂蚁都离开木杆的最小时间和最大时间。,问题分析：,1.最小时间肯定是各自朝最近的一端跑，27-11=14，1123，所以最长时间是24。,15,算法：,1.找出中间的蚂蚁离两端的距离中较小的。,a2=11,a2=27-11=14,因为a2a2，所以最小距离是11，时间11/1=11,2.找出两端的蚂蚁距两端的距离中较大的。,a0=3,a0=27-3=24,a4=23,a4=27-23=4,这四个数中最大的是24,3.所以，最大时间24，最小时间11,16,程序：,public class Ant ,private static int LONG = 27;,private int a = 3, 7, 11, 17, 23 ;,private int min = 0, max = 0;,public void gogogo() ,for (int i = 0; i a.length; i+) ,min = Math.max(min, Math.min(ai, LONG - ai);,max = Math.max(max, Math.max(ai, LONG - ai);,public int getMax() return max; ,public int getMin() return min; ,public static void main(String args) ,Ant client = new Ant();,client.gogogo();,System.out.println(client.getMax();,System.out.println(client.getMin();,17,面试题2,猴子分桃,有5只猴子在海边发现一堆桃子,决定第二天来平分.第二天清晨,第一只猴子最早来到,它左分右分分不开,就朝海里扔了一只,恰好可以分成5份,它拿上自己的一份走了.第 2,3,4,5只猴子也遇到同样的问题,采用了同样的方法,都是扔掉一只后,恰好可以分成5份.问这堆桃子至少有多少只？,分析题目:,只要能求出每一个猴子当前桃子总数.最后就能求出最终结果. 还有一个问题就是从什么地方入手,是知道第一只猴子面前的总数还是最后一只猴子面前的总数.,再次假设:,1:知道第一只猴子面前的总数n.那么下一只猴子面前应该有(n - (n - 1)/5)个桃子.可以利用一个循环来实现n的值是否满足要求.,这是算法1.,2:如果知道最后一只猴子面前的总数n,那么上一只猴子面前应该有n/4 * 5 + 1个桃子.同样,也可以利用一个循环来验证满足条件的n值.这是算法2.,18,下面发算法2的代码: 结果为3121,.,#include ,void main( ) int Count = 1;,while (true) ,int i = 0;,int Temp = Count;,while (Temp % 5 = 0) & (Temp + 1) % 4 = 0) ,i+;,Temp = Temp + 1;,Temp = Temp / 4 * 5;,if (i = 4) ,Count = Temp + 1;,break;,if (i = 4) break; ,Count+;,printf(%d,Count);,getchar();,19,Thanks!,20,