旅行售货员问题(优先队列式分支限界法).doc

#include #include #define NoEdge 1000struct MinHeapNodeint lcost; /子树费用的下界int cc; /当前费用int rcost; /xs:n-1中顶点最小出边费用和int s; /根节点到当前节点的路径为x0:sint *x; /需要进一步搜索的顶点是/xs+1:n-1struct MinHeapNode *next;int n; /图G的顶点数int *a; /图G的邻接矩阵/int NoEdge; /图G的无边标记int cc; /当前费用int bestc; /当前最小费用MinHeapNode* head = 0; /*堆头*/MinHeapNode* lq = 0; /*堆第一个元素*/MinHeapNode* fq = 0; /*堆最后一个元素*/int DeleteMin(MinHeapNode*&E)MinHeapNode* tmp = NULL;tmp = fq;/ w = fq-weight ;E = fq;if(E = NULL) return 0;head-next = fq-next; /*一定不能丢了链表头*/fq = fq-next;/ free(tmp) ;return 0;int Insert(MinHeapNode* hn)if(head-next = NULL) head-next = hn; /将元素放入链表中 fq = lq = head-next; /一定要使元素放到链中else MinHeapNode *tmp = NULL; tmp = fq; if(tmp-cc hn-cc) hn-next = tmp; head-next = hn; fq = head-next; /*链表只有一个元素的情况*/ else for(; tmp != NULL;) if(tmp-next != NULL & tmp-cc hn-cc) hn-next = tmp-next; tmp-next = hn; break; tmp = tmp-next; if(tmp = NULL) lq-next = hn; lq = lq-next; return 0;int BBTSP(int v)/解旅行售货员问题的优先队列式分支限界法/*初始化最优队列的头结点*/head = (MinHeapNode*)malloc(sizeof(MinHeapNode);head-cc = 0;head-x = 0;head-lcost = 0;head-next = NULL;head-rcost = 0;head-s = 0;int *MinOut = new intn + 1; /*定义定点i的最小出边费用*/计算MinOuti=顶点i的最小出边费用int MinSum = 0;/最小出边费用总合for(int i = 1; i = n; i+) int Min = NoEdge; /*定义当前最小值*/ for(int j = 1; j = n; j+) if(aij != NoEdge & /*当定点i,j之间存在回路时*/ (aij x = new intn;/ E.x=new intn;for(i = 0; i xi = i + 1;E-s = 0;E-cc = 0;E-rcost = MinSum;E-next = 0; /初始化当前扩展节点int bestc = NoEdge; /*记录当前最小值*/搜索排列空间树while(E-s s = n - 2) /当前扩展结点是叶结点的父结点 /* 首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路 且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点 */ if(aE-xn - 2E-xn - 1 != NoEdge & /*当前要扩展和叶节点有边存在*/ aE-xn - 11 != NoEdge & /*当前页节点有回路*/ (E-cc + aE-xn - 2E-xn - 1 + aE-xn - 11 cc + aE-xn - 2E-xn - 1 + aE-xn - 11; /*更新当前最新费用*/ E-cc = bestc; E-lcost = bestc; E-s+; E-next = NULL; Insert(E); /*将该页节点插入到优先队列中*/ else free(E-x);/该页节点不满足条件舍弃扩展结点 else /*产生当前扩展结点的儿子结点 当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s， 其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。 对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。 当lcosts + 1; i xE-sE-xi != NoEdge) /*当前扩展节点到其他节点有边存在*/ /可行儿子结点 int cc = E-cc + aE-xE-sE-xi; /*加上节点i后当前节点路径*/ int rcost = E-rcost - MinOutE-xE-s; /*剩余节点的和*/ int b = cc + rcost; /下界 if(b x = new intn; for(int j = 0; j xj = E-xj; N-xE-s + 1 = E-xi; N-xi = E-xE-s + 1;/*添加当前路径*/ N-cc = cc; /*更新当前路径距离*/ N-s = E-s + 1; /*更新当前节点*/ N-lcost = b; /*更新当前下界*/ N-rcost = rcost; N-next = NULL; Insert(N); /*将这个可行儿子结点插入到活结点优先队列中*/ free(E-x); /完成结点扩展 DeleteMin(E);/取下一扩展结点 if(E = NULL) break; /堆已空if(bestc = NoEdge) return NoEdge;/无回路for(i = 0; i xi;/将最优解复制到v1:nwhile(true)/释放最小堆中所有结点 free(E-x); DeleteMin(E); if(E = NULL) break;return bestc;int main()n = 0;int i = 0;FILE *in, *out;in = fopen(input.txt, r);out = fopen(output.txt, w);if(in = NULL | out = NULL) printf(没有输入输出文件n); return 1;fscanf(in, %d, &n);a = (int*)malloc(sizeof(int*) * (n + 1);for(i = 1; i = n; i+) ai = (int*)malloc(sizeof(int) * (n + 1);for(i = 1; i = n; i+) for(int j = 1; j = n; j+) fscanf(in, %d, &aij);/ prev = (int*)malloc(sizeof(int)*(n+1) ;int*v = (int*)malloc(sizeof(int) * (n + 1);/ MaxLoading(w , c