tsp.cpp

c++程序实现TSP问题

/*----------------------------------------------------------------------------------------

功能描述：本程序实现找TSP问题的精确最优解。

实现方法：本程序的的基本思想是回溯法。深度优先遍历所有的路径，不断更新当前最优解以找到最终的
		  最优解。当前最优解的另一个作用是削减不必要搜索的子树。

算法分析：在是一个NP问题。从理论上讲无法在多项式的复杂度内实现。但是如果加上一些判定技巧也是
          可以使搜索次数大大减少，使计算机的处理规模增大。但无论如何也难以突破O(n!)的算法复杂
		  度。除了回溯法还可以用分支界线法，但是用此方法需要大量的额外辅助空间，是一种用空间
		  换时间的办法，而此方法也不能从跟本上解决问题，因为当处理规模很大时空间的消耗也是难
		  以承受的。

          作者：  毛毛                        日期：2007-10-19
------------------------------------------------------------------------------------------*/

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

struct Node//一个状态结点
{
	short * path;
	short cost;
	short pos;
	struct Node *next;
};
struct Key//用来存放各种组合的最小值
{
	short elem;
	short * data;//如果是叶子结点，分配空间存放一个长度为n-1的数组
	struct Key *down;//下一个位置的第一个结点
	struct Key *next;//这一个位置的下一个结点
};
struct Queue//定义一个队列用于广度优先遍历
{
	struct Node * front;
	struct Node * rear;
};
void InitQueue(struct Queue *Q);//初始化一个空队列
bool QueueEmpty(struct Queue *Q);//判断队列是否为空
void EnQueue(struct Queue *Q,struct Node *N);//入队列
struct Node * DeQueue(struct Queue *Q);//出队列，返回队结点
struct Node * tree;
short *array;
struct Node * bestPath;//最优路径
int n;
struct Key * key[20];
int deleteKey[20];//被删除的节点数
int keyCount[20];//生成的节点数
int enCount=0,deCount=0;
int beginSearch=0;
int searchCount=0;
int checkNodeCount=0;
int searchBegin=0;
int oldPos=3;
long FileSize(FILE *stream);//计算文件长度
short * GetArray(char *body,long size,int &n);//获得一个距离数组
void GetBest();//找到最优解
void SearchPath(struct Node *T);//从这个结点进行深度优先搜索
bool checkNode(struct Node *T,int m,struct Key *key);//检查结点
struct Key * InitKey(int m);//生成一个参照值
void InitKeys(int begin,int end);//生成一组参照值
void InitSubKey(struct Key * key,int m,int pos);//生成参照值子空间
void FreeKeys(int begin,int end);//释放一组参照值
void FreeKey(struct Key * key);//释放一个参照值

