旅行商售货员问题的分支限界算法

旅行商售货员问题的分支限界算法姓名：学号：一、实验目的与要求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的值。代码：#includestdio.h#includeistreamusingnamespacestd;//---------------------宏定义------------------------------------------#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;kCity_Size;k++){pinnode-x[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;iCity_Size;i++){miniOut[i]=MAX_COST;//初始化时每一个结点都不可达for(j=0;jCity_Size;j++){if(City_Graph[i][j]0&&City_Graph[i][j]miniOut[i]){//从i到j可达，且更小miniOut[i]=City_Graph[i][j];}}if(miniOut[i]==MAX_COST){//i城市没有出边Best_Cost=-1;return;}miniSum+=miniOut[i];}for(i=0;iCity_Size;i++){//初始化的最优路径就是把所有结点依次走一遍Best_Cost_Path[i]=i;}Best_Cost=MAX_COST;//初始化的最优费用是一个很大的数pNode=newNode;//初始化第一个结点并入堆pNode-lcost=0;//当前结点的优先权为0也就是最优pNode-cc=0;//当前费用为0（还没有开始旅行）pNode-rcost=miniSum;//剩余所有结点的最小出边费用和就是初始化的miniSumpNode-s=0;//层次为0pNode-pNext=NULL;for(intk=0;kCity_Size;k++){pNode-x[k]=Best_Cost_Path[k];//第一个结点所保存的路径也就是初始化的路径}put(heap,*pNode);//入堆while(pNode!=NULL&&(pNode-s)City_Size-1){//堆不空不是叶子for(intk=0;kCity_Size;k++){Best_Cost_Path[k]=pNode-x[k];//将最优路径置换为当前结点本身所保存的}/***pNode结点保存的路径中的含有这条路径上所有结点的索引**x路径中保存的这一层结点的编号就是x[City_Size-2]**下一层结点的编号就是x[City_Size-1]*/if((pNode-s)==City_Size-2){//是叶子的父亲intedge1=City_Graph[(pNode-x)[City_Size-2]][(pNode-x)[City_Size-1]];intedge2=City_Graph[(pNode-x)[City_Size-1]][(pNode-x)[0]];if(edge1=0&&edge2=0&&(pNode-cc+edge1+edge2)Best_Cost){//edge1-1表示不可达//叶子可达起点费用更低Best_Cost=pNode-cc+edge1+edge2;pNode-cc=Best_Cost;pNode-lcost=Best_Cost;//优先权为Best_CostpNode-s++;//到达叶子层}}else{//内部结点for(i=pNode-s;iCity_Size;i++){//从当前层到叶子层if(City_Graph[pNode-x[pNode-s]][pNode-x[i]]=0){//可达//pNode的层数就是它在最优路径中的位置inttemp_cc=pNode-cc+City_Graph[pNode-x[pNode-s]][pNode-x[i]];inttemp_rcost=pNode-rcost-miniOut[pNode-x[pNode-s]];//下一个结点的剩余最小出边费用和//等于当前结点的rcost减去当前这个结点的最小出边费用if(temp_cc+temp_rcostBest_Cost){//下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解for(j=0;jCity_Size;j++){//完全copy路径，以便下面修改temp_x[j]=Best_Cost_Path[j];}temp_x[pNode-x[pNode-s+1]]=Best_Cost_Path[i];//将当前结点的编号放入路径的深度为s+1的地方temp_x[i]=Best_Cost_Path[pNode-s+1];//??????????????//将原路//径中的深度为s+1的结点编号放入当前路径的//相当于将原路径中的的深度为i的结点与深度W为s+1的结点交换Node*pNextNode=newNode;pNextNode-cc=temp_cc;pNextNode-lcost=temp_cc+temp_rcost;pNextNode-rcost=temp_rcost;pNextNode-s=pNode-s+1;pNextNode-pNext=NULL;for(intk=0;kCity_Size;k++){pNextNode-x[k]=temp_x[k];}put(heap,*pNextNode);deletepNextNode;}}}}pNode=RemoveMiniHeap(heap);}}intmain(){inti,j;printf(请输入旅行的节点数);scanf(%d,&City_Size);for(i=0;iCity_Size;i++){printf(请分别输入每个节点与其它节点的路程花费);for(j=0;jCity_Size;j++){scanf(%d,&City_Graph[i][j]);}}Traveler();printf(最小花费%d\n,Best_Cost);return1;}运行结果：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界