#include <StdAfx.h>
#include <math.h>
#include <algorithm>
using std::random_shuffle;
using std::swap;

/*********************************************************
	InitialSA()——模擬退火算法的初始化
	1. 根據(jù)直角坐標(biāo)生成城市距離矩陣
	2. 計(jì)算初始溫度
*********************************************************/
void InitialSA()
{
	if( FileType == 1 )
	{
		CityNumber = vecCitys.size();
	
		vecCityDistances.clear();
		std::vector<SYCity>::iterator iter_from, iter_to;
		for( iter_from=vecCitys.begin();iter_from!=vecCitys.end();iter_from++ )
		{
			for( iter_to=vecCitys.begin();iter_to!=vecCitys.end();iter_to++ )
			{
				SYCityDistance tmp_citydistance;
				CountCityDistance( *iter_from, *iter_to, tmp_citydistance );

				vecCityDistances.push_back( tmp_citydistance );
			}
		}
	}
	else if( FileType == 2 )
	{
		vecCitys.clear();

		int nRow = -1;
		int ncityindex;
		CString strcityname;
		std::vector<SYCityDistance>::iterator iter_dis;
		for( iter_dis=vecCityDistances.begin();iter_dis!=vecCityDistances.end();iter_dis++ )
		{
			if( nRow < 0 )
				nRow = iter_dis->m_nFromCity;

			if( iter_dis->m_nFromCity == nRow )
			{
				ncityindex = iter_dis->m_nToCity;
				strcityname.Format("城市 %d",ncityindex);

				SYCity tmpCity;
				tmpCity.m_strName = strcityname;
				tmpCity.m_nIndex = ncityindex;
				tmpCity.m_Coordinate.m_fcodx = 0.0;
				tmpCity.m_Coordinate.m_fcody = 0.0;
				vecCitys.push_back( tmpCity );
			}
			else
				break;
		}
		CityNumber = vecCitys.size();
	}	
	
	double fMaxCityDistance = 0.0;
	double fMinCityDistance = 100000.0;
	double fCityDistance = 0.0;
	std::vector<SYCityDistance>::iterator iter_dis;
	for( iter_dis=vecCityDistances.begin();iter_dis!=vecCityDistances.end();iter_dis++ )
	{
		fCityDistance = iter_dis->m_fDistance;

		if( fCityDistance > fMaxCityDistance )
			fMaxCityDistance = fCityDistance;

		if( fCityDistance < fMinCityDistance )
			fMinCityDistance = fCityDistance;
	}

	int rate = 20;
	InitialTemperature = CountInitialTemperatureMaxMin( fMaxCityDistance, fMinCityDistance, rate );
	NowTemperature = InitialTemperature;
	NowExternalIterNumber = 0;
	NowInnerIterNumber = 0;
}

/*********************************************************
	ClearSA()——清空殘留數(shù)據(jù)
*********************************************************/
void ClearSA()
{
	vecCitys.clear();
	vecCityDistances.clear();
	CityNumber = 0;
	InitialTemperature = 0.0;
	NowTemperature = 0.0;
	NowExternalIterNumber = 0;
	NowInnerIterNumber = 0;
}

/*********************************************************
	CountCityDistance()——計(jì)算城市之間的距離
	輸入?yún)?shù)： 1、FromCity			源城市引用
			   2、ToCity			目標(biāo)城市引用
			   3、CityDistance		城市距離利用，返回值
	返回值：   源城市與目標(biāo)城市之間的距離，double型
*********************************************************/
double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance )
{
	CityDistance.m_nFromCity = FromCity.m_nIndex;
	CityDistance.m_nToCity = ToCity.m_nIndex;

	CityDistance.m_fDistance = sqrt( (FromCity.m_Coordinate.m_fcodx-ToCity.m_Coordinate.m_fcodx)*(FromCity.m_Coordinate.m_fcodx-ToCity.m_Coordinate.m_fcodx) +
									 (FromCity.m_Coordinate.m_fcody-ToCity.m_Coordinate.m_fcody)*(FromCity.m_Coordinate.m_fcody-ToCity.m_Coordinate.m_fcody) );

	return CityDistance.m_fDistance;

}

