tsp.cpp

神经网络TSP算法

// TSP.cpp: implementation of the TSP class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "YYTSP.h"
#include "TSP.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

TSP::TSP()
{
         A = 500 ;       //
         B = 500 ;       //
         C = 200 ;        //
         D = 500 ;  
		 x0=0.02;
		 t_Interval=1;
		 for(int i=0;i<N;i++)
			 for(int j=0;j<N;j++)
				 _v[i][j]=0;
		 initial();
		 distance();
		 e=0;
		 Emin=0;

         initial();
         distance();
}

void TSP::initial()             //初始化
{
	
    //给出每个城市的坐标
	X[0]=0.4;   Y[0]=0.4493;
	X[1]=0.2493;Y[1]=0.1463;
	X[2]=0.1707;Y[2]=0.2293;
	X[3]=0.2293;Y[3]=0.7610;
	X[4]=0.5171;Y[4]=0.9414;
	X[5]=0.8732;Y[5]=0.6536;
	X[6]=0.6878;Y[6]=0.5219;
	X[7]=0.8488;Y[7]=0.3609;
	X[8]=0.6683;Y[8]=0.2536;
	X[9]=0.6195;Y[9]=0.2643;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			v[i][j]=0.0;
			_v[i][j]=0.0;
			u[i][j]=0.0;
		}
	}      //输入的第一个赋值
}

void TSP::distance()//计算两城市间的距离
{
    int i,j;
	for(i=0;i<N;i++)
		 for(j=0;j<N;j++)
        	dd[i][j]=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));            
}



void TSP::InitUx()//初始化X[i][j],输入
{
    int i=0,j=0;
	srand( (unsigned)time(NULL));
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
		{  
			double t=(rand()/(float)32767)*2-1;
			u[i][j]=x0*0.5*log(N-1)+t;
			//cout<<u[i][j]<<endl;
		}
}

//输出的计算   i代表城市名，j代表时间
void TSP::InitVx()
{
 	int i=0,j=0;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
		{
			v[i][j]=(1+tanh(u[i][j]/x0))*0.5;//通过输入激励求得初始输出
		   	if(v[i][j]<0.01) v[i][j]=0;
			else if(v[i][j]>0.99) v[i][j]=1;
		}
}

int TSP::train(int count)
{
        int x,y,i,j,judge,q;
		int sumX[10],sumY[10];
		double va[10][10],vb[10][10],vc=0,vd[10][10],dU[10][10];
		double ddd[10][10];

	
		do
		{
		InitUx();
		InitVx();

		for(q=0;q<count;q++)
		{
             e=0;
			 //求式dU[x][i]=-U[x][i]/R-A*va[x][i]-B*vb[x][i]-C*vc-D*vd[x][i]中的va,vb,vc,vd		
			for(x=0;x<10;x++)for(i=0;i<10;i++) //初始化
				{
				va[x][i]=vb[x][i]=vd[x][i]=ddd[x][i]=0;
			}
			for(x=0;x<10;x++)
			{
				for(i=0;i<10;i++)            //va
				{
				    for(j=0;j<10;j++)
					{
					   if(j!=i) va[x][i]+=v[x][j];											
					}
				}
			}
			for(x=0;x<10;x++)for(i=0;i<10;i++)	//vb
			{
				for(y=0;y<10;y++)
				{
					if(y!=x) vb[x][i]+=v[y][i];
				}
			}
			for(x=0;x<10;x++)for(j=0;j<10;j++) vc+=v[x][j];			
			vc-=N;
			for(x=0;x<10;x++)for(i=0;i<10;i++)//vd
			{
				for(y=0;y<10;y++)
				{
					if(i==0)	
						vd[x][i]+=dd[x][y]*(v[y][1]+v[y][9]);
					else if(i==9)
						vd[x][i]+=dd[x][y]*(v[y][0]+v[y][8]);
					else
						vd[x][i]+=dd[x][y]*(v[y][i+1]+v[y][i-1]);
				}
			}

			for(x=0;x<10;x++)for(i=0;i<10;i++)
			{
				dU[x][i]=(-u[x][i]/100-A*va[x][i]-B*vb[x][i]-C*vc-D*vd[x][i]);
				u[x][i]+=dU[x][i];
			}
            //下一次的输出V[][]
			InitVx();

			//求取优化的距离指示标e
            for(x=0;x<10;x++)   
			    for( y=0;y<10;y++)
				{
					for( i=0;i<10;i++)
					{
						if(i==0) 
							ddd[x][y]+=dd[x][y]*v[x][i]*(v[y][i+1]+v[y][10-1]);
						else if(i==(10-1)) 
							ddd[x][y]+=dd[x][y]*v[x][i]*(v[y][i-1]+v[y][0]);
						else
							ddd[x][y]+=dd[x][y]*v[x][i]*(v[y][i+1]+v[y][i-1]);
					}
					e += ddd[x][y];
				}

		    for(i=0;i<N;i++)
			{
				sumX[i]=0;
				sumY[i]=0;
			}
			for(i=0;i<N;i++)   //计算行和与列和
			    for(j=0;j<N;j++)
				{
					sumX[i]+=(int)v[i][j];
					sumY[i]+=(int)v[j][i];
				}
			judge=1;
			for(i=0;i<N;i++) //判断每行每行每列是否为1
			{
				judge=(int)(judge*sumX[i]*sumY[i]); //如果judge[i]==1,则说明为1
			}
              
		  if(judge==1)
		  {
			  cout<<e<<endl;
			  //cout<<q<<endl;
			  return 1;//将网络中稳定点的个数赋给a
		  }
		}
		}while(q>=count);

       
		return 0;
     
}
void TSP::printV(void)
{
	for(int ii=0;ii<10;ii++)
	{
		for(int jj=0;jj<10;jj++)
			cout<<v[ii][jj]<<", ";
		cout<<endl;
	}
}
void TSP::print_V(void)
{
	for(int ii=0;ii<10;ii++)
	{
		for(int jj=0;jj<10;jj++)
			cout<<_v[ii][jj]<<", ";
		cout<<endl;
	}
}


TSP::~TSP()
{

}