tsp.cpp

旅行商问题： 某售货员要到若干城市去推销商品

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct node{
	int x;
	int *ptr;
	struct node *next;
}Node;

__int64 *CN = NULL;

int **CreatIntArray_2(int **Head,int m,int n)
{
    int i,j;
    int *p=NULL;

    if( !(m > 0 && n > 0) ){                              //判断维度是否正确
		printf("错误的数组维度\n");
		return NULL;
	}
    if( !(p = (int *)malloc(sizeof(int) * m * n))){   //申请总体空间
		printf("Malloc error\n");
		return NULL;
	}
    if( !(Head = (int **)malloc(sizeof(int *)*m))){   //申请二级指针空间
		printf("Malloc error\n");
		return NULL;
	}
    for(i = 0;i < m;i++)                
        Head[i]=p + n * i;
    for(i = 0;i < m;i++)                  
        for(j = 0;j < n;j++)
            Head[i][j] = 0;
    return Head;
} 

__int64 C(int n,int k)   //求组合数C(n,k)
{
	int i;
	__int64 up = 1,down = 1;
	
	for(i = n - k + 1; i <= n;i++)
		up *= i;
	for(i = 2; i <= k; i++)
		down *= i;
	return up/down;
}

void FillCN(int n)
{
	int i;
	CN[0] = 1;
	for(i = 1; i <= n; i++){
		if(i > n/2)
			CN[i] = CN[n - i];
		else
			CN[i] = C(n,i);
		//printf("%ld ",CN[i]);
	}
}
int NumOf(long a,int n) //求长整型数a的二进制表示中1的个数,n为最多的1的个数
{
	int i,num = 0;
	for(i = 0; i < n;i++)
		if((a & (1<<i)) != 0) //注意(a & (1<<i))外层的括号不能少
			num++;
	return num;
}
int GetDiff(long a,long b,int n)  //求回溯路径，找出那位二进制位不同
{
	int i;
	for(i = 1; i <= n;i++){
		if(((a & 1<<(i - 1)) ^ (b & 1<<(i - 1))) != 0)
			return i;
	}
}
void ReArry(long L,int n,int **a,int **b)  //根据数L返回两个数组，数组a包含1的位置，数组b包含0的位置,n为最多的1的个数
{
	int i,j,k,l;

	j = NumOf(L,n);
	if( !(*a = (int *)malloc(sizeof(int)*(j+1)))){   //申请二级指针空间
		printf("Malloc error\n");
		return ;
	}
	(*a)[0] = j;  //a[0]放置1的个数
	if( !(*b = (int *)malloc(sizeof(int)*(n-j+1)))){   //申请二级指针空间
		printf("Malloc error\n");
		return ;
	}
	(*b)[0] = n - j;  //b[0]放置0的个数
	k = l = 1;
	for(i = 0; i < n;i++)  //在数组a和b中放置1和0信息
		if((L & (1<<i)) != 0) //注意(a & (1<<i))外层的括号不能少
			(*a)[k++] = i + 1;
		else
			(*b)[l++] = i + 1;
	
}

