欢迎来到天天文库
浏览记录
ID:8149823
大小:68.50 KB
页数:6页
时间:2018-03-07
《旅行商售货员问题分支限界算法》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、旅行商售货员问题的分支限界算法姓名:学号:一、实验目的与要求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的值。代码:#include#includeusingnamespacestd;//---------------------宏定义------------------------------------------#defineMAX_CITY_NUMBER10//城市最大数目#defineMAX_COST10000000//两个城市之间费用的最大值//--------------------
4、-全局变量----------------------------------------intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市间边权重的数组intCity_Size;//表示实际输入的城市数目intBest_Cost;//最小费用intBest_Cost_Path[MAX_CITY_NUMBER];//最小费用时的路径//------------------------定义结点---------------------------------------type
5、defstructNode{intlcost;//优先级intcc;//当前费用intrcost;//剩余所有结点的最小出边费用的和ints;//当前结点的深度,也就是它在解数组中的索引位置intx[MAX_CITY_NUMBER];//当前结点对应的路径structNode*pNext;//指向下一个结点}Node;//---------------------定义堆和相关对操作--------------------------------typedefstructMiniHeap{Node*pHead;//堆的头}MiniHe
6、ap;//初始化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.lcos
7、t;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(
8、(next->lcost)>(pinnode->lcost)){//发现一个优先级大的,则置于其前面pinnode->pNext=pre->pNext;pre->pNext=pinnode;break;//跳出}pre=next;ne
此文档下载收益归作者所有