tsp1.cpp

(1).问题描述：旅行商问题 某售货员要到若干城市去推销商品

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


#define MAXDIS 30000
#define x 0
#define y 1

int **G;         //图的邻接矩阵
int n;			 //图顶点数
unsigned int s;  //用于表示顶点集合，第i位为1，表示第(i+1)个顶点在集合s中(i>0)
int **D;		 //表示顶点到s顶点集合的距离
int **R;		 //表示i到集合s路径的第一个顶点是R[i][s]
int **Loc;		 //点坐标

//-------------------------------------------------------------------------------------
int Exp(int k){
	//计算2的k次方
	return 1<<k;
}//Exp

//-------------------------------------------------------------------------------------
Readfile(){
	//读入测试文件
	int space;
	int i,j;
	freopen("TSP4.txt","r",stdin);
	scanf("%d",&n);
	printf("n=%d\n",n);
	G=(int **)malloc(sizeof(int *)*(n+1));
	for(i=0;i<=n;i++)
		G[i]=(int *)malloc(sizeof(int)*(n+1));//为邻接矩阵分配空间
	space=Exp(n-1);
	D=(int **)malloc(sizeof(int *)*(n+1));
	for(i=0;i<=n;i++)
		D[i]=(int *)malloc(sizeof(int)*(space));
	R=(int **)malloc(sizeof(int *)*(n+1));
	for(i=0;i<=n;i++)
		R[i]=(int *)malloc(sizeof(int)*(space));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&G[i][j]);
	return 1;
}//Readfile

//-------------------------------------------------------------------------------------
unsigned int Deletes(int k){
	//从s中将第k个顶点删除
	unsigned int ts;
    ts=1;
	ts=ts<<(k-2);
	ts=~ts;
	return s&ts;
}//Deletes

//-------------------------------------------------------------------------------------
void FillTable(){
	//采用自底向上填表
	int i,k;
	unsigned int max,s2;
	max=Exp(n-1)-1;
	for(s=1;s<=max;s++){
		for(i=1;i<=n;i++)
			if((s&1<<(i-2))==0){
				//如果第i个顶点不属于集合s
				D[i][s]=MAXDIS;
				for(k=2;k<=n;k++){
					if((s&1<<(k-2))!=0){
						//D[i][s]=min{G[i][k]+D[k][s-{k}]},其中k属于s
						s2=s&~(1<<(k-2));
						if(G[i][k]+D[k][s2]<D[i][s]){
							D[i][s]=G[i][k]+D[k][s2];
							R[i][s]=k;
						}//if
					}//if
				}//for
			}//if
	}//for
}//FillTable

//-------------------------------------------------------------------------------------
void Tsp(){
	//动态规划求解
	int i;
	s=s&0;
	for(i=2;i<=n;i++){
		D[i][s]=G[i][1];
		R[i][s]=1;
	}//for
	FillTable();
}//Tsp

//-------------------------------------------------------------------------------------
void Reconstruct(){
	//构造最优解，输出最短回路
	int i,k;
	s=Exp(n-1)-1;
	printf("The total distance is:%d\n",D[1][s]);
	printf("The shortest path is:\n");
	printf("1->");
	for(i=1,k=R[1][s];i<=n;i++,k=R[k][s]){
		if(i<n)
			printf("%d->",k);
		else
			printf("%d   ",k);
		s=Deletes(k);
	}//for
	printf("\n");
}//Reconstruct

//-------------------------------------------------------------------------------------
void DrawGragh(){
	//画图函数
	int x1,y1,i,j,k;
	char *M[20]={"1 ","2 ","3 ","4 ","5 ","6 ","7 ","8 ","9 ","10","11","12","13","14","15","16","17","18","19","20"};
	HDC hdc = GetWindowDC( GetDesktopWindow() );			// 获取一个可供画图的DC,此处用桌面
	HPEN hpen1 = CreatePen( PS_SOLID, 1, RGB(255,0,0) );	// 创建红色1像素宽度的实线画笔
	HBRUSH hbrush1 = CreateSolidBrush( RGB(0,0,255) );		// 创建一个实体蓝色画刷
	HPEN hpen2 = CreatePen( PS_DASH, 1, RGB(0,255,0) );		// 创建绿色1像素宽度的破折画笔
	HPEN hpen3 = CreatePen( PS_SOLID, 2, RGB(255,0,0) );	// 创建红色2像素宽度的实线画笔
	HPEN hpen4 = CreatePen( PS_SOLID, 2, RGB(255,153,27) );	// 创建黄色2像素宽度的实线画笔
	HPEN hpen_old = (HPEN)SelectObject( hdc, hpen1 ); 
	HBRUSH hbrush_old = (HBRUSH)SelectObject( hdc, hbrush1 );
		// 将hpen1和hbrush1选进HDC，并保存HDC原来的画笔和画刷
	Loc=(int **)malloc(sizeof(int *)*(n+1));
	for(i=0;i<=n;i++)
		Loc[i]=(int *)malloc(sizeof(int)*2);
	x1=160;
	y1=260;
	for(i=1;i<=n;i++){
		//画点
		Loc[i][x]=x1;
		Loc[i][y]=y1;
		Ellipse( hdc, Loc[i][x], Loc[i][y], Loc[i][x]+7, Loc[i][y]+7 );
		TextOut( hdc, Loc[i][x], Loc[i][y],M[i-1],2);		//给点标上号数
		if(i%3==0) {
			y1+=60;
			x1=160+(i/3)*35;
		}//if
		else x1+=150;
	}//for
	SelectObject( hdc, hpen2 );   //选hpen2，绿色破折画笔
	for(i=1;i<=n;i++)
		for(j=1;j<i;j++)
			if(G[i][j]!=0){
				//当两个城市相通时，画边
				MoveToEx( hdc, Loc[i][x], Loc[i][y], NULL ); 
				LineTo( hdc, Loc[j][x], Loc[j][y] );
			}//if
	SelectObject( hdc, hpen3 );   //选hpen3，红色实线画笔
	s=Exp(n-1)-1;
	MoveToEx( hdc, Loc[1][x], Loc[1][y], NULL );
	for(i=1,k=R[1][s];i<=n;i++,k=R[k][s]){
		//画tsp路线，采用动态画法，每隔1.5秒画一条线
		Sleep(1500);
		if(i%2==1) SelectObject( hdc, hpen3 );   //选hpen3，红色实线画笔
		else SelectObject( hdc, hpen4 );   //选hpen3，黄色实线画笔
		LineTo( hdc, Loc[k][x], Loc[k][y] );
		MoveToEx( hdc, Loc[k][x], Loc[k][y], NULL );
		s=Deletes(k);
	}//for
}//DrawGragh

//-------------------------------------------------------------------------------------
void main(){
	LARGE_INTEGER litmp;
	LARGE_INTEGER liCount1;   
	LARGE_INTEGER liCount2;
	double dfFreq;
	QueryPerformanceFrequency(&litmp);
	dfFreq = (double)litmp.QuadPart;
	if(Readfile()!=1)
		//读入测试文件
		printf("Read test file error!\n");
	QueryPerformanceCounter(&liCount1);
	Tsp();	//调用Tsp()动态规划求最优解
	Reconstruct();	//构造最优解
	QueryPerformanceCounter(&liCount2);
	printf("Running Time=%f   ",(double)(liCount2.QuadPart -liCount1.QuadPart )/dfFreq);
	//程序运行时间（秒级别）
	DrawGragh();	//画图	
}//main