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

分支限界法旅行售货员问题（TSP）6.1 分支限界法的基本思想6.1 分支限界法的基本思想6.1 分支限界法的基本思想旅行售货员问题（TSP）问题陈述:
旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。
即：
设G(V,E)是一带权有向图,V={1,2,…n},其耗费矩阵C=(ci,j)，当(i,j)E时,记ci,j=且ci,j=.问如何选择周游路线使耗费最小？算法思路:设周游路线从结点1开始,解为等长数组X=(1,x2,...xn)
xi{2,...,n}.则解空间树为排列树，在树中做广度优先搜索。
约束条件:xixj,ij;
目标函数:解向量对应的边权之和∑Cij
目标函数限界初值:U=优先队列式分支限界法用极小堆存储活结点表{}；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{}.算法的while循环体完成对排列树内部结点的扩展。

对于当前扩展结点，算法分2种情况进行处理：
①首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。
②当s<n-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x[0:s]，其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。当lcost<bestc时，将这个可行儿子结点插入到活结点优先队列中。算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x[0:n-1]，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到叶结点所相应的回路是一个最小费用旅行售货员回路，算法可结束。
算法结束时返回找到的最小费用，相应的最优解由数组v给出。while(E.s<n-1){//非叶结点
if(E.s==n-2){//当前扩展结点是叶结点的父结点
//再加2条边构成回路所构成回路是否优于当前最优解
if(a[E.x[n-2]][E.[n-1]]!=NoEdge&&a[E.x[n-1]][1]!=NoEdge&&(E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]
<bestc||bestc==NoEdge)){//费用更小的回路
bestc=E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]];
E.cc=bestc;
E.lcost=bestc;
E.s++;
H.Insert(E);}
elsedelete[]E.x;}//舍弃扩展结点
else{//产生当前扩展结点的儿子结点
for(inti=E.s+1;i<n;i++)
if(a[E.x[E.s]][E.x[i]]!=NoEdge){
//可行儿子结点
Typecc=E.cc+a[E.x[E.s]][E.x[i]];
Typercost=E.rcost-MinOut[E.x[E.s]];
Typeb=cc+rcost;//下界if(b<bestc||bestc==NoEdge){//子树可能含最优解,结点插入最小堆
MinHeapNode<Type>N;
N.x=newint[n];
for(intj=0;j<n;j++)
N.x[j]=E.x[j];
N.x[E.s+1]=E.x[i];
N.x[i]=E.x[E.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)returnNoEdge;//无回路
for(i=0;i<n;i++)v[i+1]=E.x[i];//将最优解复制到v[1:n]
while(true){//释放最小堆中所有结点
delete[]E.x;
try{H.DeleteMin(E);}catch(OutOfBounds){break;}}
returnb