#include "stdafx.h"
#include "AnnealingTSP.h"
#include <math.h>
#include <float.h>

CAnnealingTSP::CAnnealingTSP(void)
{
	Reset();
}

CAnnealingTSP::~CAnnealingTSP(void)
{
	Reset();
}

void CAnnealingTSP::Reset()
{	
	m_vecPathCurrent.clear();

	m_dTemperature = 1000.0;					// * The current temperature.
	m_dTotalDistanceCurrent = DBL_MAX;		// * The length of the current path.
}

void CAnnealingTSP::SetPathData(const VectorPathData& vecPathData, const SPathData& ptStart)
{
	if ((int)vecPathData.size()<1) return;

	Reset();

	CGreedyTSP::SetPathData(vecPathData, ptStart);

	m_vecPathCurrent.resize(m_nPathCount);
}

bool CAnnealingTSP::anneal(double d)
{
	if (m_dTemperature < 1.0E-4) 
	{
		if (d > 0.0)
			return true;
		else
			return false;
	}

	double random = double(rand())/(1.0*RAND_MAX);

	if (random < exp(d / m_dTemperature))
		return true;
	else
		return false;
}

double CAnnealingTSP::getLength(int i, int j)
{
	int c1 = m_vecPathCurrent[i % m_nPathCount];
	int c2 = m_vecPathCurrent[j % m_nPathCount];

	return m_pPathGraph[c1][c2];
}

double CAnnealingTSP::CalculateTSP()
{
	if (m_nPathCount<1) return -1.0;

	if (m_nPathCount<2) 
	{
		return (m_dTotalDistance=GetTotalDistance());
	}

	srand((unsigned)time(NULL));
	int nCycle = 1;
	int nSameCount = 0;

	// copy path result
	m_vecPathCurrent = m_vecPathResult;
	m_dTotalDistanceCurrent = m_dTotalDistance;

	while (nSameCount<50) 
	{
		// make adjustments to city order(annealing)
		for (int j2 = 0; j2 < m_nPathCount * m_nPathCount; j2++)
		{
			int i1 = rand() % m_nPathCount;
			int j1 = rand() % m_nPathCount;

			double d = getLength(i1, i1 + 1) + getLength(j1, j1 + 1) - getLength(i1, j1) - getLength(i1 + 1, j1 + 1);

			if (anneal(d)) 
			{
				if (j1 < i1) 
				{
					int k1 = i1;
					i1 = j1;
					j1 = k1;
				}

				for (; j1 > i1; j1--) 
				{
					int i2 = m_vecPathCurrent[i1 + 1];
					m_vecPathCurrent[i1 + 1] = m_vecPathCurrent[j1];
					m_vecPathCurrent[j1] = i2;
					i1++;
				}
			}
		}

		// See if this improved anything
		m_dTotalDistanceCurrent = GetTotalDistance(m_vecPathCurrent);

		if (m_dTotalDistanceCurrent < m_dTotalDistance) 
		{
			m_vecPathResult = m_vecPathCurrent;
			m_dTotalDistance = m_dTotalDistanceCurrent;
			nSameCount = 0;
		} 
		else
		{
			nSameCount++;
		}

		m_dTemperature = m_dDelta * m_dTemperature;

		nCycle++;
	}


	SortingPathResult();

	return m_dTotalDistance;
}