旅行商售货员问题的分支限界算法姓名：学号：一、实验目的与要求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//两个城市之间费用的最大值//---------------------全局变量------
