分支限界算法设计与应用

《分支限界算法设计与应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验七分支限界的应用一.基本原理的概括一个具体问题，其解决的方法可能有很多种，可采用各种不同的算法设计方法。二.该类算法设计与实现的要点熟练掌握各种算法设计方法三.实验目的和要求要求用分支限界以及至少i种其它算法求解旅行商问题，提高综合应用各种算法设计方法的能力。四.实验内容（分支限界算法&贪心算法）（一）旅行商问题一一分支限界算法:由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNodeo每个节

2、点包括如下区域：x（从1到n的整数排列,其中x[0]=1）,s（—个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s],而剩余待访问的节点是x[s+1:n・1]）,cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），Icost（该节点子树小任意叶节点小的最小耗费），most（从顶点x[s:n-1]出发的所有边的最小耗费之和）。当类型为MinHe叩Node（T）的数据被转换成为类型T时，其结果即为lcost的值。代码如下：#include#include

3、usingnamespacestd;//宏定义#defineMAX_CITY_NUMBER10//城市最大数目#defineMAX_COST10000000//两个城市之间费用的最大值//全局变量intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];〃表示城市间边权重的数组intCity_Size;〃表示实际输入的城市数目intBest_Cost;〃最小费用intBest_Cost_Path[MAX_CITY_NUMBER];〃最小费用时的路

4、径//定义结点typedefstructNode{intlcost;〃优先级intcc;〃当前费用intrcost;//剩余所有结点的最小出边费用的和ints;〃当前结点的深度，也就是它在解数组中的索引位置intx[MAX_CITY_NUMBER];〃当前结点对应的路径structNode*pNext;//指向卜一个结点}Node;//定义堆和相关对操作typedefstructMiniHeap{Node*pHead;〃堆的头[MiniHeap;〃初始化voidInitMiniHeap(MiniHea

5、p*pMiniHeap){pMiniHeap->pHead=newNode;pMiniHeap->pHead->pNext=NULL;}〃入堆voidput(MiniHeap*pMiniHeap.Nodenode){Node*next;Node*pre;Node*pinnode=newNode;//将传进来的结点信息copy一份保存〃这样在函数外部对node的修改就不会影响到堆了pinnode->cc=node.cc;pinnode->lcost=node.lcost;pinnode->pNext=n

6、ode.pNext;pinnode->rcost=node.rcost;pinnode->s=node.s;pinnode->pNext=NULL;for(intk=O;kx[kl=node.xfk];}pre=pMiniHeap->pHead;next=pMiniHeap->pHead->pNext;if(next==NULL){pMiniHeap->pHead->pNext=pinnode;elsewhile(next!=NULL)if((next

7、->lcost)>(pinnode->lcost))｛〃发现一个优先级大的，则置于其前面pinnode->pNext=pre->pNext;pre・>pNext=pinnode;break;〃跳出pre=next;next=next->pNext;}pre->pNext=pinnode;〃放在末尾}}〃出堆Node*RemoveMiniHeap(MiniHeap*pMiniHeap){Node*pnode=NULL;if(pMiniHeap->pHead->pNext!=NULL){pnode=pMi

8、niHeap->pHead->pNext;pMiniHeap->pHead->pNext=pMiniHeap->pHead->pNext->pNext;}returnpnode;}//分支限界法找最优解voidTraveler(){inti,j；inttemp_x[MAX_CITY_NUMBER];Node*pNode=NULL;intminiSum;〃所有结点最小出边的费用和intminiOut[MAX_CITY_NUMBERJ;〃保存每个结点的最小出