/*********************************
模擬退火算法(SA)求解旅行商(TSP)問題
06373055 陳宗澤
2008.12.18
**********************************/


#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <ctime>
using namespace std;

#define  TERMINATE   0.000001     //終結差
#define  p0          0.95         //溫度下降系數
#define  MAX_COUNT   2            //路程多少沒有變化時結束
#define  TEMP		 280          //初始溫度
#define  MAX_CITY    200          //最大城市數
struct Point
{
	double x,y;
};

Point citys[20];				//城市的坐標,用數組記錄
int n;  						//城市數目
double t0;  					//初始溫度
double bestLength;				//最優解
double preLength;				//前一次的解，用來判斷結束條件
double currentLength;			//當前解
int  LOOP;						//循環次數, 為100*n
int  bestPath[MAX_CITY+1];	     		//最佳城市路線
int  currentPath[MAX_CITY+1];			//當前城市路線

/*******************
計算兩個城市之間的距離
*******************/
inline double calcDis(int a, int b) //返回點A和點B之間的距離
{
a--;b--;

	double dis = 
		sqrt((citys[a].x-citys[b].x)*(citys[a].x-citys[b].x)+(citys[a].y-citys[b].y)*(citys[a].y-citys[b].y));
	return dis;
}
/*******************
計算路線的長度
*******************/
double pathLength(int p[]) 
{
	double length = 0;
	for(int i = 0; i <n; i ++) 
		length += calcDis(p[i], p[i + 1]);
	return length;
}
/********************
初始化函數,讀入數據,初始化溫度和路線等
********************/
void initialize()
{
	FILE *infile,*outfile;
	if((infile=fopen("1.in","r"))==NULL)
	{
		cout<<"cann't open 1.in"<<endl;
		system("pause");
		exit(1);
	}
	
	fscanf(infile, "%d",&n);
	for(int i=0;i<n;i++)
		citys[i].x=citys[i].y=0;
	for(int i=0;i<n;i++)
	{
		

		int c;double x,y;
		fscanf(infile,"%d",&c);
		fscanf(infile,"%lf",&x);
		fscanf(infile,"%lf",&y);
		citys[c-1].x=x;
		citys[c-1].y=y;
		if(i==0)
		{ citys[n].x=x;citys[n].y=y;}
	}
	
	fclose(infile);
/*
    if ((outfile= fopen("1.out","w"))==NULL)
    {
		system("pause");
		exit(1);
    }
*/

	t0 = TEMP;										//初始溫度
	LOOP = 100 * n;									//每一個溫度的循環次數
	memset(bestPath,0,sizeof(bestPath));
	cout << "\n初始狀態: " ;

	//fprintf(outfile,"初始線路:  ");

	//fprintf(galog, "\n generation  best  average  standard \n");
	
	for (int i = 0; i < n; i++)
	{
		bestPath[i]=i+1;		//初始化路線序列
		cout<<bestPath[i]<<"-";
	}
	bestPath[n]=1;
	cout << "初始溫度: " << t0;
    
	
	bestLength = pathLength(bestPath);				//初始化最優解

}


/********************
交換城市rand1和rand2之間的方向
********************/
void swap(int rand1, int rand2)
{
	if(rand1 > rand2) 
	{
		int temp = rand1;
		rand1 = rand2;
		rand2 = temp;
	}

	for(int i = 1; i <= (rand2 - rand1 - 1) / 2; i ++) 
	{
		int temp = currentPath[rand1 + i];
		currentPath[rand1 + i] = currentPath[rand2 - i];
		currentPath[rand2 - i] = temp;
	}
}

/*********************
判斷當前解是否滿足接受的概率
*********************/
bool IsAccept(double bestLength, double currentLength, double t)
{
	double p = (double)rand() / (double)(RAND_MAX);
	double pt = exp((bestLength - currentLength) / t);
	if(pt > p) 
		return true;
	else 
		return false;
}
/*********************
模擬退火算法的具體函數
*********************/
void SA() {
	double t = t0;
	int count = 0;				
	while(1) 
	{
		for(int i = 0; i < LOOP; i ++) 
		{

			for(int i=0;i<=n;i++)
				currentPath[i]=bestPath[i];

			int rand1 = rand() % (n + 1);
			int rand2 = rand() % (n + 1);
			while(abs(rand1 - rand2) < 3)
				rand2 = rand() % (n + 1);


			swap(rand1, rand2);

			//計算新解
			double currentLength = pathLength(currentPath);		
		    
			//判斷是否應該接受新解
			if(currentLength - bestLength < TERMINATE) 
			{
				bestLength = currentLength;
				
				for(int i=0;i<=n;i++)
					bestPath[i]=currentPath[i];
			} else

    		if (IsAccept(bestLength, currentLength, t))
				{
					bestLength = currentLength;	
					for(int i=0;i<=n;i++)
					{
						bestPath[i]=currentPath[i];
					}
				}
		}

		if(fabs(preLength - bestLength) < TERMINATE) 
		{
			count++;
			//滿足結束條件，輸出終結狀態，MAX_COUNT標記結束時要求的結果不變的次數
			if(count > MAX_COUNT) 
			{
				cout << "\n終結路線: ";
				for(int i=0;i<n;i++)
					cout<<bestPath[i]<<"-";
				cout<< "  路線：" << bestLength << endl;
				return;
			}
		} 
		else 
		{
			preLength = bestLength;
			count = 0;
		}
		//每次輸出當前溫度下的計算結果
		cout << "\n當前溫度：" << t << "   路線：-";
		for(int i=0;i<n;i++)
			cout<< bestPath[i]<<"-";
		cout<< "  路長：" << bestLength << endl;
		//溫度下降
		t = t * p0;
	}
}


int main()
{
    initialize();
    SA();
system("pause");
}