tsp.cpp

旅行商问题 某售货员要到若干城市去推销商品

#include "TSP.h"

int d[20][1048576],pre[20][1048576],vnum[19];  //d数组为存放经过集合A到达顶点i的最短路径的长度
											   //pre数组存放的是和d数组对应的各个顶点的前驱顶点的编号
											   //vnum数组保存的是每个顶点对应的二进制的值，如vnum[0]=1，vnum[1]=2,vnum[2]=4……
											   //1对应顶点2的二进制值，2对应顶点3的二进制值……
extern int vertex[21][21];
//求最短路程和前驱顶点的备忘录
void TSP(int n)
{
	int A,i,j,h,m,s,p,min,v,prev;
	s=(int)pow(2,n-1)-1;  
	for(i=2;i<=n;++i)     //从顶点1出发到其他顶点且中间经过顶点集合A为空的情况
	{
		d[i-2][0]=vertex[1][i];
		pre[i-2][0]=1;     //记录其前驱顶点编号
	}
	h=1;
	for(i=0;i<n-1;++i)    //将从2-n的顶点对应的二进制值保存到数组vnum中
	{
		vnum[i]=h;
		h*=2;
	}
	for(j=1;j<s;++j)
		for(i=2;i<=n;++i)
		{
			A=j;
			if(j&vnum[i-2])    //如果集合A中包含了顶点i或起始顶点，则跳过处理过程
				continue;
			min=INFINITY;            //置min为无穷大
			h=1;                     //h用来标记A中访问的顶点编号,h为1表示顶点2
			while(!(v=A%2)&&h<n)	 //获取集合A中的一个顶点,起编号用h来记录
			{
				A/=2;				 //A除2来获取下一个顶点信息
				h++;				 //h-1为对应的顶点的编号
			}    
			while(v!=0)              //判断A中的顶点是否遍历
			{
				m=j-vnum[h-1];     //1->A-{m}->m->i,m为此时选择出来的终点i的前一顶点
				p=d[h-1][m]+vertex[h+1][i];   //求路径长度
				if(p<min)				//判断p是否为当前1->i的最短路径
				{
					min=p;				//更新最小值
					prev=h+1;			//记录此时的前驱顶点
				}
				A/=2;					//从集合中去掉已经访问过的顶点
				h++;					//h加1从而跳过已访问的顶点
				while(!(v=A%2)&&h<n)	//获取A中除去v后的其他任一顶点
				{
					A/=2;
					h++;
				}   
			}
			d[i-2][j]=min;				//更新备忘录信息
			pre[i-2][j]=prev;			//更新前驱节点信息
		}
}
//输出最短路线
void print(int n)
{
	int i,j,prev,min=INFINITY,k=(int)pow(2,n-1)-1,l;
	for(i=2;i<=n;++i)   //用1->i的路程长度加上i->1的长度，从而判断哪条路线是最短的
	{
		j=k-vnum[i-2];
		if((l=d[i-2][j]+vertex[i][1])<min)
		{
			min=l;     //记录最短路程的长度
			prev=i;	   //记录最短路程的顶点号
		}
	}
	printf("最短路程为：%d\n",min);   //输出最短路程长度
	printf("最优路线为：1->%d->",prev);  //输出逆序路线
	for( i = 1; i < n-1; ++i )  //根据前驱顶点数组输出从prev开始的各个顶点的前驱顶点
	{
		k = k-vnum[prev-2];  
		prev = pre[prev-2][k];
		printf("%d->",prev);
	}
	printf("1\n");
}