sacode.cpp

模拟退火优化旅行商问题,付城市坐标!vC++代码!

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

/*********************************************************
	InitialSA()——模拟退火算法的初始化
	1. 根据直角坐标生成城市距离矩阵
	2. 计算初始温度
*********************************************************/
void InitialSA()
{
	CityNumber = vecCitys.size();
	
	vecCityDistances.clear();
	double fMaxCityDistance = 0.0;
	double fMinCityDistance = 100000.0;
	double fCityDistance = 0.0;
	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;
			fCityDistance = CountCityDistance( *iter_from, *iter_to, tmp_citydistance );

			if( fCityDistance > fMaxCityDistance )
				fMaxCityDistance = fCityDistance;

			if( fCityDistance < fMinCityDistance )
				fMinCityDistance = fCityDistance;

			vecCityDistances.push_back( tmp_citydistance );
		}
	}

	int rate = 40;
	InitialTemperature = CountInitialTemperatureMaxMin( fMaxCityDistance, fMinCityDistance, rate );
}

/*********************************************************
	ClearSA()——清空残留数据
*********************************************************/
void ClearSA()
{
	vecCitys.clear();
	vecCityDistances.clear();
	CityNumber = 0;
	InitialTemperature = 0.0;
}

/*********************************************************
	CountCityDistance()——计算城市之间的距离
	输入参数： 1、FromCity			源城市引用
			   2、ToCity			目标城市引用
			   3、CityDistance		城市距离利用，返回值
	返回值：   源城市与目标城市之间的距离，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()——计算起始温度
	输入参数： 1、maxdis	城市之间的最大距离
			   2、mindis	城市之间的最小距离
			   3、rate		比例系数
	返回值：   起始温度，double型
	计算方法参见《现代优化计算方法》（邢文训等编著） p117 
*********************************************************/
double CountInitialTemperatureMaxMin( double maxdis, double mindis, int rate )
{
	return( rate*( CityNumber*maxdis - CityNumber*mindis ) );
}

/*********************************************************
	FormRouterString()——根据行走路径生成路径字符串，供显示使用
	输入参数： 1、CityRouter		给定行走路径的引用
	返回值：   行走路径的显示字符串
*********************************************************/
CString FormRouterString( SYRouter &CityRouter )
{
	CString strTemp, strValue;

//	strTemp = "";
	strTemp = "路程:";
	strValue.Format("%4.2f",CityRouter.m_fTotalDistance);
	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 +=" ";
	}
	return strTemp;
}

/*********************************************************
	GetCoordinatebyCityIndex()——根据城市索引获取城市坐标
	输入参数： 1、cityindex				城市索引
			   2、coordx				城市X坐标
			   3、coordy				城市Y坐标
	返回值：  空 
*********************************************************/
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()——获得指定路径的城市坐标字符串
	输入参数：	1、CityRouter			城市路径索引 
				2、strTemp				城市坐标字符串
	返回值：  空 
*********************************************************/
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;
	}
}