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


/*	
程序初始參數說明:

初始溫度的選取方法：	
	選取一個確定值：600度
	
狀態被接受的條件：
	使用了課件95頁的方法，如果delta f < 0, 則At = 1，否則At = exp(-delta f / t)

降溫算法：
	采用等比例下降的方法，比例系數為0.95

同一溫度內計算結束的條件：
	在每個溫度下采用固定的迭代次數，Lk=100n，n為城市數；

算法結束條件：
	當相鄰三個溫度得到的解無任何變化時算法停止。 
*/

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

#define  epsln		0.000001
#define  p0         0.95
#define  MAX_COUNT  2
#define  TEMP		280

//記錄坐標的結構類型
struct dis
{
	double x,y;
};
/*
const double epsln = 0.000001;
const double p0 = 0.95;
const int MAX_COUNT = 2;
*/
dis citys[20];				//城市的坐標,用數組記錄
int n;						//城市數目
double t0;					//初始溫度
double bestLength;			//最優解
double preLength;			//前一次的解，用來判斷結束條件
double currentLength;		//當前解
int LOOP;					//循環次數
string bestPath;			//城市路徑，根據兩個輸入數據都順序用一位字符表示城市名的情況，可以用字符串記錄路徑。
string currentPath;			//每次得到的當前城市路徑

double distance(char a, char b) //返回點1和點2的距離
{
	double dis = sqrt((citys[a - 'A'].x - citys[b - 'A'].x) * (citys[a - 'A'].x - citys[b - 'A'].x) 
		+ (citys[a - 'A'].y - citys[b - 'A'].y) * (citys[a - 'A'].y - citys[b - 'A'].y));
	return dis;
}

double pathLength(string p) 
{
	double length = 0;
	for(int i = 0; i < n; i ++) 
		length += distance(p[i], p[i + 1]);
	return length;
}

//讀入文件中的城市坐標數據
void readData()
{
	string fileName;
	cout << "請輸入文件名：";
	cin >> fileName;
	ifstream fin(fileName.data());

	fin >> n;
	for (int i = 0; i < n; i++)
	{
		citys[i].x = 0;
		citys[i].y = 0;
	}
	for (int i = 0; i < n; i++)
	{
		char city;
		double x,y;
		fin >> city >> x >> y;
		citys[(int)(city - 'A')].x = x;
		citys[(int)(city - 'A')].y = y;
	}
	fin.close();
}

//設置各項參數
void setup()
{
	t0 = TEMP;										//初始溫度
	LOOP = 100 * n;									//每一個溫度的循環次數
	bestPath = "";									
	for (int i = 0; i < n; i++)
		bestPath = bestPath + (char)(i + 'A');
	bestPath = bestPath;// + bestPath[0];				//初始化路線序列
	cout << "\n初始狀態: " << bestPath.substr(0, n);
	cout << "\n起始溫度: " << t0;
	bestLength = pathLength(bestPath);				//初始化最優解
}

void shuffle(int rand1, int rand2)
{
	if(rand1 > rand2) 
	{
		int temp = rand1;
		rand1 = rand2;
		rand2 = temp;
	}

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

//判斷當前解是否滿足接受的概率
bool proAccept(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 simulateAnneal() {
	double t = t0;
	int count = 0;		//記錄每一個溫度下結果重復的次數，如果重復了三次，就結束整個算法。		
	while(true) 
	{
		for(int i = 0; i < LOOP; i ++) 
		{
			//隨機選取兩個城市，將他們之間的城市走向反向
			currentPath = bestPath;
			int rand1 = rand() % (n + 1);
			int rand2 = rand() % (n + 1);
			while(abs(rand1 - rand2) < 3)
				rand2 = rand() % (n + 1);

			//將rand1，rand2之間的城市走向反向
			shuffle(rand1, rand2);

			//計算新解
			double currentLength = pathLength(currentPath);		

			//新解的接受準則，注意使用浮點數的大小比較方法，要分兩種情況
			if(currentLength - bestLength < epsln) 
			{
				bestLength = currentLength;
				bestPath = currentPath;
			} 
			else //判斷當前解是否滿足接受的概率
				if (proAccept(bestLength, currentLength, t))
				{
					bestLength = currentLength;	
					bestPath = currentPath;
				}
		}

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

void init()
{
	readData();				//讀入數據
	setup();				//初始化參數
}

int main()
{
	init();					//讀入數據，初始化參數
	simulateAnneal();		//用模擬退火算法求解

	system("pause");
	return 0;
}