/*************************** BRUTEFORCE.CPP ***********************************
* TSP Algorithms : BruteForce                                      21.11.2008 *
*                                                                             *
* Brute force algorithm, tries all possible solutions in order to             *
* find the best possible solution of TSP.                                     *
*                                                             Beycan Kahraman *
******************************************************************************/

#include "BruteForce.h"

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

void BruteForce::Permutations(short k)
{
	if(k == n)
	{
		int cycle_weight = 0;
		for(int i=0; i<n; ++i)
			cycle_weight += dist[sequence[i]][sequence[(i+1)%n]];

		if(cycle_weight < min_cycle)
		{
			min_cycle = cycle_weight;

			for(int i=0; i<n; ++i)
				best_cycle[i] = sequence[i];
		}

		return;
	}

	int temp;

	for(int i=k; i<n; ++i)
	{
		temp = sequence[k];
		sequence[k] = sequence[i];
		sequence[i] = temp;

		Permutations(k+1);

		temp = sequence[k];
		sequence[k] = sequence[i];
		sequence[i] = temp;
	}
}

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

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

	//duration = clock();

	/*	Brute Force Algorithm runs here ...	*/

	Permutations(1);

	//duration = clock() - duration;

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

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

BruteForce::~BruteForce(void)
{
}
