tsp_generic.cpp

TSP的智能算法

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

//
// TSP_Generic.cpp :interface for TPS_Genetic class
////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "TSP_Generic.h"

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

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

TSP_Generic::TSP_Generic(): m_pTSPData(NULL),m_nDim(0)
{
}

void TSP_Generic::SetTSPData(TSP_data *pData)
{
	m_pTSPData = pData;
	m_nDim = pData->GetDim();
	Initialize();
}

CList<int, int>* TSP_Generic::GetBestTour()
{
	return & m_lBestTour;
}

TSP_Generic::~TSP_Generic()
{
	m_pTSPData = NULL;
}

int TSP_Generic::GetDim()
{
	return m_nDim;
}

int TSP_Generic::ComputeNNTour()
{
	if (m_pTSPData == NULL)
	{
		assert(false);
		return -1;
	}

	if (m_pTSPData->GetDim() < 1)
		return -1;

	CTypedPtrList<CPtrList, TSP_node*> aNodeQueue;
	int nSize = m_pTSPData->GetDim();

	// initially stick all into the queue
	for (int i=0; i<nSize; i++)
	{
		aNodeQueue.AddTail(m_pTSPData->GetAt(i));
	}

	// start computing (start with first city)
	TSP_node* pNodeV0 = aNodeQueue.RemoveHead(); //去掉首元素，并将此元素返回
	TSP_node* pNodeV = pNodeV0;
	TSP_node* pNodeW = NULL;
	int nPathSize = 0;		// just store the size, don't care about actual path
	int nCost = 0;			// cost of tour

	while (nPathSize != (nSize-1))
	{
		// find W - the nearest unvisited city to V
		POSITION pos = aNodeQueue.GetHeadPosition();
		POSITION posN, posOld;
		TSP_node* pNodeTmp = NULL;
		int nDist = 0;
		int nDistN = 1000000;

		while (pos != NULL)
		{
			posOld = pos;
			pNodeTmp = aNodeQueue.GetNext( pos );

//			nDist = ComputeDistance(pNodeV, pNodeTmp);	// already computed
			nDist = m_pTSPData->GetWeightAt(pNodeV->GetID()-1, pNodeTmp->GetID()-1);

			if (nDist < nDistN) 
			{
				nDistN = nDist;		// distance to nearest neighbour so far
				posN = posOld;		// point to nearest neighbour in list
				pNodeW = pNodeTmp;	// nearest neighbour
			}
		}
		aNodeQueue.RemoveAt(posN);	// 将指定位置的元素去掉

		// update tour
		nPathSize++;

		nCost += m_pTSPData->GetWeightAt(pNodeV->GetID()-1, pNodeW->GetID()-1);
		pNodeV = pNodeW;
	}
	//nPathSize++;	
	// increment tour length to come back to start

	nCost += m_pTSPData->GetWeightAt(pNodeV0->GetID()-1, pNodeV->GetID()-1);

	return nCost;
}