旅行售货员问题c源代码及运行结果

1、源代码：#include <stdio.h>#include <malloc.h>#define noedge 1000struct minhe叩nodeint lcost; /子树费用的下界int cc;当前费用int rcost; /xs:n-l j中顶点最小出边费用和int s; 根节点到肖前节点的路径为x0:s int *x; 需要进一步搜索的顶点是xs+ l:n-l struct minheapnode *next;1；intn;/图g的顶点数int *a; 图g的邻接矩阵/int noedge; /图g的无边标记int cc;当前费用int bestc; /

2、当前最小费用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

3、insertcminheapnode* hn)if(head->next = null)head->next = hn; 将元素放入链表屮 fq = lq = head->next; 一定要使元素放到链中elseminheapnode *tmp = null;tmp = fq;if(tmp->cc > hn->cc)hn->next = tmp;head->next = hn;fq = head->next; /*链表只有一个元素的情况*/ elsefor(; tmp != null;)if(tmp->next != null &am

4、p;& lmp>cc > hn->cc) hn->next = tmp->next;tmp->next = hn;break;tmp = tmp->next;if(tmp = null)lq->next = hn;iq = lq>n ext;return 0;1int bbtsp(int v)解旅行售货员问题的优先队列式分支限界法/*初始化最优队列的头结点*/head = (minheapnode*)malloc(sizeof(minheapnode); head->cc = 0;head->x = 0;head->

5、;lcost = 0;head->next = null;head->rcost = 0;head->s = 0;int *minout = new intn + 1; /*定义定点i的最小出边费用*/ 计算minoutlij=顶点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 <

6、min | min = noedge) /*当顶点 i,j 之间的距离小于 min*/min = alijijj;/*更新当前最小值*/if(min = noedge)return noedge;/无回路 minouti = min; /*顶点i的最小出边费用*/ minsum +二min; /*最小111边费用的总和*/minheapnode 水e = 0;e = (minheapnode*)malloc(sizeof(minheapnode);e->x = new inlfn;/ e.x=new intn;for(i = 0; i < n; i+)e->xi = i +

7、1;e->s = 0;e->cc = 0;e->rcost = minsum;e->next = 0; 初始化当前扩展节点int bestc = noedge; /*记录当前最小值*/搜索排列空间树while(e->s v n 1)/非叶结点if(e->s = n - 2)/当前扩展结点是叶结点的父结点if(ae->xn2e->xfn1 != noedge && /*当前要扩展和叶节点有边存在*/ ae->xn - 1川1 != noedge &&/*当前页节点有冋路*/(e->cc + ae->

8、xn - 2e->xn - 1 + ae->xn - 11 < bestc /*该节点相 应费用小于最小费用*/| bestc = noedge)bestc = e->cc + ae->xfn - 2e->xn - 1 + ae->xn - 11; /*更新当前最 新费用勺e->cc = bestc;e->lcost = bestc;e>s+;e->next = null;insert(e); /*将该页节点插入到优先队列中*/elsefree(e->x);/该页节点不满足条件舍弃扩展结点else/产生当前扩展结点的儿子结

9、点for(i = e->s + 1; i < n; i+)if(ae->xe->se->xi != noedge) /*当前扩展节点到其他节点有边存在*/可行儿子结点int cc = e->cc + ae->xle->s川/*加上节点i后当前节点路径*/int rcost = e->rcost minoute->xe->s; /*剩余节点的和*/ int b = cc + rcost; 下界if(b < bestc | bestc = noedge)/子树可能含最优解，结点插入最小堆minheapnode * n;n =

10、(minheapnode*)malloc(sizeof(minheapnode);n->x = new intn;for(int j = 0; j < n; j+)n->xj = e->xu;n->xe->s + 1 = e->xil;n->xi = e->xe->s + 1;/* 添加当前路径 */n->cc = cc; /*更新当前路径距离*/n->s = e->s + 1;/*更新当前节点*/n->lcost = b; /*更新当前下界*/n> rcost = rcost;n->next =

11、null;insert(n); /*将这个可行儿子结点插入到活结点优先队列中*/free(e->x);完成结点扩展deletemin(e);取下一扩展结点if(e = null)break; /堆己空if(bestc = noedge)retum noedge;/无回路for(i = 0; i < n; i+)vi + 1 = e>xi;将最优解复制到vl:nwhile(true)释放最小堆小所有结点free(e->x);deletemin(e);if(e = null)break;return bestc;int mab-on£int i npscanf(=%d j <&n)ia n (inr*)maloc(sizeof(im*) * (n + 1)八 for(i h 1 二 ch n; i+)a 三 h (ihs*ma=oc(sizeof(int)*n + 1)；一for(i h 1 二 ah n； i+)or(int j h 1二 ch n二+)scanf(=%dj <&a三三)；-一 prev h (ints*maloc(s