tsp.cpp

某售货员要到若干城市去推销商品

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

#define x 0//把数组用坐标形象化
#define y 1

int num,min[20][1<<20],path[20][1<<20],arcs[20][20];//min数组用于存储路径长度,path数组用于存储路径上的点

int value(int k,int i,int n)//点k经路径集合i回到出发点0所需路径长度
{                           //路径集合i这样表示:如果p点在这个集合中,则在i的二进制数表示中,第p位为1,否则为0
	int p,q,r;
	min[k][i]=10000;//先设个较大的值
	p=q=1;
	while(p<=i)//如果比路径集合大,则肯定不在这集合中
	{
		if((i&p)!=0)//在该路径集合中
		{
			r=min[q][i&~p]+arcs[k][q];//计算所需长度,并取最小者记录
			if(r<min[k][i])
			{
				min[k][i]=r;
				path[k][i]=q;
			}
		}
		p=p+p;//判断下一个点是否在路径集合中
		q++;//q为路径集合中抽出的点
	}
	return min[k][i];
}

void trace(int n)//求最短路径
{
	int k;
	int i;
	for(k=1;k<=n;k++)
		min[k][0]=arcs[0][k];//初始化,只有一条边时值为顶点间距离
	for(i=1;i<=(1<<n)-1;i++)
		for(k=1;k<=n;k++)
			if(((1<<(k-1))&i)==0)//顶点k不在路径集合i中
				min[k][i]=value(k,i,n);
		
}

void draw()//画图函数
{
	int x1,y1,i,j,k,s;
	int **Loc;
	char *S[20]={"0 ","1 ","2 ","3 ","4 ","5 ","6 ","7 ","8 ","9 ","10","11","12","13","14","15","16","17","18","19"};
	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_SOLID, 1, RGB(0,255,0) );	// 创建绿色1像素宽度的实线画笔
	HPEN hpen3 = CreatePen( PS_SOLID, 2, RGB(255,0,0) );	// 创建红色2像素宽度的实线画笔
	HPEN hpen_old = (HPEN)SelectObject( hdc, hpen1 ); 
	HBRUSH hbrush_old = (HBRUSH)SelectObject( hdc, hbrush1 );// 将hpen1和hbrush1选进HDC，并保存HDC原来的画笔和画刷
	Loc=(int **)malloc(sizeof(int *)*(num+1));//为存储坐标开辟节点
	for(i=0;i<=num;i++)
		Loc[i]=(int *)malloc(sizeof(int)*2);
	x1=100;
	y1=220;
	for(i=1;i<=num;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],S[i-1],2);//给点标上号数
		x1+=30;
		y1=260+rand()%300;
	}
	SelectObject( hdc, hpen2 );//选hpen2，绿色实线画笔
	for(i=1;i<=num;i++)
		for(j=1;j<i;j++)
			if(arcs[i-1][j-1]!=0)//当两个城市相通时，画边
			{
				MoveToEx( hdc, Loc[i][x], Loc[i][y], NULL ); 
				LineTo( hdc, Loc[j][x], Loc[j][y] );
			}
	SelectObject( hdc, hpen3 );//选hpen3，红色实线画笔
	s=(1<<(num-1))-1;
	MoveToEx( hdc, Loc[1][x], Loc[1][y], NULL );
	s=(1<<(num-1))-1;
	printf("\n  路径为:0->");
	for(i=1,k=path[0][0];i<=num-1;i++,k=path[k][s])//画tsp路线，采用动态画法，每隔2秒画一条线
	{
		Sleep(2000);
		LineTo( hdc, Loc[k+1][x], Loc[k+1][y] );
		printf("%d->",k);
		MoveToEx( hdc, Loc[k+1][x], Loc[k+1][y], NULL );
		s=s&~(1<<(k-1));//从路径集合中去掉该点
	}
    Sleep(2000);
	printf("0   ");
	LineTo( hdc, Loc[k+1][x], Loc[k+1][y] );
}

void main()//主函数
{
	FILE *fp;
	int i,j;
	char filename[20];
	long start;//计录时间用的
	printf("\n  Please input the file name:"); //读入文件
	scanf("%s",filename);
    start=GetTickCount();//开始计时
    if((fp=fopen(filename,"r"))==NULL)
    {
        printf("\n  The file is not exist!\n\n  ");//文件不存在则退出/
        exit(0);
    }
    fscanf(fp,"%d\n",&num);
	for(i=0;i<num;i++)
		for(j=0;j<num;j++)
			fscanf(fp,"%d\n",&arcs[i][j]);//读入各顶点间距离
	fclose(fp);
	trace(num-1);//求最短路径
	j=min[1][(1<<(num-1))-1-1]+arcs[0][1];
	path[0][0]=1;
	if(num>2)
		for(i=2;i<num;i++)
		if(min[i][(1<<(num-1))-1-(1<<(i-1))]+arcs[0][i]<j)//求出路径上第二点及最短路径
		{
			j=min[i][(1<<(num-1))-1-(1<<(i-1))]+arcs[0][i];
		    path[0][0]=i;
		}
	
	printf("  最短路径长度为:%d",j);
	printf("    找到最短路径共耗时:%f秒",(GetTickCount()-start)/1000.0);
	draw();//做图
}