/*********************************************************
	CountInitialTemperatureMaxMin()——計(jì)算起始溫度
	輸入?yún)?shù)： 1、maxdis	城市之間的最大距離
			   2、mindis	城市之間的最小距離
			   3、rate		比例系數(shù)
	返回值：   起始溫度，double型
	計(jì)算方法參見《現(xiàn)代優(yōu)化計(jì)算方法》（邢文訓(xùn)等編著） p117 
*********************************************************/
double CountInitialTemperatureMaxMin( double maxdis, double mindis, int rate )
{
	return( rate*( CityNumber*maxdis - CityNumber*mindis ) );
}

/*********************************************************
	CreateCityRouter()——生成城市行走路徑
	輸入?yún)?shù)： 1、CityRouter	城市行走路徑的vector引用，返回值
	返回值：   空
	注：生成1->2->3->......->n的城市行走順序，作為算法初值
*********************************************************/
void CreateCityRouter( CityRouterDef &CityRouter )
{
	for( int i=1;i<=CityNumber;i++ )
		CityRouter.push_back( i );

//	random_shuffle(CityRouter.begin(), CityRouter.end()); 
}

/*********************************************************
	CreateCityRouter2opt()——從某行走路徑的鄰域中隨機(jī)選擇一個(gè)新的行走路徑，鄰域映射為2-opt
	輸入?yún)?shù)： 1、preCityRouter		原先行走路徑的vector引用
			   2、CityRouter		新的行走路徑的vector引用，返回值
	返回值：   空
*********************************************************/
void CreateCityRouter2opt( CityRouterDef &preCityRouter, CityRouterDef &CityRouter )
{
	int swapA, swapB;
	CityRouter = preCityRouter;

	while(1)
	{
		swapA = (rand()%CityNumber)-1;
		if( swapA >= 0 )
			break;
	}

	while(1)
	{
		swapB = (rand()%CityNumber)-1;
		if( swapA != swapB && swapB >= 0 )
		{
			int tmp = CityRouter[swapA];
			CityRouter[swapA] = CityRouter[swapB];
			CityRouter[swapB] = tmp;
			break;
		}
	}
}

/*********************************************************
	CountTotalDistance()——根據(jù)給定路徑計(jì)算該路徑對(duì)應(yīng)的總路程
	輸入?yún)?shù)： 1、CityRouter		給定行走路徑的vector引用
	返回值：   總路程，double型
*********************************************************/
double CountTotalDistance( CityRouterDef &CityRouter )
{
	if( CityRouter.size() != CityNumber )
		return 0.0;

	double totaldis = 0.0;
	for( int i=1;i<CityNumber;i++ )
	{
		totaldis += FindCityDistance( CityRouter[i-1], CityRouter[i] );
	}
	totaldis += FindCityDistance( CityRouter[CityNumber-1], CityRouter[0] );
	return totaldis;
}

/*********************************************************
	FindCityDistance()——根據(jù)兩城市的索引獲得兩城市之間的路程
	輸入?yún)?shù)： 1、FromCityIndex		源城市的索引
			   2、ToCityIndex		目標(biāo)城市的索引
	返回值：   兩城市之間的路程，double型
*********************************************************/
double FindCityDistance( int FromCityIndex, int ToCityIndex )
{
	int nIndex = (FromCityIndex-1)*CityNumber+(ToCityIndex-1);

	std::vector<SYCityDistance>::iterator iter_citydis;
	iter_citydis = vecCityDistances.begin()+nIndex;

	if( iter_citydis->m_nFromCity == FromCityIndex &&
		iter_citydis->m_nToCity == ToCityIndex )
		return( iter_citydis->m_fDistance );
	else
		return( 0.0 );
}

/*********************************************************
	CountDownTemperature()——計(jì)算外層循環(huán)的下降后的溫度
	輸入?yún)?shù)： 1、nowtemp		當(dāng)前溫度
			   2、DownMode		下降方式，保留
	返回值：   下降后的溫度，double型
	注：		溫度下降方式 T（k+1） = K*T（k），K=0.95溫度下降方式 T（k+1） = K*T（k），K=0.95
*********************************************************/
double CountDownTemperature( double nowtemp, int DownMode )
{
	return( 0.95*nowtemp );
}

