tsp_data.cpp

TSP的智能算法

////////////////////////////////////////////////////////////
// This virsion is AntSystem 1.0
// author: zhaochaoqing ChongQing University
//
//the author can be contacted at:
//   Email: [e-mail]
//
////////////////////////////////////////////////////////////

//
// TSP_data.cpp :interface for TPS_data class
////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "TSP_data.h"
#include "TSP_node.h"


#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//using namespace std;

TSP_data::TSP_data(): m_nDim(0), m_aNodes(NULL), 
m_aWeights(NULL),m_dMaxX(1.0), m_dMaxY(1.0)
{

}

void TSP_data::Initialize(int nSize)
{
	ASSERT(m_aNodes == NULL);		// must be NULL
	ASSERT(m_aWeights == NULL);

	m_nDim = nSize;

	if (m_aNodes == NULL)
	{
		m_aNodes = new TSP_node*[GetDim()];
	}

	if (m_aWeights == NULL)
	{
		// create 2D matrix
		m_aWeights = new int*[GetDim()];

		for (int i=0; i<GetDim(); i++)
		{
			m_aWeights[i] = new int[GetDim()];
		}
	}
}

TSP_node* TSP_data::GetAt(int nIdx)
{
	ASSERT((m_aNodes != NULL) && (nIdx >= 0) && (nIdx < GetDim()));

	if ((m_aNodes != NULL) && (nIdx >= 0) && (nIdx < GetDim()))
		return m_aNodes[nIdx];

	return NULL;
}
int TSP_data::GetDim() const
{
	return m_nDim;
}

TSP_data::~TSP_data()
{

}

int TSP_data::ComputeDistance(TSP_node *ps, TSP_node *pd)
{
	double dx=ps->GetX() - pd->GetX();
	double dy=ps->GetY() - pd->GetY();
	double dDist=sqrt(dx*dx+dy*dy); 
	 int nDist=int(dDist+0.5);//各路径均增加0.5
	return nDist;
}

void TSP_data::ReadFile()
{
	ifstream Rd;
	//Rd.open("20Cities.txt");
	Rd.open("eil51.txt");
	//Rd.open("ch130.txt");
	//Rd.open("eil76.txt");
	//Rd.open("eil101.txt");
	//Rd.open("ts225.txt");
	Rd>>m_nDim;  //输入问题的规模
	Initialize(m_nDim);
	assert(m_aNodes !=NULL); 
	int i=0;

	while(Rd.eof()==0 && i<m_nDim)
	{
		int Index=0;
		double dx=0.0,dy=0.0;
		Rd>>Index>>dx>>dy;
		if (dx > m_dMaxX)
		{
			m_dMaxX = dx;
		}
		if (dy > m_dMaxY)
		{
			m_dMaxY = dy;
		}
		TSP_node *pNode=new TSP_node(Index,dx,dy);
		m_aNodes[i]=pNode;
//		m_aNodes[i]->print();
		i++;
	}
	for (int k=0; k<GetDim(); k++)
	{
		for (int h=0; h<GetDim(); h++)
		{
			m_aWeights[k][h] = ComputeDistance(GetAt(k), GetAt(h));
		//	cout<<m_aWeights[k][h]<<" ";
		}
	}
	Rd.close();
}

void TSP_data::DistoryData()
{
		if (m_aNodes != NULL)
	{
		for (int i=0; i<GetDim(); i++)
		{
			delete m_aNodes[i];
		}
		delete []m_aNodes;
	}

	if (m_aWeights != NULL)
	{
		// destroy 2D matrix
		for (int i=0; i<GetDim(); i++)
		{
			delete[] m_aWeights[i];
		}
		delete[] m_aWeights;
	}
}