tsp40.cpp

旅行商问题 tsp

#include<iostream.h>
#include<stdlib.h>
# include <stdio.h>
# include <math.h>
# include <ctype.h>
# include <time.h>
# define N 10
# define NN N*N
# define G(x) ((1.0+ tanh(x/u0))/2.0)  
void scities();               //城市坐标
void sinit();                 //初始神经元状态 
void cstates() ;               //设计能量函数
void dstates();               //输出
int recheck();           
int m=15;                       //10?
int tm, aa;
double v[NN],       /* neuron output*/
       v1[14000], 
       u[NN],       /* neurons input */
       dd[NN],     /* traverlling distance */
       t[NN],
       xx[N], yy[N], /* coordinate of cities */
       e,           /* energy */
       f,
       sub=0.00001;
double A=0.5,
       B=0.5,
       C=0.2,
       D=0.5,
       u0=0.02,
       h=0.01,
       l[NN],
       pi=3.1415926;
FILE *fp,*fopen();



void main()
{
      int i;
      double f1;
      fp=fopen("result.txt","w");
      i=0;
     f1=-0.07;   
	//  f1=0;               //
 
	  //预置一批S型激励函数值,以留作后面使用
      do
	  {   
		  i++;
          f1+=sub;           //sub=0.00001;
          v1[i]=G(f1);
	//	  cout<<"v1["<<i<<"]="<<v1[i]<<endl;               //0.99左右
	  } while((v1[i]<=0.999)&&(i<=13999));
	 //产生十个城市的位置分布
	//  cout<<f1<<endl;                           //0.06907
	  
	 scities();          //坐标 距离 初始阈值
 	 for(i=1;i<=50;i++)
	 {   tm=0;
         aa=i*10;
         cout<<"组号"<<i<<endl;         
		 
		 //产生神经元的初始状态
		 sinit();
 		 f=0;
         do
		 { //进行神经元状态的迭代运算
			 cstates();
             //判断前后两次的能量函数值是否很接近,若很接近,则结束运算
			 if(fabs(e-f)<1e-20) 
				 break;
 			 //检查旅行路线的合法性
			 if( recheck())
				 break;
             f=e;
		 }while(tm<1000);  //迭代超过1000次未达到稳定状态,则求解失败
 		 //计算在最终稳定状态下合法旅行路径的长度,并显示所有神经元的状态
		 dstates();
	 }
	 fclose(fp);

}







