实验七 分支限界法.doc

《实验七 分支限界法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验七分支限界法（2学时）一、实验目的与要求1、掌握旅行商售货员问题的分支限界算法；2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。二、实验题：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。三、实验提示旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。以下

2、为第一种方法。由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域：x（从1到n的整数排列，其中x[0]=1），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s],而剩余待访问的节点是x[s+1:n-1]），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费），rcost（从顶点x[s:n-1]出发的所有

3、边的最小耗费之和）。当类型为MinHeapNode(T)的数据被转换成为类型T时，其结果即为lcost的值。分枝定界算法的代码见程序程序首先生成一个容量为100的最小堆，用来表示活节点的最小优先队列。活节点按lcost值从最小堆中取出。接下来，计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费MinOut。如果某些顶点没有出边，则有向图中没有旅行路径，搜索终止。如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜索。根的孩子B作为第一个E-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1，因此s=0,x[0]=

4、1,x[1:n-1]是剩余的顶点（即顶点2，3，.，n）。旅行路径前缀1的开销为0，即cc=0，并且，rcost=n&&i=1时MinOut。在程序中，bestc给出了当前能找到的最少的耗费值。初始时，由于没有找到任何旅行路径，因此bestc的值被设为NoEdge。旅行商问题的最小耗费分枝定界算法templateTAdjacencyWDigraph::BBTSP(intv[]){//旅行商问题的最小耗费分枝定界算法//定义一个最多可容纳1000个活节点的最小堆MinHeap>H(1000);T*MinOut=newT[n

5、+1];//计算MinOut=离开顶点i的最小耗费边的耗费TMinSum=0;//离开顶点i的最小耗费边的数目for(inti=1;i<=n;i++){TMin=NoEdge;for(intj=1;j<=n;j++)if(a[j]!=NoEdge&&(a[j]

6、

7、Min==NoEdge))Min=a[j];if(Min==NoEdge)returnNoEdge;//此路不通MinOut=Min;MinSum+=Min;}//把E-节点初始化为树根MinHeapNodeE;E.x=newint[n];for(i=0

8、;i

9、n-1]][1]

10、

11、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++;H.Insert(E);}elsedelete[]E.x;}else{//产生孩子for(inti=E.s+1;i

12、=E.rcost-MinOut[E.x[E.s]];Tb=cc+rcost;//下限if(b

13、

14、bestc==NoEdge){//子树可能有更好的叶子//把根保存到最大堆中MinHeapNodeN;N.x=newint[n];for(intj=0;j