/*********************************************************
	JudgeOverInnerLoop()——判斷是否結(jié)束某一溫度下的內(nèi)層循環(huán)
	輸入?yún)?shù)： 1、JudgeMode		判斷方式，保留
	返回值：   是否結(jié)束標(biāo)志位，BOOL型
	注：		某一溫度下的循環(huán)次數(shù)是固定的，即城市個(gè)數(shù)的三次方
*********************************************************/
BOOL JudgeOverInnerLoop( int JudgeMode )
{
	if( NowInnerIterNumber >= CityNumber*CityNumber*CityNumber )  //*CityNumber)
		return TRUE;
	else
		return FALSE;
}

/*********************************************************
	JudgeOverExternalLoop()——判斷是否結(jié)束模擬退火算法
	輸入?yún)?shù)： 1、JudgeMode		判斷方式，保留
	返回值：   是否結(jié)束標(biāo)志位，BOOL型
	注：		使用“零度法”的判斷方式，T（k）<= 0.01，結(jié)束計(jì)算
*********************************************************/
BOOL JudgeOverExternalLoop( int JudgeMode )
{
	if( NowTemperature <= 0.01 )		//InitialTemperature*0.001 )
		return TRUE;
	else
		return FALSE;
}

/*********************************************************
	FormRouterString()——根據(jù)行走路徑生成路徑字符串，供顯示使用
	輸入?yún)?shù)： 1、CityRouter		給定行走路徑的引用
	返回值：   行走路徑的顯示字符串
*********************************************************/
CString FormRouterString( SYRouter &CityRouter )
{
	CString strTemp, strValue;

	strTemp = "路徑 ";
	
	std::vector<int>::iterator iter_cityindex;
	for( iter_cityindex=CityRouter.m_CityRouter.begin();
		 iter_cityindex!=CityRouter.m_CityRouter.end();
		 iter_cityindex++ )
	{
		strValue.Format("%d",*iter_cityindex);
		strTemp += strValue;

		if( iter_cityindex+1 == CityRouter.m_CityRouter.end() )
			strTemp += " ";
		else
			strTemp +=" ";
	}

	strTemp += "  ";
	strTemp += "總路程 ";
	strValue.Format("%10.4f",CityRouter.m_fTotalDistance);
	strTemp += strValue;
	return strTemp;
}

/*********************************************************
	GetCoordinatebyCityIndex()——根據(jù)城市索引獲取城市坐標(biāo)
	輸入?yún)?shù)： 1、cityindex				城市索引
			   2、coordx				城市X坐標(biāo)
			   3、coordy				城市Y坐標(biāo)
	返回值：  空 
*********************************************************/
void GetCoordinatebyCityIndex( int cityindex, double &coordx, double &coordy )
{
	coordx = 0.0;
	coordy = 0.0;

	if( cityindex > 0 && cityindex <= CityNumber )
	{
		std::vector<SYCity>::iterator iter_city;
		iter_city = vecCitys.begin()+cityindex-1;

		if( iter_city->m_nIndex == cityindex )
		{
			coordx = iter_city->m_Coordinate.m_fcodx;
			coordy = iter_city->m_Coordinate.m_fcody;
		}
	}
}

/*********************************************************
	GetRouterFileString()——獲得指定路徑的城市坐標(biāo)字符串
	輸入?yún)?shù)：	1、CityRouter			城市路徑索引 
				2、strTemp				城市坐標(biāo)字符串
	返回值：  空 
*********************************************************/
void GetRouterFileString( SYRouter &CityRouter, CString &strTemp )
{
	strTemp.Empty();

	CString strValue;
	std::vector<int>::iterator iter_city;
	double coordx, coordy;
	for( iter_city=CityRouter.m_CityRouter.begin();
		 iter_city!=CityRouter.m_CityRouter.end();
		 iter_city++ )
	{
		GetCoordinatebyCityIndex( *iter_city, coordx, coordy );
		strValue.Format("%.4f %.4f\n",coordx, coordy );
		strTemp += strValue;
	}
}