traveling.cpp

研究生算法作业著名的旅行者问题

// Traveling.cpp: implementation of the CTraveling class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Traveler.h"
#include "Traveling.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//##ModelId=40863F410288
CTraveling::CTraveling()
{

}

//##ModelId=40863F410292
CTraveling::~CTraveling()
{

}


//##ModelId=40863F410300
void CTraveling::Backtrack(int i)
{
	if ( i == n)
	{
		if(a[x[n-1]][x[n]] != NoEdge &&
			a[x[n]][0] != NoEdge &&
			(cc + a[x[n-1]][x[n]] + a[x[n]][0] < bestc ||
			bestc == NoEdge))
		{
			for(int j =1; j<=n; j++)
				bestx[j] = x[j];
			int size = sizeof(bestx);
			size = sizeof(x);
			bestc = cc + a[x[n-1]][x[n]] + a[x[n]][0];
			
		}
	}
	else
	{
		for (int j = i; j <= n; j++)
		{
			if (a[x[i-1]][x[j]] != NoEdge &&
				(cc + a[x[i-1]][x[i]] < bestc ||
				bestc == NoEdge))
			{
				Swap(x[i],x[j]);
				cc += a[x[i-1]][x[i]];
				Backtrack(i+1);
				cc -=a[x[i-1]][x[i]];
				Swap(x[i],x[j]);
			}
		}
	}
}

//##ModelId=40863F41029C
void CTraveling::SetCityCount(const int p)
{
	/*
	if (p < 0)
		return;
	this ->n = p;

	//所有的城市
	if (this ->city !=NULL)
		delete[] this->city;
	city = new int[n * n];

	//邻接矩阵
	if (this ->a !=NULL)
		delete[] this->a;
	a = new int* [n];

	for(int i=0;i<n;i++)
		a[i] = city + i * n;

	//最优解
	if (this->x !=NULL)
		delete[] this->x;
	this->x = new int[n+1];
*/
	//当前最优解
	//if (this->best !=NULL)
	//	delete[] this->best;
//	this->best = new int[n+1];
}

//##ModelId=40863F4102BB
int CTraveling::TSP(int **a,int v[],int n)
{
	
	this->x = new int[n+1];
	//置x为单位阵列
	for(int i=1;i<=n;i++)
		x[i] = i-1;
	x[0]=0;
	this->n = n;
	this->bestx = v;
	this->a = a;
	this->bestc = NoEdge;
	this->cc = 0;
	Backtrack(2);
	delete[] this->x;
	return bestc;
}
//##ModelId=40863F4102E2
void CTraveling::Swap(int &a, int &b)
{
	int t=a;
	a = b;
	b = t;
}