tsp.cpp

用C语言实现旅行商问题。该算法简单精悍

// TSP.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <windows.h>

#define INF 10000
#define pi 3.14159265358
#define L 200.0  /*圆的半径 */
#define N1  21

/*集合用二进制数表示，其对应的正整数为数组的下标 */

//Dij[i][j] 为从i点经过j集合到源点的花费 
int Dij[N1][1<<20];
// routine[i][j] 为从i点经过j集合到源点情况下i->..
int routine[N1][1<<20];

int Distance[N1][N1];
int CityNum;
long start;  //计时

//-----------------------------------------------------------------
//Copyright.cpp
void Copyright(){
	printf("******************* Copyright ************************\n");
	printf("Author:wangjd     04120087    finished time:07.07.01\n\n");
	printf("File Function:\n");
	printf("Give several cities signed 1,2....n  and the distances of every two cities\n");
	printf("You must pass every city one time and only one time,At last back to 1\n");
	printf("The routine you searched must be shortest of all\n\n");
	printf("Usage:\n");
	printf("	TSP\n");
	printf("	TSP TSPxx.txt\n");
}


//------------------------------------------------------------------------
//get the datas from file
void GetData(char *file){
	FILE *in;
	int i,j,c;
	
	if((in = fopen(file,"r"))==NULL){
			printf("Can't open the inputfile : %s \n",file);
			exit(0);
	}
	start=GetTickCount();

	fscanf(in,"%d",&c);
	CityNum = c;
	for(i=0;i<CityNum;i++)
		for(j=0;j<CityNum;j++){
			fscanf(in,"%d",&Distance[i][j]);
		}
}

//********************************************************************************************
/* 图形界面操作 */
void draw(int num,int *rout){
	double temp;
	double x[N1],y[N1];
	char *M[N1]={"0'\0'","1 ","2 ","3 ","4 ","5 ","6 ","7 ","8 ","9 ","10","11","12","13","14","15","16","17","18","19","20"};
	HBRUSH hbrush_old;

	HDC hdc = GetWindowDC( GetDesktopWindow() );
	HPEN hpen1 = CreatePen( PS_SOLID, 1, RGB(255,200,200) );// 创建浅色1像素宽度的实线画笔  
	HPEN hpen2 = CreatePen( PS_DASH, 5, RGB(0,255,0) ); // 创建绿色5像素宽度的破折画笔
	HBRUSH hbrush1 = CreateSolidBrush( RGB(0,0,255) ); // 创建一个实体蓝色画刷 
	HBRUSH hbrush2 = CreateSolidBrush( RGB(128,0,255) ); //紫色 
	HBRUSH hbrush3 = CreateSolidBrush( RGB(0,255,64) );//绿色
	HPEN hpen_old = (HPEN)SelectObject( hdc, hpen1 ); 

	for(int i=0;i<num;i++){
		temp =i*(360.0/num)*(pi/180); //计算坐标
		y[i] =400 + L * sin(temp);
		x[i] =400 + L * cos(temp);

		if(i%3==0)
			hbrush_old = (HBRUSH)SelectObject( hdc, hbrush1);
		else if(i%3==1)
			hbrush_old = (HBRUSH)SelectObject( hdc, hbrush2);
		else  
			hbrush_old = (HBRUSH)SelectObject( hdc, hbrush3);

		Ellipse( hdc,(int)x[i], (int)y[i], int(x[i]+10), int(y[i]+10) );//画圆
		TextOut( hdc,(int)x[i],(int)y[i],M[i+1],2); //i,signed i+1; 并用数字标记
	}
	
	for(i=0;i<num;i++) //画各个点之间的直线
		for(int j = i+1;j<num;j++){
			MoveToEx( hdc, (int)x[i], (int)y[i], NULL ); 
			LineTo( hdc, (int)x[j], (int)y[j] );
		}

	hpen1 = CreatePen( PS_SOLID, 1, RGB(0,128,0) ); //换种颜色
	hpen_old = (HPEN)SelectObject( hdc, hpen1 );

	for(i=0;i<CityNum;i++){ //画路径点间的线
		MoveToEx( hdc,(int)x[rout[i+1]-1],(int)y[rout[i+1]-1],NULL);
		LineTo( hdc,(int)x[rout[i+2]-1],(int)y[rout[i+2]-1]);
	}
}




//*************************************************************************
//main.c
void main(int argc, char* argv[])
{
	char filename[10];
	int i,j,k,max,min,rout,curpos;
	int temp[N1];

	if(argc != 1 && argc != 2){
		printf("The number of argvment is unreasonable\n");
		return ;
	}
	if(argc==1){
		Copyright();
		return ;
	}

	strcpy(filename,argv[1]);
	GetData(filename);  //get need datas from file 

	max=(1<<(CityNum-1))-1; /*2^(n-1)-1*/

	for(i=1;i<CityNum;i++)  //i->0 (i直接到0)的花费
		Dij[i][0]=Distance[i][0];

	/* ex: CityNum=4 max=7,最终求得1->[2,3]->0,2-[1,3]->0,3-[1,2]->0的值*/
	for(i=1;i<max;i++){   //全部集合除了111..111集合
		for(j=1;j<=CityNum-1;j++)  //第一个起点  0->j+Dij[j][I]
			if((i>>(j-1)&1) ==0){   //j点不在集合i中
			    min=INF;
				for(k=1;k<=CityNum;k++){
					if((i>>(k-1)&1) !=0){  //k点在集合i中
						Dij[j][i] = Distance[j][k]+Dij[k][i-(1<<(k-1))];//递推公式
						if(Dij[j][i] < min){
							min=Dij[j][i];
							rout=k;
						}
					}
				}
				Dij[j][i]=min;
				routine[j][i]=rout;	
			}
	} //i>>(j-1)&1 判断是否 j位置1 ；i-(1<<(k-1)) 从i集合中删除k位上的值


	/*计算整条路径的最少花费*/
	min=INF;
	for(i=1;i<CityNum;i++){
		k=Distance[0][i]+Dij[i][max-(1<<(i-1))];
		if(k < min){   //t(11..11) 集合中删去位置i上的点
			min= k;
			curpos=i;  //最短路径上的第一个结点
		}
	}
	printf("The lowest cost of searched rout is %d \n",min);

	printf("The searched Path is :\n");
	printf("  1->%d",curpos+1);
	temp[1] = 1 ;   //保存各个路径点在temp中
	temp[2] = curpos+1;

	i=3;
	k=max; //111..11
	for(j=CityNum-1;j>0;j--){ //逆向求各个结点
		k=k-(1<<(curpos-1));  //直接放进数组内就有问题
		curpos=routine[curpos][k];
		printf("->%d",curpos+1);
		temp[i++] = curpos+1;
	}

	printf("\n");
	//draw为作图函数，参数为城市个数和保存的路径点
	draw(CityNum,temp);

	printf("The program take time:%f seconds\n",(GetTickCount()-start)/1000.0);	
}