算法设计： 五、分支界限法（1. 旅行售货员问题）—— C++实现 - 算法分析

分支界限法

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树，裁剪那些不能得到最优解的子树以提高搜索效率。

分支界限法解题的一般思路：

（1）分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约
束条件的解中找出在某种意义下的最优解。
（2）搜索方式：以广度优先或以最小耗费优先的方式搜索解空间树。分支限
界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
（3）在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一
旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可
行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
（4）此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩
展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

旅行售货员问题

某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要
选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总
旅费）最小。

求解思想：

旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图 G 中找出费用最小的周游路线。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括 V 中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。

在具体实现时，用邻接矩阵表示所给的图G。在类Traveing中用二维数组a存储图G的邻接矩阵。

template <class Type>
class Traveling
{
public:Type BBTSP(int *v, Type **, int, Type);
private:Type **a,                                   //图G的邻接矩阵NoEdge;                                //图G的无边标志int n;                                      //图G的顶点数
};

要找最小费用旅行售货员回路，选用最小堆表示活结点优先队列。最小堆中元素的类型为MinHeapNode。该类型结点包含域x，用于记录当前解；s表示结点在排列树中的层次，从排列树的根结点到该结点的路径为x[0:s]，需要进一步搜索的顶点是x[s+1:n-1]。cc表示当前费用，lcost是子树费用的下界，rcost是x[x:n-1]中顶点最小出边费用和。

//队列中元素类型
template <class Type>
class MinHeapNode
{template <class T>friend class Traveling;
public:bool operator < (const MinHeapNode &MH) const{return lcost > MH.lcost;}
private:Type rcost,                                 //x[s:n-1]中顶点最小出边费用和lcost,                                 //子树费用的下界cc;                                    //当前费用int s,                                      //根结点到当前结点的路径为x[0:s]*x;                                     //需要进一步搜索的顶点是x[s+1:n-1]
};

算法开始时创建一个最小堆，表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的Minout作算法初始化。算法的第一个扩展结点是排列树中根结点的唯一儿子结点。在该结点处，已确定的回路中唯一顶点为顶点1.初始时有s=0,x[0]=1,x[1:n-1]=(2,3,…,n),cc=0且 rcost = \sum_{j=s}^{n}Minout[i]，算法中用bestc记录当前最优值。

template <class Type>
Type Traveling<Type>::BBTSP(int *v, Type **G, int tn, Type tNoEdge)
{priority_queue<MinHeapNode<Type> > pq;MinHeapNode<Type> E, N;Type bestc, cc, rcost, MinSum, *MinOut, b;int i, j;a = G;n = tn;NoEdge = tNoEdge;MinSum = 0;                                             //最小出边费用和MinOut = new Type[n+1];                                 //计算MinOut[i]=顶点i的最小出边费用for(i = 1; i <= n; i++){MinOut[i] = NoEdge;for(j = 1; j <= n; j++)if(a[i][j] != NoEdge && (a[i][j] < MinOut[i] || MinOut[i] == NoEdge))MinOut[i] = a[i][j];if(MinOut[i] == NoEdge)                             //无回路return NoEdge;MinSum += MinOut[i];}//初始化E.s = 0;E.cc = 0;E.rcost = MinSum;E.x = new int[n];for(i = 0; i < n; i++)E.x[i] = i+1;bestc = NoEdge;//搜索排列空间树while(E.s < n-1)                                        //非叶结点{if(E.s == n-2)                                      //当前扩展结点是叶结点的父结点 再加2条边构成回路{                                                   //所构成回路是否优于当前最优解if(a[E.x[n-2]][E.x[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]][1];E.cc = bestc;E.lcost = bestc;E.s++;pq.push(E);}elsedelete []E.x;                               //舍弃扩展结点}else                                                //产生当前扩展结点儿子结点{for(i = E.s+1; i < n; i++)if(a[E.x[E.s]][E.x[i]] != NoEdge){//可行儿子结点cc = E.cc + a[E.x[E.s]][E.x[i]];        //当前费用rcost = E.rcost - MinOut[E.x[E.s]];     //更新最小出边费用和b = cc + rcost;                         //下界if(b < bestc || bestc == NoEdge)        //子树可能含最优解 结点插入最小堆{N.s = E.s + 1;N.cc = cc;N.lcost = b;N.rcost = rcost;N.x = new int[n];for(j = 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];pq.push(N);                         //加入优先队列}}delete []E.x;                                   //完成结点扩展}if(pq.empty())                                      //堆已空break;E = pq.top();                                       //取下一扩展结点pq.pop();}if(bestc == NoEdge)                                     //无回路return NoEdge;for(i = 0; i < n; i++)                                  //将最优解复制到v[1:n]v[i+1] = E.x[i];while(pq.size())                                        //释放最小堆中所有结点{E = pq.top();pq.pop();delete []E.x;}return bestc;
}