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

CDynamicTSP::CDynamicTSP(void)
{
	m_pBitArray = NULL;
	m_pDP = NULL;

	Reset();
}

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

void CDynamicTSP::Reset()
{
	if (m_pDP)
	{
		for (int i=0; i<m_nPathCount; i++)
		{
			delete [] m_pDP[i];
		}
		delete [] m_pDP;
	}
	m_pDP = NULL;

	if (m_pBitArray)
	{
		delete [] m_pBitArray;
	}
	m_pBitArray = NULL;

	m_nSubSetCount = 0;
}

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

	Reset();

	CGreedyTSP::SetPathData(vecPathData, ptStart);

	// new
	m_pBitArray = new int[m_nPathCount];
	m_pDP = new SDP*[m_nPathCount];

	m_nSubSetCount = 1<<m_nPathCount;

	for (int i=0; i<m_nPathCount; i++)
	{
		m_pBitArray[i] = 1<<i;

		m_pDP[i] = new SDP[m_nSubSetCount];
		memset(m_pDP[i], 0, sizeof(SDP)*m_nSubSetCount);
	}
}

int get_bit_index (int path)
{
	for (int i=0; i<32; i++)
	{
		if ((path>>i) & 1)
		{
			return i;
		}
	}
	return -1;
}

double CDynamicTSP::TSP_Process(int nFrom, int nPathSet, int nLen)
{
	// setÀÌ ÇϳªÀ϶§
	if (nLen == 1)
	{
		int to = get_bit_index(nPathSet);
		return m_pPathGraph[nFrom][to];
	}

	// ÀúÀåÇÑ °ªÀ» ÀÌ¿ë
	if (m_pDP[nFrom][nPathSet].dMinCost)
	{
		return m_pDP[nFrom][nPathSet].dMinCost;
	}

	int nMinPathSet = 0;
	double dCost = DBL_MAX;
	
	for(int i=0; i<m_nPathCount; i++)
	{
		if (m_pBitArray[i] & nPathSet)
		{
			// »õ·Î¿î°æ·Î´Â¸ñÀûÁönode¸¦Á¦¿ÜÇѳª¸ÓÁöµµ½Ãµé
			int nNewPathSet = nPathSet - m_pBitArray[i];

			// f(N,{N-1,N-2...1}) = cost[N][N-1] + f(N-1, {N-2,N-3...1})
			double dNewCost = m_pPathGraph[nFrom][i] + TSP_Process(i, nNewPathSet, nLen-1);

			if (dCost > dNewCost)
			{
				nMinPathSet = nNewPathSet ;
				dCost = dNewCost ;
			}
		}
	}

	// ÃÖ¼Òºñ¿ëÀ»ÀúÀå
	m_pDP[nFrom][nPathSet].dMinCost = dCost ;
	m_pDP[nFrom][nPathSet].nPathSet = nMinPathSet ;

	return dCost;
}

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

	if (m_nSubSetCount<1) return -1.0;

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

	int nPathSet = 0;
	for(int i=0; i<m_nPathCount; i++)
	{
		nPathSet |= 1<<i ;
	}

	// start node
	if (m_nStartIndex==-1) m_nStartIndex = 0;
	int nNewPathSet = (nPathSet & ~m_pBitArray[m_nStartIndex]);

	// tsp process
	m_dTotalDistance = TSP_Process(m_nStartIndex, nNewPathSet, m_nPathCount-1);

	// get result
	int nIndex = 0;
	m_vecPathResult[nIndex++] = m_nStartIndex;

	int nNextPathSet = m_pDP[m_nStartIndex][nNewPathSet].nPathSet;
	int nNextNode = get_bit_index(nNewPathSet-nNextPathSet);

	do
	{
		m_vecPathResult[nIndex++] = nNextNode;
		nNewPathSet = nNextPathSet ;
		nNextPathSet = m_pDP[nNextNode][nNextPathSet].nPathSet;

	} while ((nNextNode=get_bit_index(nNewPathSet-nNextPathSet))!=-1);

	SortingPathResult();

	return (m_dTotalDistance=GetTotalDistance());
}