旅行商问题.cpp

旅行商问题 算法中经典的算法 实验报告 内附代码

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

#define MAXNUM 100000
#define x 0
#define y 1

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

int Exp(int k)//计算2的k次方:二进制数左移一位实现*2
{
	k=1<<k; 
	return k;
}

int Readfile()//读入测试文件
{
	int space,i,j;
	char s[10];
	printf("请输入数据文件名:");
	gets(s);
	if(freopen(s,"r",stdin)==NULL)
	{
		printf("数据文件读取失败!\n");
		return 0;
	}
	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;
}

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]=MAXNUM;
				for(k=2;k<=n;k++)
				{
					if((s&1<<(k-2))!=0)
					{   
						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;
						}
					}
				}
			}
	}
}

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

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

void Reconstruct()//构造最优解，输出最短路程和最短路径 
{
	int i,k;
	s=Exp(n-1)-1;
	printf("最短路程是:%d\n",D[1][s]);
	printf("最短路径为:\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);
	}
	printf("\n");
}

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;
		}
		else x1+=150;
	}
	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] );
			}
			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);
			}
}

int main()//主函数 
{	
	double dfFreq;
	printf("================================================\n");
	printf("#程序运行过程中请勿移动窗口，否则会影响图形显示#\n");
	printf("#如已移动窗口并造成图形显示异常，请重新运行程序#\n");
	printf("================================================\n");
	if(Readfile()==0) //调用Readfile(),读入测试文件
		return 0;
	else
	{
		LARGE_INTEGER litmp;
		LARGE_INTEGER liCount1; 
		LARGE_INTEGER liCount2;

		QueryPerformanceFrequency(&litmp);
		dfFreq = (double)litmp.QuadPart;
		QueryPerformanceCounter(&liCount1);
		Tsp();//调用Tsp()动态规划求最优解
		QueryPerformanceCounter(&liCount2);
		Reconstruct();//调用Reconstruct()构造最优解,并输出最短路程和最短路径 
		DrawGragh(); //画图 
	}
	return 0;
}