旅行商售货员问题的分支限界算法姓名：学号：一、实验目的与要求1、掌握旅行商售货员问题的分支限界算法；2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。二、实验题：编程实现：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。三、实验提示旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。以下为第一种方法。由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域：x（从1到n的整数排列，其中x[0]=1），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s],而剩余待访问的节点是x[s+1:n-1]），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费），rcost（从顶点x[s:n-1]出发的所有边的最小耗费之和）。当类型为MinHeapNode(T)的数据被转换成为类型T时，其结果即为lcost的值。代码：#include#includeusingnamespacestd;//---------------------宏定义------------------------------------------#defineMAX_CITY_NUMBER10//城市最大数目#defineMAX_COST10000000//两个城市之间费用的最大值//---------------------全局变量----------------------------------------intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市间边权重的数组intCity_Size;//表示实际输入的城市数目intBest_Cost;//最小费用intBest_Cost_Path[MAX_CITY_NUMBER];//最小费用时的路径//------------------------定义结点---------------------------------------typedefstructNode{intlcost;//优先级intcc;//当前费用intrcost;//剩余所有结点的最小出边费用的和ints;//当前结点的深度，也就是它在解数组中的索引位置intx[MAX_CITY_NUMBER];//当前结点对应的路径structNode*pNext;//指向下一个结点}Node;//---------------------定义堆和相关对操作--------------------------------typedefstructMiniHeap{Node*pHead;//堆的头}MiniHeap;//初始化voidInitMiniHeap(MiniHeap*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=node.pNext;pinnode->rcost=node.rcost;pinnode->s=node.s;pinnode->pNext=NULL;for(intk=0;kx[k]=node.x[k];}pre=pMiniHeap->pHead;next=pMiniHeap->pHead->pNext;if(next==NULL){pMiniHeap->pHead->pNext=pinnode;}else{while(next!=NULL){if((next->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=pMiniHeap->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_NUMBER];//保存每个结点的最小出边的索引MiniHeap*heap=newMiniHeap;//分配堆InitMiniHeap(heap);//初始化堆miniSum=0;for(i=0;i