void scities()
{   int i=0;
    int j;
    double h[N],o,w,oo;
	//给出每个城市的坐标
    xx[0]=0.4;   yy[0]=0.4493;
	xx[1]=0.2493;yy[1]=0.1463;
	xx[2]=0.1707;yy[2]=0.2293;
	xx[3]=0.2293;yy[3]=0.7610;
	xx[4]=0.5171;yy[4]=0.9414;
	xx[5]=0.8732;yy[5]=0.6536;
	xx[6]=0.6878;yy[6]=0.5219;
	xx[7]=0.8488;yy[7]=0.3609;
	xx[8]=0.6683;yy[8]=0.2536;
	xx[9]=0.6195;yy[9]=0.2643;
	//计算城市之间的距离
    for(i=0;i<N;i++)
		for(j=0;j<N;j++)
		{
			if(i==j) continue;
            dd[i*N+j]=hypot(xx[i]-xx[j],yy[i]-yy[j]);
		//	cout<<"dd["<<i*N+j<<"]="<<dd[i*N+j]<<endl;       //
        }
     //根据坐标先初始化下神经元的阈值
     for(i=0;i<N;i++)
	 {	 o=(yy[i]-0.5)/(xx[i]-0.5);
         h[i]=atan(o);                          //角度
         oo=hypot(xx[i]-0.5,yy[i]-0.5);        //到点（0.5，0.5）的距离
         for(j=0;j<N;j++)
		 {
			 w=h[i]+(j-1)*2*pi/(float)N;
             l[i*N+j]=cos(w)*oo;
         }

       }
}
void sinit()
{
     int i,i1;
     double u00=0-u0*log(N-1)/2.0;
    /* for(i=0;i<aa;i++) 
	 {
		 t[i]=rand()/(float)32767;
	 }     */
	// cout<<t[0];                        //小于1的随机数
     for(i=0;i<NN;i++) 
	 {
		 t[i]=rand()/(float)32767;
	 }
	
	 //求神经元的初始状态
     for(i=0;i<NN;i++)
     {
         u[i]=u00+0.001*(t[i]*2-1)+0.002*l[i];
         i1=(int)(u[i]*100000.0+0.5)+7000;
	//	 cout<<i1<<endl;                               //
         if(i1 > 13907) v[i]=v1[13907];
         if(i1<=1) v[i]=v1[1];
         if(i1>1 && i1<=13907)
			 v[i]=v1[i1];
	//	cout<<"v["<<i<<"]="<<v[i]<<endl;       //
      }
}
void cstates()
{
	int i1,i,j,x,y,x0,y0;
	double z,k,z1;
    e=0.0;k=0;
    for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			k+=v[i*N+j];    //E3
	//	cout<<"k="<<k<<endl;                //
		
	//求能量函数值
	e=0.0;
	for(x=0;x<N;x++)     //10行
	{
		x0=x*N;
		for(i=0;i<N;i++)
		{
			for(j=0;j<N;j++)
			{
				if(i==j) continue;
			e+=v[x0+i]*v[x0+j];       //  E1每行两两相乘 之和
			}
		}
	}
	for(i=0;i<N;i++)          //10列
		for(x=0;x<N;x++)
		{
			x0=x* N;
			for(y=0;y<N;y++)
			{
				if (x==y) continue;
				e+=v[x0+i]*v[y*N+i];        //E2每列两两相乘 之和
			}
		}
	for(x=0;x<N;x++)
	{
		x0=x*N;
        for(y=0;y<N;y++)
		{
			if (y==x) continue;
            y0=y*N;
            for(i=0;i<N;i++)
			{
				if (i==0)
                   e+=v[x0]*dd[x0+y]*(v[y0+1]+v[y0+N-1]);
                else 
					if(i==N-1)
						e+=v[x0+i]*dd[x0+y]*(v[y0+N-2]+v[y0]);
					else
						e+=v[x0+i] * dd[x0+y]*(v[y0+i-1]+v[y0+i+1]); //E4
              }
         }
    }
    e+=(A*e+C*(k-N)*(k-N))/2.0;        //能量函数E


    //计算 duxi/dt 
    for(x=0;x<N;x++)
	{
		x0=x*N;
        for(i=0;i<N;i++)
		{
			z=-C*(k-m);
			for(j=0;j<N;j++)
			{
				if(i==j) continue;
                z-=v[x0+j];
            }
            for(y=0;y<N;y++)
			{
				if(x==y) continue;
				z-=v[y*N+i];
			}
            u[x0+i]+=h*z;
            //再求神经元的状态
			z1=u[x0+i]* 100000.0+0.5;
            i1=(int) z1 +7000;
            if(i1>13907) v[x0+i]=v1[13907];
            if(i1<=1) v[x0+i]=v1[1];
            if(i1>1 && i1<=13907) v[x0+i]=v1[i1];
		}
	}
	tm+=1;
}
void dstates()
{
     int i, j, x0;
     double dis;
     fprintf(fp,"iterations=%d   e=%f",tm, e);
     cout<<"       迭代次数="<<tm<<"  能量函数e="<<e<<"    ";
     if(recheck())
	 {
		 cout<<" 合法路径 ";
         fprintf(fp, "  right path\n");
		//求最终的路径长度
		dis=0;
		for (i=0;i<N;i++)
		  for (j=0;j<N;j++)
		  {
			  if (v[i*N+j]>0.99)
				  dis=dis+dd[i*N+j];
			
		  }
		    cout<<"     距离="<<dis<<endl<<endl;
        fprintf(fp,"distance = %f \n",dis);
        /* ovput the result of neuron satrix */
        for(i=0;i<N;i++)
		{
			x0=i*N;
			for(j=0;j<N;j++)
				fprintf(fp,"%3.0f%s",v[x0+j],",   ");
			fprintf(fp,"\n");
		}
			fprintf(fp,"\n\n");
	 }
     else
	 {
		 fprintf(fp, " wrong path \n\n");
         cout<<"wrong path \n\n";
	 }
}
int recheck()
{
	int i,j,x0;
    double k;
	/*neuron's State must access 0 or 1 */
    for(i=0;i<NN;i++)
		if((v[i]>0.01) && (v[i]<0.99))
			return 0;
	/*every row have and only have one 1 */
	for(i=0;i<N;i++) 
	{
		k=0.0;
        x0 =i*N;
        for(j=0;j<N;j++)
			k+=v[x0+j];        //每行v的和
        if((k-1.0)>0.1)
			return 0;
	}
    /* every column have and only have one 1*/
    for(i=0;i<N;i++)         //10列
	{
		k=0.0;
        for(j=0;j<N;j++)
			k+=v[j*N+i];        //每列v的和
        if((k -1.0)>0.1)
            return 0;
   }
   return 1;
}
	/*****end******/