#include <iostream.h>
#include <time.h>
#include <stdio.h>
#include <iomanip>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>


#define MaxCity_Num  10
double dist[MaxCity_Num][MaxCity_Num] ;      //城市間距離矩陣
double  u[MaxCity_Num][MaxCity_Num];         //神經元輸入
double	v[MaxCity_Num][MaxCity_Num];         //神經元輸出

#define A    1.5
#define D    0.05
#define H    1
#define U0   0.02
#define G(x)  ((1.0 + tanh(x / U0)) / 2.0)       //sigmoid函數
double MinDist = 10000.0;



void InitializeNet(double **u,double **v,int n)     //初始化神經元
{  
	int i,j;
	double m;

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			m = (rand() / (RAND_MAX + 1.0));
			u[i][j] = 0;
			v[i][j] = m;
		}


}


double Energy(double **v,double **dist,int n,double AA,double DD)    //能量函數
{  
	int i;
	int x;
	int y;
	double e;
	double t;
	double value;
	 
	e = 0;
	for(x = 0; x < n; x++)	
	{
		t = 0;
		for(i = 0; i < n; i++)
		{
			t += v[x][i];
		}
		e += (t - 1) * (t - 1);
	}
	
    for(i = 0; i < n; i++)	
	{
		t = 0;
		for(x = 0 ;x < n; x++)
		{
			t += v[x][i];
		}
		e += (t - 1) * (t - 1);
	}	

	t = 0;
	for(x = 0; x < n ; x++)	
	{
        for(y = 0; y < n; y++)
		{
			if(x == y) 
			{
				continue;
			}

            for(i = 0; i < n; i++)
			{
		    	if(i < n - 1)
				{
					t += v[x][i] * dist[x][y] * v[x][i] * v[y][i + 1];
				}
                if(i == n - 1)
				{
					t += v[x][i] * dist[x][y] * v[x][i] * v[y][0];
				}

            }
        }
    }
	
	value = (AA * e + DD * t) / 2;
	return value;


 
}
void Work(double **u,double **v,double **dist,int n,double AA,double DD,double HH)
{
    int i,j,x,y;
	double s,t,z;
    
	for(x = 0; x < n; x++)
	{
        for(i = 0; i < n; i++)
		{
			s = 0;	
			for (j = 0; j < n; j++) 
			{
				s += v[x][j];
			}
		    s -= 1;
			
			t = 0;
            for(y = 0; y < n; y++) 
			{
				t += v[y][i];
            }
			t -= 1;

			s *= AA;
			t *= AA;
		    
			z = 0;
			for(y = 0; y < n; y++) 
			{
				if(i < n-1) 
				{
					z += v[y][i + 1] * dist[x][y];
				}
				if(i == n-1)
				{
					z += v[y][0] * dist[x][y];
				}
			}
			z *= DD;
		    z = -s - t - z;	            
			u[x][i] += HH * z;
			v[x][i] = G(u[x][i]);
		}
	}


}



double distance(double **graph,int road[],int n)        //計算城市間距離
{
    int i;
	double sum;
	
	sum = 0.0;
	for(i = 0; i < n - 1; i++)
	{
		sum += graph[road[i] - 1][road[i + 1] - 1];
	}
    sum += graph[road[i] - 1][road[0] - 1];
	return sum;

}


bool Stop(double **v,int n)            //檢查約束   
{
    int i,j;
    double k;

    for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			if((v[i][j] > 0.01) && (v[i][j] < 0.99))
				return 0;
		}

	for(i = 0; i < n; i++)
	{
		k = 0;
        for(j = 0; j < n; j++)
		{
			if(i == j) 
			{
				continue;
			}
			k += v[i][j];
		}
        if((k - 1.0) > 0.01 || (1.0 - k) > 0.01)
		{
			return 0;
		}
	}
    for(i = 0; i < n; i++)
	{
		k = 0;
        for(j = 0; j < n; j++)
		{
			if (i == j) 
			{
				continue;
			}
			k += v[j][i];
		}
        if((k - 1.0) > 0.01 || (1.0 - k) > 0.01)
		{
            return 0;
		}
	}

	return 1;

 
}


double show(double **v,double **dist,int n,int flag)       //顯示輸出結果
{
     int i,j;
     double d;
	 int road[MaxCity_Num];

     if(Stop(v,n))
	 {
		d = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
			{
				if(v[i][j] > 0.99)
					road[j] = i + 1;
			}
		d = distance(dist,road,n);
		if (MinDist > d)  
		{
			MinDist = d;
		}
	
        if(flag==1)
		{
  
	        cout<<"當前回路為：  ";
	        for(i = 0; i < n; i++)
			{
		        cout<<road[i]<<" ";
			}
            cout<<road[0]<<endl;

            cout<<"路徑長度為："<<d<<endl<<endl;
 
		}
	 }
	 return d;


}



void RunNet(double **u,double **v,double **dist,int n,double AA,double DD,double HH,int flag)
{
    int count;
    double e,f;

	srand((int)time(0));
	 	
 	for(int i = 1; i <= 100; i++)
	{   
		 count = 0;
                
		 InitializeNet(u,v,n);

 		 f = 0;
		 do
		 { 
			 e = Energy(v,dist,n,AA,DD);
			 Work(u,v,dist,n,AA,DD,HH);
			 count++;
			 
			 if(fabs(e - f) < 1e-20) 
			 {
				 break;
			 }
			 
			 if(Stop(v,n))
			 {
				 break;
			 }
			 
             f = e;
		 }while(count < 1000);  
		 
		// if(flag)
		// {
			 show(v,dist,n,flag);
		 //}
	 }
	
	 

     cout<<"最短路徑長度為："<<MinDist<<endl;
  
}



void main()
{  
	int City_Num;
    ifstream datafile;                      
    char fileName[10];
	double *uu[MaxCity_Num];
	double *vv[MaxCity_Num];
	double *dd[MaxCity_Num];
	int ShowDist;
	int ShowCurrentResult;

	 
	cout<<"請輸入城市的數目（10）：";
	cin>>fileName;
    City_Num=atoi(fileName);

	cout<<"是否查看距離矩陣（1－是，0－否）：";
	cin>>ShowDist;

	cout<<"是否查看中間結果（1－是，0－否）：";
	cin>>ShowCurrentResult;
	
	for(int k=0;k<MaxCity_Num;k++)                           //初始化鄰接矩陣
         for(int m=0;m<MaxCity_Num;m++)
             dist[k][m]=0;
    datafile.open(strcat(fileName,".txt"));                  //打開文件   

    for(int i=0;i<MaxCity_Num;i++)                           //輸入數據到矩陣
	{	     for(int j=0;j<MaxCity_Num;j++)
		{	datafile>>dist[i][j];
			//dist[j][i]=dist[i][j];
		}
	}

if(ShowDist==1)	
{   
	for( k=0;k<MaxCity_Num;k++)
	  for(int l=0;l<MaxCity_Num;l++)
	     cout<<"dist["<<k<<"]["<<l<<"]="<<dist[k][l]<<" ";
	
	 cout<<endl<<endl;
}

   
	for(i = 0; i <MaxCity_Num; i++) 
	{
		uu[i] = u[i];
		vv[i] = v[i];
		dd[i] = dist[i];
	}

	RunNet(uu,vv,dd,MaxCity_Num,A,D,H,ShowCurrentResult);
 





}