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

《旅行售货员问题(优先队列式分支限界法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#defineNoEdge1000structMinHeapNode{intlcost;//子树费用的下界intcc;//当前费用intrcost;//x[s:n-1]中顶点最小出边费用和ints;//根节点到当前节点的路径为x[0:s]int*x;//需要进一步搜索的顶点是//x[s+1:n-1]structMinHeapNode*next;};intn;//图G的顶点数int**a;//图G的邻接矩阵//intNoEdge;//图G的无边

2、标记intcc;//当前费用intbestc;//当前最小费用MinHeapNode*head=0;/*堆头*/MinHeapNode*lq=0;/*堆第一个元素*/MinHeapNode*fq=0;/*堆最后一个元素*/intDeleteMin(MinHeapNode*&E){MinHeapNode*tmp=NULL;tmp=fq;//w=fq->weight;E=fq;if(E==NULL)return0;head->next=fq->next;/*一定不能丢了链表头*/fq=fq->next;//free

3、(tmp);return0;}intInsert(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->nex

4、t!=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;}}return0;}intBBTSP(intv[]){//解旅行售货员问题的优先队列式分支限界法/*初始化最优队列的头结点*/head=(MinHeapNode*)malloc(sizeof(MinHeapNode));head->cc=0;head->x=0;head->lc

5、ost=0;head->next=NULL;head->rcost=0;head->s=0;int*MinOut=newint[n+1];/*定义定点i的最小出边费用*///计算MinOut[i]=顶点i的最小出边费用intMinSum=0;//最小出边费用总合for(inti=1;i<=n;i++){intMin=NoEdge;/*定义当前最小值*/for(intj=1;j<=n;j++)if(a[i][j]!=NoEdge&&/*当定点i,j之间存在回路时*/(a[i][j]

6、

7、Min==NoEdg

8、e))/*当顶点i,j之间的距离小于Min*/Min=a[i][j];/*更新当前最小值*/if(Min==NoEdge)returnNoEdge;//无回路MinOut[i]=Min;//printf("%d",MinOut[i]);/*顶点i的最小出边费用*/MinSum+=Min;//printf("%d",MinSum);/*最小出边费用的总和*/}MinHeapNode*E=0;E=(MinHeapNode*)malloc(sizeof(MinHeapNode));E->x=newint[n]

9、;//E.x=newint[n];for(i=0;ix[i]=i+1;E->s=0;E->cc=0;E->rcost=MinSum;E->next=0;//初始化当前扩展节点intbestc=NoEdge;/*记录当前最小值*///搜索排列空间树while(E->ss==n-2){//当前扩展结点是叶结点的父结点/*首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到

10、优先队列中，否则舍去该叶结点*/if(a[E->x[n-2]][E->x[n-1]]!=NoEdge&&/*当前要扩展和叶节点有边存在*/a[E->x[n-1]][1]!=NoEdge&&/*当前页节点有回路*/(E->cc+a[E->x[n-2]][E->x[n-1]]+a[E->x[n-1]][1]

11、

12、bestc==NoEdge)){b