旅行商问题.cpp

经典的旅行商问题的求解

#include<iostream.h>
#include<stdlib.h>
struct stack
{
	int n;
	int L;
	int c;
	int fx;
	stack* p;//父接点
	stack*NEXT;
};
stack *Tsp1,*Tsp2;
int cycle[100]={0};
void pause()//暂停函数
{
	char s;
	cout<<"press <Enter> key to continue……";
	cin.unsetf(ios::skipws);
	cin>>s;
	cin.setf(ios::skipws);
}
int find(stack *p,stack *Headopen,stack* Headclosed)//展开接点在OPEN 和CLOSED是否出现
{
	stack *p1,*p2;
	p1=Headopen;
	p2=Headclosed;
	Tsp1=Tsp2=NULL;
	while(p1!=NULL)
	{
		if(p->c==p1->c) 
		{
			Tsp1=p1;
			return 1;
		}
		p1=p1->NEXT;
	}
	while(p2!=NULL)
	{
		if(p->c==p2->c) 
		{
			Tsp2=p2;
			return 1;
		}
		p2=p2->NEXT;
	}
	return 0;
}
int f(stack *s,int L,stack* Headclosed,int citynum)//计算估价函数
{
	int length=0,i=0;
	while(s!=NULL)
	{
		length=length+s->L;
		s=s->p;
		i++;
	}
	length=length+(citynum-1-i)*L;
	return length;
}
stack* sortopen(stack *p3,stack*p)//升序排列OPEN表
{
	stack*p1,*p2;
	if(p3==NULL)
	{ 
		p3=p;
		p->NEXT=NULL;
		return p3;
	}
	if(p3->fx>=p->fx) 
	{
		p->NEXT=p3;
		p3=p;
		return p3;
	}
	p2=p1=p3;
	while(p2->NEXT&&(p2->fx)<(p->fx))
	{
		p1=p2;p2=p2->NEXT;
	}
	if((p2->fx)<(p->fx))//插入链表尾部
	{
		p2->NEXT=p;
		p->NEXT=NULL;
	}
	else//插入P2之前
	{
		p->NEXT=p2;
		p1->NEXT=p;
	}
	return p3;
}
void tsp(int **a,int start,int citynum,int Len)//TSP主体函数
{
	int i=1,k,j;
	stack*sp1,*sp2,*Headopen,*Headclosed,*s0;
	s0=new stack;
	s0->L=a[start-1][start-1];
	s0->c=start;
	s0->p=NULL;
	Headopen=s0;
	Headopen->NEXT=NULL;
	sp1=Headopen;
	Headclosed=NULL;
	while(sp1!=NULL)
	{
		if(Headclosed==NULL)
		{
			Headclosed=Headopen;
			Headopen=Headopen->NEXT;
			Headclosed->n=i++;
			Headclosed->fx=f(Headclosed,Len,Headclosed,citynum);
			j=Headclosed->c-1;
			sp2=Headclosed;
		}
		else//
		{
			if(Headopen!=NULL)
			{
				sp2->NEXT=Headopen;
				Headopen=Headopen->NEXT;
				sp2=sp2->NEXT;
				sp2->NEXT=NULL;
				sp2->n=i++;
				j=sp2->c-1;
			}
			else break;
		}
		for(k=0;k<citynum;k++)//扩展N接点
		{
			if(k!=j)
			{
				stack *p0;
			    p0=new stack;
			    p0->p=sp2;
			    p0->L=a[j][k];
			    p0->c=k+1;
			    p0->fx=f(p0,Len,Headclosed,citynum);
			    if(find(p0,Headopen,Headclosed)==1)
				{
					if(sp2->p->c!=p0->c)
					{
						if(Tsp1!=NULL&&(p0->fx<Tsp1->fx)) 
						{
							Tsp1->p=p0->p;
							Tsp1->L=p0->L;
						}
						else if(Tsp2!=NULL&&(p0->fx<Tsp2->fx))
						{
							Tsp2->p=p0->p;
							Tsp2->L=p0->L;
						}
					}
				}
				else
					Headopen=sortopen(Headopen,p0);
			}
		}
	}
	int length=0;
	i=0;
	while(Headclosed!=NULL)
	{
		cycle[i]=Headclosed->c;
		length=length+Headclosed->L;
		Headclosed=Headclosed->NEXT;
		i++;
	}
	cycle[i+1]=length;
}
int find3(int**a,int num)//找出最小权值
{
	int c=a[0][1];
	for(int i=0;i<num;i++)
	{
		for(int j=0;j<num;j++)
		{
			if(a[i][j]<c&&a[i][j]!=0) c=a[i][j];
		}
	}
	return c;
}
void display(int p[],int k,int **a)//显示函数
{
	int L=0;
	for(int j=0;j<k-2;j++)
	{
		L=L+a[p[j]-1][p[j+1]-1];
	}
    p[k-1]=L;
	for( int i=0;i<k-1;i++)
	{
		if(p[i]==0) break;
		else
			cout<<p[i]<<"--->";
	}
	cout<<endl;
	cout<<"所走的总路程是："<<p[k-1];
	cout<<endl;
}
void main()
{
	int start=1,Len,citynum,count;
	cout<<"旅行商问题的A算法解答："<<endl;
	cout<<"旅行商问题：有叫TSP问题，假设有N个可以互相"<<endl;
	cout<<"	   直达的城市，某旅行商准备从其中的A城出发，"<<endl;
	cout<<"	   周游个城市一周，最后又回到A城市，要求所走路程最短"<<endl;
	cout<<"**********************************************"<<endl;
	cout<<"**********************************************"<<endl;
    pause();
    system("cls");//清屏函数
	cout<<"5个城市为默认状态，你也可以输入其他城市数目"<<endl;
	cout<<"其中A城市到B城市的距离看作相等，所以，"<<endl;
	cout<<"你只需要输入citynum*(citynum-1)/2个权值就可以了！"<<endl;
	cout<<endl;
    pause();
    system("cls");//清屏函数
	cout<<"请输入城市数目（默认为5个城市）："<<endl;
	cin>>citynum;
	int **a=new int*[citynum];
	int b[5][5]={0,1,2,7,5,1,0,4,4,3,2,4,0,1,2,7,4,1,0,3,5,3,2,3,0};
	for(int k=0;k<citynum;k++)
	{
		a[k]=new int[citynum];
	}
	if(citynum==5)
	{
		cout<<"执行默认状态："<<endl;
		for(int i=0;i<5;i++)
		{	
			for(int j=0;j<5;j++)
				a[i][j]=b[i][j];
		}
	}
	else
	{	
		cout<<"请输入"<<citynum*(citynum-1)/2<<"条航路的权值："<<endl;
		for(int i=0;i<citynum;i++)
		{
			for(int j=i;j<citynum;j++)
			{
				if(i==j) a[i][j]=0;
				else
					cin>>a[i][j];
				a[j][i]=a[i][j];
			}
		}
	}
	cout<<"用二维数组a[i][j]表示你所输入的状态图为:"<<endl;
	cout<<"=================================="<<endl;
	for(int i=0;i<citynum;i++)
	{
		count=1;
		for(int j=0;j<citynum;j++)
		{
			cout<<a[i][j]<<"   ";
			if(count==citynum) cout<<endl;
			count=count+1;
		}
	}
	cout<<"================================="<<endl;
	cout<<"*********************************"<<endl;
	cout<<"a[i][j]的值表示i到j的路程"<<endl;
	cout<<"*********************************"<<endl;
	cout<<endl;
	Len=find3(a,citynum);
	cout<<"输入起始城市："<<endl;
	cin>>start;
	if(start>citynum)
		cout<<"只有"<<citynum<<"个城市，你的输入非法！"<<endl;
	else
	{
		cycle[citynum]=start;
		tsp(a,start,citynum,Len);
		display(cycle,citynum+2,a);
	}
}