回溯法旅行商问题.cpp

算法设计与分析的经典程序

#include <stdio.h>
using namespace std;
template <class Type> 
class Travel{
friend Type TSP(int **,int [],int,Type);
private:void Backtrack(int);
	int n, 
Type **a,
     cc, bestc, NoEdge;
};
template <class Type>
void Travel <Type> :: Backtrack(int i)
{if (i==n) {if (a[x[n-1]][x[n]] != NoEdge &&
	a[x[n]][1] != NoEdge &&
	(cc+a[x[n-1]][x[n]]+a[x[n]][1] < bestc ||
	bestc == NoEdge)){
	for (int j=1;j<=n;j++)	best[j] = x[j] ;
	bestc =cc + a[x[n-1]][x[n]] + a[x[n]][1];}
	}
	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[j]];
	 Backtrack(i+1);
	 cc -= a[x[i-1]][x[j]];
	 Swap(x[i],x[j]);}
}
}
template <class Type>
Type TSP(Type **a,int v[], int n,Type NoEdge)
{Travel <Type> Y;Y.x = new int [n+1];
for(int i=1;i<=n;i++)Y.x[i] =i;
Y.a =a;Y.n = n;
Y.bestc = NoEdge;
Y.bestx =v;Y.NoEdge = NoEdge;
delete [] Y.x;
return Y.bestc;
}