void main()
{
	FILE * fl;
	printf("输入要计算的文件名:\n");
	char fileName[100];
	scanf("%s",fileName);
	if((fl=fopen(fileName,"r"))==NULL)
	{
		printf("文件打开错误!\n");
		return;
	}
	long size=FileSize(fl);
	fseek(fl, SEEK_SET, 0); 
	char *body=new char[size];
    fread(body,size,1,fl);
	fclose(fl);
	n=-1;
	array=GetArray(body,size,n);
	printf("%s\n",body);
	for(int x=0;x<n;x++)
	{
		for(int y=0;y<n;y++)
		{
			printf("%d,",*(array+x*n+y));
		}
		printf("\n");
	}
	InitKeys(3,19);
	printf("分配完成\n");
	getchar();
	printf("继续...\n");
	for(int i=3;i<=19;i++)
	{
		keyCount[i]=0;
		deleteKey[i]=0;
	}
	int t1=clock();
	GetBest();
	int t2=clock();
	if(bestPath!=NULL)
	{
		printf("bestCost:%d\tsearchCount=%d,begingSearch=%d\n",bestPath->cost,searchCount,beginSearch);
		printf("enCount=%d,deCount=%d,checkNodCount=%d\n",enCount,deCount,checkNodeCount);
		//for(int i=3;i<=19;i++)
		{
		//	printf("keyCount%d:%d,deleteKey%d:%d\n",i,keyCount[i],i,deleteKey[i]);
		}
		for(int x=0;x<n;x++)
		{
			printf("%d,",bestPath->path[x]);
		}
	}
	else
	{
		printf("没有找到!");
	}
	double t=(t2-t1)/1000.0;
	printf("\n耗时:%f秒", t);  
	getchar();
};
void InitKeys(int begin,int end)
{
	for(int m=begin;m<=end;m++)
	{
		key[m]=InitKey(m);
	//	printf("%d分配完成!\n",m);
	//	getchar();
	}
}
struct Key * InitKey(int m)
{
	struct Key * key=new struct Key;
	key->data =NULL;
	key->elem =0;
	key->next =NULL;
	key->down =NULL;
	InitSubKey(key,m,0);
	return key;
}
void FreeKeys(int begin,int end)
{
	for(int m=begin;m<=end;m++)
	{
		FreeKey(key[m]);
		printf("%d释放完成!\n",m);
		getchar();
	}
}
void FreeKey(struct Key * key)
{
	if(key->down!=NULL)
	{
		FreeKey(key->down);
	}
	if(key->next!=NULL)
	{
		FreeKey(key->next);
	}
	if(key->data!=NULL)
	{
		delete key->data;
	}
	delete key;
}
void InitSubKey(struct Key * key,int m,int pos)//m表示从n个中取m个，pos表示组合数中的位置
{
	if(pos<m-1)
	{
		struct Key *old=(struct Key *)malloc(sizeof(struct Key));
		for(short i=key->elem+1;i<=(n+pos-m+1);i++)
		{
			struct Key *current=new struct Key;
			current->elem=i;
			current->down =NULL;
			current->data =NULL;
			current->next =NULL;
			if(i==key->elem+1)
			{
				key->down=current;
			}
			else
			{
				old->next =current;
			}
			old=current;
			InitSubKey(old,m,pos+1);
		}
	}
	else if(pos==m-1)
	{
		key->data =(short *)malloc(sizeof(short)*n);
		for(short i=1;i<n;i++)
		{
			*(key->data +i)=30000;
		}
	}
}
bool checkNode(struct Node *T,int m,struct Key *key)//检查结点是否保留
{
//	checkNodeCount++;
	short *path=new short[m];
	for(int x=0;x<m;x++)
	{
		path[x]=T->path[x+1];
	}
	for(x=0;x<m-2;x++)
	{
		for(int y=m-2;y>x;y--)
		{
			if(path[y]<path[y-1])
			{
				int t=path[y];
				path[y]=path[y-1];
				path[y-1]=t;
			}
		}
	}
	struct Key *current=key;	
	for(int i=0;i<m-1;i++)
	{
		current=current->down;
		while(path[i] > current->elem)
		{
			current=current->next;
		}
	}
	delete path;
	if(current->data[T->path[m]] >= T->cost )
	{
		current->data[T->path[m]]=T->cost ;
		return true;
	}
	else
	{
		delete T->path ;
		delete T;
		return false;
	}
};
void GetBest()
{
	tree=new struct Node;
	tree->path =new short[n];
	bestPath=new struct Node;
	bestPath->path =new short[n];
	for(int i=0;i<n;i++)
	{
		tree->path[i]=i;
		bestPath->path[i]=i;
	}
	tree->pos =0;
	tree->cost =0;
	tree->next =NULL;
	bestPath->cost=0;
	for(int pos=0;pos<n-2;pos++)
	{
		int min=*(array+bestPath->path[pos]*n+bestPath->path[pos+1]);	
		int p=pos+1;
		for(int j=pos+2;j<n;j++)
		{
			int current=*(array+bestPath->path[pos]*n+bestPath->path[j]);
			if(min>current)
			{
				min=current;//最小代价
				p=j;//在数组中的位置
			}
		}
		bestPath->cost+=min;
		int temp=bestPath->path[pos+1];
		bestPath->path[pos+1]=bestPath->path [p];
		bestPath->path [p]=temp;
	}
	bestPath->cost+=*(array+bestPath->path[n-2]*n+bestPath->path[n-1])+*(array+bestPath->path[n-1]*n);
	printf("greedy:%d\n",bestPath->cost);

	struct Queue *Q=new struct Queue;
	InitQueue(Q);
	EnQueue(Q,tree);
	
	while(!QueueEmpty(Q))
	{
		struct Node *T=DeQueue(Q);
	/*	if(T->pos==n-2)//如果形成一条路径
		{
			T->cost=T->cost + *(array+T->path[n-2]*n+T->path[n-1]) + *(array+T->path [n-1]*n);
			if(T->cost <bestPath->cost )//如果这路径比最好路径还好
			{
				delete(bestPath->path);
				delete(bestPath);//替换之
				bestPath=T;
			}
		}*/
	//	else//如果没有形成一条路径t
		{
			pos=T->pos;
			if(pos>=3 && pos<=9)
			{
				if(pos>oldPos)
				{
					FreeKey(key[oldPos]);
					oldPos=pos;
				}
				if(!checkNode(T,pos,key[pos]))
				{
					//deleteKey[pos]++;
					continue;
				}
			}
			for(int i=T->pos+1;i<n;i++)
			{
				int cost=T->cost + *(array+T->path[T->pos]*n+T->path[i]);
				
				if(cost<bestPath->cost)//如果其cost小于最好路径，生成一个新结点 
				{
					struct Node *N=new struct Node;
					N->path=new short[n];
					N->pos=T->pos +1;//路径前进一个位置
					for(int j=0 ;j<n;j++)//将原来结点路径复制到新生结点中
					{
						N->path[j]=T->path [j];
					}
					int temp=N->path[N->pos];
					N->path [N->pos]=N->path[i];
					N->path[i]=temp;
					N->cost=cost;//新的花费(路程)
					int pos=N->pos ;
					if(pos>=3 && pos<=8)
					{
					//	keyCount[pos]++;
						if(!checkNode(N,pos,key[pos]))
						{
						//deleteKey[pos]++;
						continue;
						}
					}
					else if(N->pos>8)//pos>8时，深度搜索
					{
					//	beginSearch++;
						SearchPath(N);continue;
					}
					EnQueue(Q,N);
				}//如果其cost小于最好路径，生成一个新结点
			}//for
			delete(T->path);
			delete(T);
		}//如果没有形成一条路径
	}//while
}

