tsp.cpp

旅行商问题

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_N	15
#define MAX_INT	0x7fffffff

int N; // 图中节点的个数
int w[MAX_N][MAX_N]; //w[i][j]表示从i与j之间的权值，在此为距离 
bool adj[MAX_N][MAX_N]; //adj[i][j]=0表示i和j没有边，=1表示有边相连 

int best = MAX_INT;
int stack[MAX_N];
int x[MAX_N];//当前路径
int best_path_dfs[MAX_N];
int best_path_stack[MAX_N];
int pt1;
bool bj[MAX_N];//标记位 
int p=0;
void dfs(int dp, int j, int len)
{ 
	int i;
	if(dp==N && adj[j][pt1] && len+w[j][pt1] < best)//保留当前最优路径
	{
		len += w[j][pt1];
		if(best > len)
		{
			best = len;
			for(int m=0;m<N;m++)
				best_path_dfs[m]=x[m];
		}
		return;
	}
	for(i=0; i<N; i++)
		if(!bj[i] && adj[i][j] && len+w[i][j] < best)
		{
			bj[i] = 1;
			x[++p]=i;
		//	best_path_dfs[i]＝i;
			dfs(dp+1, i, len+w[i][j]);
			p--;
			bj[i] = 0;
		}
}

int TSP_dfs(int in_pt1, int in_N, int in_w[][MAX_N], bool in_adj[][MAX_N]) // 连通图的最短路径 
{
	N = in_N;
	pt1 = in_pt1;
	memcpy(w, in_w, N*N*sizeof(in_w[0][0]));
	memcpy(adj, in_adj, N*N*sizeof(in_adj[0][0]));
	best = MAX_INT;
	memset(bj, 0, sizeof(bj));
	bj[pt1] = 1;
	x[p]=0;
	dfs(1, pt1, 0);
	bj[pt1] = 0;
	return best;
}

int Len[MAX_N+1];

int TSP_stack(int in_pt1, int in_N, int in_w[][MAX_N], bool in_adj[][MAX_N]) // 连通图的最短路径 
{
	N = in_N;
	pt1 = in_pt1;
	memcpy(w, in_w, N*N*sizeof(in_w[0][0]));
	memcpy(adj, in_adj, N*N*sizeof(in_adj[0][0]));
	best = MAX_INT;
	//设置标记位
	memset(bj, 0, sizeof(bj));
	bj[pt1] = 1;
	int dp;
	dp  = 0;
	stack[0] = pt1; // 起点 
	dp  = 1;
	stack[1] = 0; //从0 到 N-1
	Len[0] = 0;
	while(stack[1] < N)
	{
			if(stack[dp] == N)
			{
					stack[dp] = 0;
					bj[stack[dp-1]] = 0;
					stack[dp-1]++;
					dp--; // 回溯
			}
			else 
			{
				if(!bj[stack[dp]] && adj[stack[dp]][stack[dp-1]] 
					&& Len[dp-1]+w[stack[dp]][stack[dp-1]] < best)
				{	//如果节点i有意义 
						bj[stack[dp]] = 1;
						Len[dp] = Len[dp-1] + w[stack[dp]][stack[dp-1]];
						dp ++; 
						if(dp == N)
						{
							Len[dp] = Len[dp-1] +w[stack[N-1]][pt1];
							if(best > Len[dp]){
								best = Len[dp];
								memcpy(best_path_stack, stack, sizeof(stack));
							}
							bj[stack[N-1]] = 0;
							stack[N-1] ++;
							dp --;
						}
				}
				else 
					stack[dp]++;
			}  
	}
	bj[pt1] = 0;
	return best;
}
	

int main()
{
	int i, j;
	printf("请输入结点数 N= ");
	scanf("%d", &N);
	for(i=0; i<N; i++)

		for(j=0; j<N; j++)
		{
			w[i][j] = rand()%100+1;
			w[j][i] = w[i][j];
		}
	for(i=0; i<N; i++)
		for(j=0; j<N; j++)
		{
			adj[i][j] = 1;
			if(i==j) w[i][j] = 0;
			printf("%4d%c", w[i][j], j==N-1?'\n':' ');
		}
	int rtn_dfs = TSP_dfs(0, N, w, adj);
	printf("递归回溯法：\n");
	printf("rtn_def   = %d\n", rtn_dfs);
	for(i=0;i<N-1;i++)
		printf("%d->",best_path_dfs[i]);
	printf("%d\n",best_path_dfs[i]);

	int rtn_stack = TSP_stack(0, N, w, adj);
	printf("使用栈代替递归的方法：\n");
	printf("rtn_stack = %d\n", rtn_stack);
	for(i=0;i<N-1;i++)
		printf("%d->",best_path_stack[i]);
	printf("%d\n",best_path_stack[i]);
	
	return 0;
}