sacode.h

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

#include <vector>

struct SYCoordinate
{
	SYCoordinate()
	{
		m_fcodx = 0.0;
		m_fcody = 0.0;
	}

	double m_fcodx;
	double m_fcody;
};

struct SYCity
{
	SYCity()
	{
		m_nIndex = 0;
		m_strName.Empty();
	}

	int m_nIndex;					//城市编号
	CString m_strName;				//城市名称
	SYCoordinate m_Coordinate;		//城市坐标
};

struct SYCityDistance
{
	SYCityDistance()
	{
		m_nFromCity = 0;
		m_nToCity = 0;
		m_fDistance = 0.0;
	}

	int m_nFromCity;				//源城市
	int m_nToCity;					//目标城市
	double m_fDistance;				//城市之间的距离
};

typedef std::vector<int>	CityRouterDef;

void InitialSA();
double CountInitialTemperature();
BOOL JudgeOverInnerLoop( int JudgeMode );
BOOL JudgeOverExternalLoop( int JudgeMode );
double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance );
double FindCityDistance( int FromCityIndex, int ToCityIndex );

//extern std::vector<SYCity> vecCitys;
extern std::vector<SYCityDistance> vecCityDistances;
extern int CityNumber;
//extern double InitialTemperature;

class SYRouter
{
public:
	SYRouter(){
		m_CityRouter.clear();
		m_fTotalDistance = 0.0;
		createRouter();
		m_fTotalDistance = totalDistance( m_CityRouter );
	}
	
	SYRouter( CityRouterDef &preCityRouter){
		createRouter2opt( preCityRouter);//随机选择一个新的行走路径
		m_fTotalDistance = totalDistance( m_CityRouter );//计算该路径对应的总路程
	}
	void operator=(const SYRouter& srcRouter)
	{
		m_CityRouter = srcRouter.m_CityRouter;
		m_fTotalDistance = srcRouter.m_fTotalDistance;
	}
private:	
	//////////////////////////////////////////////////////////////////////////
	//生成城市行走路径
	//输入参数： 1、CityRouter	城市行走路径的vector引用，返回值
	//返回值：   空
	//注：生成1->2->3->......->n的城市行走顺序，作为算法初值
	//////////////////////////////////////////////////////////////////////////
	void createRouter()
	{
		for( int i=1;i<=CityNumber;i++ )
			m_CityRouter.push_back( i );
		
		//	random_shuffle(CityRouter.begin(), CityRouter.end()); 
	}
	//////////////////////////////////////////////////////////////////////////
	//从某行走路径的邻域中随机选择一个新的行走路径，邻域映射为2-opt
	//输入参数： 1、preCityRouter		原先行走路径的vector引用
	//		   2、CityRouter		新的行走路径的vector引用，返回值
	//返回值：   空
	//////////////////////////////////////////////////////////////////////////
	void createRouter2opt(CityRouterDef &preCityRouter)
	{
		int swapA, swapB;
		m_CityRouter = preCityRouter;		
		while(1)
		{
			swapA = (abs(rand())%CityNumber);
			swapB = (abs(rand())%CityNumber);
			if( swapA != swapB && swapB >= 0 && swapA >= 0)
			{
				int tmp = m_CityRouter[swapA];
				m_CityRouter[swapA] = m_CityRouter[swapB];
				m_CityRouter[swapB] = tmp;
				break;
			}
		}
	}

	//////////////////////////////////////////////////////////////////////////
	//根据两城市的索引获得两城市之间的路程
	//输入参数： 1、FromCityIndex		源城市的索引
	//			   2、ToCityIndex		目标城市的索引
	//	返回值：   两城市之间的路程，double型
	//////////////////////////////////////////////////////////////////////////
	double cityDistance( 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 );
	}
	//////////////////////////////////////////////////////////////////////////
	//根据给定路径计算该路径对应的总路程
	//输入参数： 1、CityRouter		给定行走路径的vector引用
	//返回值：   总路程，double型
	//////////////////////////////////////////////////////////////////////////
	double totalDistance( CityRouterDef &CityRouter )
	{
		if( CityRouter.size() != CityNumber )
			return 0.0;
		
		double totaldis = 0.0;
		for( int i=1;i<CityNumber;i++ )
		{
			totaldis += cityDistance( CityRouter[i-1], CityRouter[i] );
		}
		totaldis += cityDistance( CityRouter[CityNumber-1], CityRouter[0] );
		return totaldis;
	}
public:
	CityRouterDef m_CityRouter;
	double m_fTotalDistance;
};