/********************** NEARESTNEIGHBOR.CPP ***********************************
* TSP Algorithms : NearestNeighbor                                 21.11.2008 *
*                                                                             *
* - Start at vertex v1                                                        *
* - Trace (v1,v2) which is the shortest edge from v1.                         *
* - Leave v2 along (v2,v3) the shortest edge from v2.                         *
* - Keep the cycle simple.                                                    *
* - Continue until every vertex has been visited.                             *
* - Complete the cycle by edge (vn,v1).                                       *
*                                                             Beycan Kahraman *
******************************************************************************/

#include "NearestNeighbor.h"

NearestNeighbor::NearestNeighbor(short dist[][SZ], int n) : AlgorithmTSP(dist, n)
{
	Run();
}

void NearestNeighbor::Run()
{
	__int64 freq, start, end, diff;

	QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
	QueryPerformanceCounter((LARGE_INTEGER*)&start);

	//duration = clock();

	/*	Nearest Neighbor Algorithm runs here ...	*/

	int minDistance;
	int minNo;

	for(int i=0; i<n; ++i)
		sequence[i] = -1;

	min_cycle = 0;
	best_cycle[0] = 0;
	sequence[0] = 1;

	for(int i=0; i<n-1; ++i)
	{
		minNo = 0;
		minDistance = 32767;

		for(int j=1; j<n; ++j)
		{
			if(j == best_cycle[i]) continue;

			if(sequence[j] < 0 && dist[best_cycle[i]][j] < minDistance)
			{
				minNo = j;
				minDistance = dist[best_cycle[i]][minNo];
			}
		}

		min_cycle += minDistance;
		sequence[minNo] = 1;
		best_cycle[i+1] = minNo;

	}

	min_cycle += dist[best_cycle[n-1]][0];

	//duration = clock() - duration;

	QueryPerformanceCounter((LARGE_INTEGER*)&end);
	diff = ((end - start) * 1000000) / freq;

	duration = (unsigned int)(diff & 0xffffffff);
}

NearestNeighbor::~NearestNeighbor(void)
{
}