int main(void)
{
	int i,k,f,q,g,temp,m,n;  //m为输入的顶点个数，n为m-1，表示除顶点外的顶点个数
	int *a = NULL,*b = NULL;//用于存放1和0的位置信息
	long l,nl;//l为长整型循环变量，nl为集合的个数
	FILE *fp;
	int **G = NULL;//存放顶点信息
	Node *N = NULL;//集合数组
	Node **P = NULL,**Q = NULL;  //指针数组，用于存放指向Node类型的指针
	__int64 j,h;
	clock_t start,end; //测试程序运行时间

	start = clock();
	if(!(fp = fopen("TSP.txt","r"))){
		printf("Open file error\n");
		return -1;
	}

	fscanf(fp,"%d",&m);  //读取顶点个数

	n = m - 1;  //n为除顶点外的点的个数
	
	if(!(G = CreatIntArray_2(G,m,m))){
		printf("Malloc G error!\n");
		return -1;
	}

	for(i = 0; i < m; i++)
		for(j = 0; j < m; j++)
			fscanf(fp,"%d",&G[i][j]);
/*****************************	
   //打印顶点信息
	for(i = 0; i < m; i++){
		for(j = 0; j < m; j++)
			printf("%d ",G[i][j]);
		printf("\n");
	}
******************************/
	fclose(fp);

//	printf("%d",NumOf((long)15,4));
//	printf("%d",C(20,10));
//	printf("%d",GetDiff(41,25,n));
	nl = (1<<n);
	if( !(CN = (__int64 *)malloc(sizeof(__int64)*(n+1)))){   //给集合数组申请空间
		printf("Malloc error\n");
		return NULL;
	}
	FillCN(n);
/*	for(i = 1; i <= n;i++)
		printf("%ld ",CN[i]);*/
	if( !(N = (Node *)malloc(sizeof(Node)*nl))){   //给集合数组申请空间
		printf("Malloc error\n");
		return NULL;
	}
	if( !(P = (Node **)malloc(sizeof(Node *)*(n + 1)))){   //给集合数组申请空间
		printf("Malloc error\n");
		return NULL;
	}
	if( !(Q = (Node **)malloc(sizeof(Node *)*(n + 1)))){   //给集合数组申请空间
		printf("Malloc error\n");
		return NULL;
	}
	for(i = 0; i <= n;i++)
		P[i] = Q[i] = NULL;

	for(l = 0; l < nl; l++){
		N[l].x = l;
		N[l].next = NULL;
		j = NumOf(l,n);
		if(P[j] == NULL)
			P[j] = Q[j] = &N[l];
		else{
			P[j]->next = &N[l];
			P[j] = &N[l];
		}
	}
/**********************************************************
   //按照1的个数，逐行打印集合信息
	for(i = 1; i <= n;i++)
		P[i] = Q[i];
	for(l = 1; l <= n; l++){
		nl = C(n,l);
		for(j = 1; j <= nl;j++,P[l] = P[l]->next)
			printf("%d ",P[l]->x);
		printf("\n");
	}
***********************************************************/
	//初始化含1的个数为一的集合
	for(i = 1; i <= n;i++)  //回调P指针
		P[i] = Q[i];

	for(i = 1; i <= n; i++,P[1] = P[1]->next){//对n和只含一个的集合操作
		if( !(P[1]->ptr = (int *)malloc(sizeof(int)*(n+1)))){   //给集合数组申请空间
			printf("Malloc error\n");
			return NULL;
		}
		ReArry(P[1]->x,n,&a,&b);
		for(j = 1; j <= b[0]; j++){
			(P[1]->ptr)[b[j]] = G[0][a[1]] + G[a[1]][b[j]];
	//		printf("%d ",(P[1]->ptr)[b[j]]);
		}
		free(a);
		free(b);
	//	printf("\n");
	}
	for(i = 2; i <= n - 1;i++){  //对所有含1的个数为i的集合操作
		h = CN[i];       //一共有h各这样的集合
		for(j = 1,P[i] = Q[i]; j <= h;j++,P[i] = P[i]->next){  //对每个这样的集合操作
			ReArry(P[i]->x,n,&a,&b);
			if( !(P[i]->ptr = (int *)malloc(sizeof(int)*(n+1)))){   //给集合数组申请空间
				printf("Malloc error\n");
				return NULL;
			}
			for(k = 1; k <= b[0]; k++){ //对该集合拉出来的数组进行填写，填写位置是0的顶点
				temp = 35766;
				for(f = 1; f <= a[0]; f++){  //根据上一次的填表填写这次的数值
					g = (P[i]->x) & ~(1<<(a[f] - 1));  //取得上次的位置
					q = (N[g].ptr)[a[f]] + G[a[f]][b[k]];
					if(q < temp){
						temp = q;
						(P[i]->ptr)[0] = g;
					}
				}
				(P[i]->ptr)[b[k]] = temp;
			}
			free(a);
			free(b);
		}
	}
	temp = 35766;
	P[n] = Q[n];   //最后一次填表，得出结果
	if( !(P[n]->ptr = (int *)malloc(sizeof(int)*(2)))){   //给集合数组申请空间
		printf("Malloc error\n");
		return NULL;
	}
	for(i = 1; i <= n; i++){
		g = (P[n]->x) & ~(1<<(i - 1));  //取得上次的位置
		q = (N[g].ptr)[i] + G[i][0];
		if(q < temp){
			temp = q;
			(P[n]->ptr)[0] = g;
		}
	}
	(P[n]->ptr)[1] = temp;
	printf("顶点个数为%d\n最短路径长度为:%d\n",m,temp);
/***********************************************************************
	//测试ReArry函数
	ReArry(19,5,&a,&b);
	for(i = 1; i <= a[0];i++)
		printf("%d ",a[i]);
	printf("\n");
	for(i = 1; i <= b[0];i++)
		printf("%d ",b[i]);
************************************************************************/
	end = clock();
	l = nl - 1;
	printf("%d->",1);
	for(i = 1; i < n;i++){ //每次输出一个顶点
		printf("%d->",GetDiff(l,(N[l].ptr)[0],n)+1);
		l = (N[l].ptr)[0];
	}
	for(i = 1;i <= n;i++){
		if((l & (1<<(i - 1))) != 0){
			printf("%d",i+1);
			break;
		}
	}
	printf("->%d",1);
	
	printf("\n程序运行%lf秒\n",(double)(end - start) /  CLK_TCK);
/*删除空间，图形显示*/
	return 1;
			
}