maptsp.cpp

用c+++实现的遗传算法解决tsp（旅行商）问题源码

#include "mapTSP.h"

#include <stdlib.h>
#include <math.h>

#define random( x ) ( rand() % x )


void CmapTSP::CreateCitiesCircular()
{
	
	vector<CoOrd> vecCities;
	
	for( int i=0; i<m_NumCities; i++ )
	{
		CoOrd ThisCity;

		ThisCity.x = random( 1024 );
		ThisCity.y = random( 768 );

		m_vecCityCoOrds.push_back( ThisCity );
	}
	

	/*
	//first caculate the radius of spread and the origin
	const int margin = 50;
	
	double radius;

	if (m_MapHeight < m_MapWidth)
	{
		radius = (m_MapHeight / 2) - margin;
	}

	else
	{
		radius = (m_MapWidth / 2) - margin;
	}
	
	CoOrd origin(m_MapWidth / 2, m_MapHeight / 2);

	//calculate angle division between adjacent cities.
	double SegmentSize = 2 * pi / m_NumCities;
	
	double angle = 0;
	
	vector<CoOrd> vecCities;
	
	while (angle < 2 * pi)
	{
		CoOrd ThisCity;
		
		ThisCity.x = radius * sin(angle) + origin.x;
		ThisCity.y = radius * cos(angle) + origin.y;
		
		m_vecCityCoOrds.push_back(ThisCity);
		
		angle += SegmentSize;
	}
	*/
}

void CmapTSP::Resize(const int new_width, const int new_height)
{
	m_MapWidth  = new_width;
	m_MapHeight = new_height;

	m_vecCityCoOrds.clear();

	CreateCitiesCircular();
	
	CalculateBestPossibleRoute();
} 

double CmapTSP::GetTourLength( const vector<int> &route )
{
	double TotalDistance = 0;

	for( int i=0; i<route.size() - 1; i++ )
	{
		int city1 = route[i];
		int city2 = route[i+1];

		TotalDistance += CalculateA_to_B( m_vecCityCoOrds[city1], m_vecCityCoOrds[city2] );
	}

	int last = route[route.size() - 1];
	int first = route[0];

	TotalDistance += CalculateA_to_B( m_vecCityCoOrds[last], m_vecCityCoOrds[first] );

	return TotalDistance;
}

//CHB:计算两座城市间的距离
double CmapTSP::CalculateA_to_B(const CoOrd &city1, const CoOrd &city2)
{
	double xDist = city1.x - city2.x;
	double yDist = city1.y - city2.y;
	
	return sqrt(xDist*xDist + yDist*yDist);
}

//CHB:计算最优路径，确定什么时候终止程序
void CmapTSP::CalculateBestPossibleRoute()
{
	m_dBestPossibleRoute = 0;
	
	for( int city=0; city<m_vecCityCoOrds.size() - 1; city++ )
	{
		m_dBestPossibleRoute += CalculateA_to_B( m_vecCityCoOrds[city], m_vecCityCoOrds[city+1] );

		m_dBestPossibleRoute += EPSILON;
	}

	m_dBestPossibleRoute += CalculateA_to_B(m_vecCityCoOrds[m_vecCityCoOrds.size()-1], 
		                                    m_vecCityCoOrds[0]);
}