(C语言)分支界限法求解旅行商(TSP)问题

落日映苍穹つ 2022-09-17 11:19 236阅读 0赞

1.代码：

#include <stdio.h>
    #include <malloc.h>
    
    #define NoEdge           1000
    
    struct MinHeapNode
    {
    	int lcost; //子树费用的下界
    	int cc; //当前费用
    	int rcost; //x[s:n-1]中顶点最小出边费用和
    	int s; //根节点到当前节点的路径为x[0:s]
    	int *x; //需要进一步搜索的顶点是//x[s+1:n-1]
    	struct 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 int[n + 1]; /*定义定点i的最小出边费用*/
    	//计算MinOut[i]=顶点i的最小出边费用
    	int MinSum = 0;//最小出边费用总合
    	for(int i = 1; i <= n; i++)
    	{
    		int Min = NoEdge; /*定义当前最小值*/
    		for(int j = 1; j <= n; j++)
    			if(a[i][j] != NoEdge && /*当定点i,j之间存在回路时*/
    				(a[i][j] < Min || Min == NoEdge)) /*当顶点i,j之间的距离小于Min*/
    				Min = a[i][j]; /*更新当前最小值*/
    		if(Min == NoEdge)
    			return NoEdge;//无回路
    		MinOut[i] = Min;
    		//printf("%d\n",MinOut[i]);/*顶点i的最小出边费用*/
    		MinSum += Min;
    		// printf("%d\n",MinSum); /*最小出边费用的总和*/
    	}
    
    
    	MinHeapNode *E = 0;
    	E = (MinHeapNode*)malloc(sizeof(MinHeapNode));
    	E->x = new int[n];
    	// E.x=new int[n];
    	for(int i = 0; i < n; i++)
    		E->x[i] = i + 1;
    	E->s = 0;
    	E->cc = 0;
    	E->rcost = MinSum;
    	E->next = 0; //初始化当前扩展节点
    	int bestc = NoEdge; /*记录当前最小值*/
    	//搜索排列空间树
    	while(E->s < n - 1)
    	{//非叶结点
    		if(E->s == n - 2)
    		{//当前扩展结点是叶结点的父结点
    			/*
    			首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路
    			且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点
    			*/
    			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] < bestc /*该节点相应费用小于最小费用*/
    				|| bestc == NoEdge))
    			{
    				bestc = E->cc + a[E->x[n - 2]][E->x[n - 1]] + a[E->x[n - 1]][1]; /*更新当前最新费用*/
    				E->cc = bestc;
    				E->lcost = bestc;
    				E->s++;
    				E->next = NULL;
    				Insert(E); /*将该页节点插入到优先队列中*/
    			}else
    				free(E->x);//该页节点不满足条件舍弃扩展结点 
    		}else
    		{/*产生当前扩展结点的儿子结点
    		 当s<n-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x[0:s]，
    		 其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。
    		 对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。
    		 当lcost<bestc时，将这个可行儿子结点插入到活结点优先队列中。*/
    			for(int i = E->s + 1; i < n; i++)
    				if(a[E->x[E->s]][E->x[i]] != NoEdge)
    				{ /*当前扩展节点到其他节点有边存在*/
    					//可行儿子结点
    					int cc = E->cc + a[E->x[E->s]][E->x[i]]; /*加上节点i后当前节点路径*/
    					int rcost = E->rcost - MinOut[E->x[E->s]]; /*剩余节点的和*/
    					int b = cc + rcost; //下界
    					if(b < bestc || bestc == NoEdge)
    					{//子树可能含最优解,结点插入最小堆
    						MinHeapNode * N;
    						N = (MinHeapNode*)malloc(sizeof(MinHeapNode));
    						N->x = new int[n];
    						for(int j = 0; j < n; j++)
    							N->x[j] = E->x[j];
    						N->x[E->s + 1] = E->x[i];
    						N->x[i] = E->x[E->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(int i = 0; i < n; i++)
    		v[i + 1] = E->x[i];//将最优解复制到v[1:n]
    	while(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);
    	n=5;
    	a = (int**)malloc(sizeof(int*) * (n + 1));
    	for(i = 1; i <= n; i++)
    	{
    		a[i] = (int*)malloc(sizeof(int) * (n + 1));
    	}
    // 	for(i = 1; i <= n; i++)
    // 		for(int j = 1; j <= n; j++)
    // 			//fscanf(in, "%d", &a[i][j]);
    // 			a[i][j]=1;
    	a[1][1]=0;
    	a[1][2]=5;
    	a[1][3]=8;
    	a[1][4]=5;
    	a[1][5]=4;
    
    	a[2][1]=5;
    	a[2][2]=0;
    	a[2][3]=5;
    	a[2][4]=6;
    	a[2][5]=3;
    
    	a[3][1]=8;
    	a[3][2]=5;
    	a[3][3]=0;
    	a[3][4]=5;
    	a[3][5]=4;
    
    	a[4][1]=5;
    	a[4][2]=6;
    	a[4][3]=6;
    	a[4][4]=0;
    	a[4][5]=3;
    
    	a[5][1]=4;
    	a[5][2]=3;
    	a[5][3]=4;
    	a[5][4]=3;
    	a[5][5]=0;
    
    	// prev = (int*)malloc(sizeof(int)*(n+1)) ;
    	int*v = (int*)malloc(sizeof(int) * (n + 1));// MaxLoading(w , c , n) ;
    	for(i = 1; i <= n; i++)
    		v[i] = 0;
    	bestc = BBTSP(v);
    
    	printf("\n");
    	for(i = 1; i <= n; i++)
    		fprintf(stdout, "%d\t", v[i]);
    	fprintf(stdout, "\n");
    	fprintf(stdout, "%d\n", bestc);
    	return 0;
    }

2.输出结果

1->2->5->3->4->1
    距离：22