backtrack--tsp.c

使用回溯法求解TSP问题

#include <stdio.h>
#define N 13
int x[N],bestc=32767,cc=0,a[N][N];
int tsp_trackback(int i,int n)
{
	int j,temp;
	if(i==n)
	{
		if(bestc==32767||cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc)
			bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];
	}
	else
	{
		for(j=i;j<=n;j++)
			if(bestc==32767||cc+a[x[i-1]][x[j]]<bestc)
			{
				temp=x[i];x[i]=x[j];x[j]=temp; 
				cc+=a[x[i-1]][x[i]];
				tsp_trackback(i+1,n);
				cc-=a[x[i-1]][x[i]];
				temp=x[i];x[i]=x[j];x[j]=temp;
			}
	}
	return bestc;
}

int main()
{
	int i,j,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(i=1;i<=n;i++)
		x[i]=i;
	bestc=tsp_trackback(2,n);
	printf("%d\n",bestc);
	return 0;
}