『原创』算法#9 回溯法求解TSP

/*
 * @file						TSP.cpp
 * @brief						with Backtrack's way
 * @author/Univ.				taoxiaoxiao
 * @date						12-2-2013
*/
//回溯法求解TSP
#include <iostream>
#include <fstream>
using namespace std;
#define MAXN 10
#define INF 0x3f3f3f3f

int x[MAXN + 1], bestx[MAXN + 1];
int graph[MAXN+1][MAXN+1];
int cw=0, bestw=INF;
int n;

void output()
{
	cout << bestw << endl;
	for (int i = 1; i <= n; ++i)
		cout << bestx[i] << " ";
	cout << x[1] << endl;
	cout << "********************" << endl;
}

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void BacktrackTSP(int t)
{
	if (t == n)
	{
		if (graph[x[n - 1]][x[n]] != INF && graph[x[n]][1] != INF)
		{
			if (cw + graph[x[n - 1]][x[n]] + graph[x[n]][1] < bestw)
			{
				bestw = cw + graph[x[n - 1]][x[n]] + graph[x[n]][1];
				for (int i = 1; i <= n; ++i)
					bestx[i] = x[i];
			}
		}
	}
	else
	{
		for (int i= t; i <= n; ++i)
		{
			if (graph[x[t - 1]][x[i]] != INF && cw + graph[x[t - 1]][x[i]] < bestw)
			{
				swap(x[t], x[i]);
				cw += graph[x[t - 1]][x[t]];
				BacktrackTSP(t + 1);
				cw -= graph[x[t - 1]][x[t]];
				swap(x[t], x[i]);
			}
		}
	}
}

int main()
{
	system("title 回溯法解TSP");
	system("color 02");

	ifstream infile("data.txt");
	if (infile.is_open())
		cout << "open successful." << endl;
	else
	{
		cout << "open file error." << endl;
		return 0;
	}
	cout << "********************" << endl;
	while (!infile.eof())
	{
		int i, j;
		infile >> n;
		for (i = 1; i <= n; ++i)
		{
			for (j = 1; j <= n; ++j)
				infile >> graph[i][j];
		}
		for (i = 1; i <= n; ++i)
			x[i] = i;
		BacktrackTSP(2);
		output();
		cw = 0, bestw = INF;
	}
	infile.close();
	system("pause");

	return 0;
}