void SearchPath(struct Node *T)
{
	//if(searchBegin==0)
	{
	//	searchBegin=1;
	//	printf("开始深度搜索...\n");
	}
	//searchCount++;
	if(T->pos==n-2)//如果形成一条路径
	{
		T->cost=T->cost + *(array+T->path[n-2]*n+T->path[n-1]) + *(array+T->path [n-1]*n);
		if(T->cost <bestPath->cost )//如果这路径比最好路径还好
		{
			delete(bestPath->path);
			delete(bestPath);//替换之
			bestPath=T;
		}
	}
	else//如果没有形成一条路径
	{
		int pos=T->pos;
		if(pos>8 && pos<=19)
		{
			//keyCount[pos]++;
			if(!checkNode(T,pos,key[pos]))
			{
				//deleteKey[pos]++;
				return;
			}
		}
		for(int i=T->pos+1;i<n;i++)
		{
			int cost=T->cost + *(array+T->path[T->pos]*n+T->path[i]);
			
			if(cost < bestPath->cost)//如果其cost小于最好路径，生成一个新结点 
			{
				struct Node *N=new struct Node;
				N->path=new short[n];
				N->pos=T->pos +1;//路径前进一个位置
				for(int j=0 ;j<n;j++)//将原来结点路径复制到新生结点中
				{
					N->path[j]=T->path [j];
				}
				int temp=N->path[N->pos];
				N->path [N->pos]=N->path[i];
				N->path[i]=temp;
				N->cost=cost;//新的花费(路程)
				SearchPath(N);
			}
		}
		delete(T->path);
		delete(T);
	}
}


long FileSize(FILE *stream) //计算文件长度
{ 
   long curpos, length; 
   curpos = ftell(stream); 
   fseek(stream, 0L, SEEK_END); 
   length = ftell(stream); 
   fseek(stream, curpos, SEEK_SET); 
   return length; 
} ;
short * GetArray(char *body,long size,int &n)
{
	int sum=0;
	int add=0;
	int i;
	for(i=0;body[i]!=10;i++)
	{
		add=body[i]-48;
		sum=sum*10+add;
	}
	n=sum;
	*(body+size-1-n)='\0';
	short *array=new short[n*n];
	i++;
	for(int x=0;x<n;x++)
	{
		sum=0;
		add=0;
		int y=0;
		for(i++;body[i]!=10;i++)
		{
			if(body[i]!=' '&&body[i]!=10)
			{
				add=body[i]-48;
				sum=sum*10+add;
			}
			else
			{
				*(array+n*x+y)=sum;
				y++;
				sum=0;
				add=0;
				if(body[i]==10)
				{
					break;
				}
			}
		}
	}
	return array;
};

void InitQueue(struct Queue *Q)//初始化一个空队列
{
	struct Node * head=new struct Node;
	head->next =NULL; 
	Q->front =head;
	Q->rear=head;
};

bool QueueEmpty(struct Queue *Q)//判断队列是否为空
{
	if(Q->front ==Q->rear )
	{
		return true;
	}
	else
	{
		return false;
	}
};

void EnQueue(struct Queue *Q,struct Node *N)//入队列
{
	//enCount++;
	Q->rear->next=N;
	Q->rear=N; 
};

struct Node * DeQueue(struct Queue *Q)//出队列，返回队结点
{
	//deCount++;
	if(Q->front ==Q->rear )
	{
		printf("队列已空!!\n");
		return NULL;
	}
	else
	{
		struct Node *N=Q->front->next;
		Q->front->next=N->next;
		if(Q->rear==N)
		{
			Q->rear =Q->front;
		}
		return N;
	}
}