算法设计与分析 课件 8.4-分支限界 - 典型应用 - 旅行售货员问题

算法设计与分析分支限界—旅行售货员问题信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总的路程（或总旅费）最小。问题抽象：设G=(V,E)是一个带权图。图中各边的权值为正数。图中一条周游路线是包括V中每个顶点在内的一条回路。周游路线的费用是这条回路上所有边的权值之和。旅行售货员问题就是要在图G中找出费用最小的回路。1243302010654实例分析：

优先队列：

小根堆，用于表示活结点优先队列

优先级=下界lcostlcost=cc+顶点的最小费用出边和(未来最小的花费)12433020106544+5+5+4=180,0,18B4I2,26,9BCDEC21,30,14bestc：bestx：∞C3D1,6,14DCE41,4,141243302010645EDCEDCJ2J2,14,10DJCK3K2,24,10DJKCHH22,11,925DJKCHJKCIHJKICHJKIC4N3,25,0NJNKICH为n-2层结点18=4+5+5+414=5+5+4扩展结点活结点优先队列最优解树中结点的信息：结点深度，已花费代价，未来花费代价的下界NICJNKIC0,0,18B4I2,26,9C21,30,14bestc：bestx：3D1,6,14E41,4,142J2,14,103K2,24,10H22,11,9251,3,2,4H4N3,25,0NJ3P3,25,0PNICN为叶子，结束扩展结点活结点优先队列最优解1243302010645树中结点的信息：结点深度，已花费代价，未来花费代价的下界输入：图结点数n，图邻接矩阵a[][]输出：最优值bestc，最优解v[]1BBTSP(){2若图中存在没有出边的结点，则退出;3计算各顶点最小出边和MinSum;4定义最优值bestc=∞;5创建根结点E,令其s=0,cc=0,lcost=cc+MinSum,6x={1,2,…,n};7while(E不是叶结点){//遇到叶子时结束8

if(E是叶子的父结点){//E的层次为n-29c=E->cc+a[E->x[n-2]][E->x[n-1]]+10a[E->x[n-1]][1];11if(c<bestc){12bestc=c;改造E为扩展的叶结点,13E->s++,E->cc=bestc;E入队;14}15else释放E;16}17else{//扩展E的儿子结点18

for(i=E->s+1;i<=n-1;i++){19cc=E->cc+a[E->x[E->s]][E->x[i]];20lcost=cc+E->lcost-MinOut[E->x[E->s]];21if(lcost<bestc){22申请结点N;把E中x复制到N;23N->s=E->s+1;交换N->x[N->s]与N->x[i];

24N->cc=cc;N->lcost=lcost;25N入队;}26}27释放E;28}29从队列取下一个扩展结点E;30if(E不存在)break;31}32if(bestc==∞)return∞;//无回路33从E中复制x到解v中；34释放E及优先队列中剩余结点;35returnbestc;}测试填空题：针对上述