分支限界法——TSP问题ppt课件.ppt

《分支限界法——TSP问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《分支限界法——TSP问题ppt课件.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、n问题陈述问题陈述: 设G(V,E)是一带权有向图,V=1,2,n ,其耗费矩阵C=(ci,j)，当(i,j) E时, 记 ci,j= 且ci,j= .问如何选择周游路线使耗费最小？ TSP问题算法思路算法思路:设周游路线从结点1开始,解为等长数组X=(1,x2,.xn) xi2,.,n.则解空间树为排列树，在树中做广度优先搜索。约束条件: xi xj ,i j;目标函数:解向量对应的边权之和Cij目标函数限界初值:U=201042056105304630C =301142662514592524算法描述：算法描述：算法开始时创建一个最小堆，用于表示活结点优先队列堆中每个结点的子树费用的下界l

2、cost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。 4630630630142414302414302411261130142426143024262426302630300算法的算法的whilewhile循环体完成对排列树内部结点的扩展。循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分对于当前扩展结点，算法分2 2种情况进行处理：种情况进行处理：首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父

3、结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。 算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图

4、G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到叶结点所相应的回路是一个最小费用旅行售货员回路，算法可结束。算法结束时返回找到的最小费用，相应的最优解由数组v给出。 while(E.s n - 1) /非叶结点if(E.s = n - 2)/当前扩展结点是叶结点的父结点/再加2条边构成回路 所构成回路是否优于当前最优解if(aE.xn - 2E.n - 1 != NoEdge & aE.xn - 11 != NoEdge &

5、 (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

6、.xi; Type rcost = E.rcost - MinOutE.xE.s; Type b = cc + rcost; /下界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;

7、/完成结点扩展 /*取下一扩展结点*/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;下面发算法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();