/*********************** SIMPLEAPPROACH.CPP ***********************************
* TSP Algorithms : SimpleApproach                                  21.11.2008 *
*                                                                             *
* - Find a Hamilton cycle C                                                   *
* - Creating new cycles that has a better solution                            *
*     - deleting edges vi-vi+1 and vj-vj+1                                    *
*     - adding edges vi-vj and vi+1-vj+1                                      *
*     - If for some i and j,                                                  *
*       w(vi-vj) + w(vi+1-vj+1) < w(vi-vi+1) + w(vj-vj+1)                     *
* - Cij is an improvement on C.                                               *
*                                                             Beycan Kahraman *
******************************************************************************/

#include "SimpleApproach.h"

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

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

	QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
	QueryPerformanceCounter((LARGE_INTEGER*)&start);
	
	//duration = clock();

	/*	Simple Approach Algorithm runs here ...	*/

	bool added = true;
	int *temp = new int[n];
	int count;
	int new_couple;
	int old_couple;

	min_cycle = 0;

	for(int i=0; i<n; ++i)
		min_cycle += dist[sequence[i]][sequence[(i+1)%n]];

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

	while(added)
	{
		added = false;

		for(int t=0; t<n; ++t)
			for(int i=t; i<n+t; ++i)
				for(int j=i+2; j<n+i-1; ++j)
				{
					new_couple = dist[sequence[i%n]][sequence[j%n]] + dist[sequence[(i+1)%n]][sequence[(j+1)%n]];
					old_couple = dist[sequence[i%n]][sequence[(i+1)%n]] + dist[sequence[j%n]][sequence[(j+1)%n]];

					if(new_couple < old_couple)
					{
						count = 0;
						for(int k=i+1; k<j+1; ++k)
							temp[count++] = sequence[k%n];
						count = 0;
						for(int k=j; k>i; --k)
							sequence[k%n] = temp[count++];

						min_cycle -= (old_couple - new_couple);
						added = true;
					}
				}
	}

	//duration = clock() - duration;

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

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

SimpleApproach::~SimpleApproach(void)
{
}
