tsp问题.c

图论中的经典TSP旅行商问题的“便宜”算法

#include "stdio.h"
#include "stdlib.h"

//#define INDEX(N, i, j) (((N)-1)*(i)-((i)*((i)-1)/2)+(j))

int INDEX(int N, int i, int j);
void Insert(int *V, int i, int j, int C);
void Delete(int *V, int i, int C);

int main()
{
	int N;	//结点个数
	int i, j, SC = 0, TC = 0, k, t, t1, t2, step = 0;
	float quan = 0.0;
	float *W;	//权重矩阵，压缩存储
	int *S, *T;	//存储结点序列
	printf("输入结点个数:");
	scanf("%d", &N);
	W = (float *)malloc((INDEX(N, N - 1, N - 1) + 1) * sizeof(float));
	S = (int *)malloc((N - 1) * sizeof(int));
	T = (int *)malloc((N + 1) * sizeof(int));
	//下面接受输入
	for(i = 0; i < N; i++)
	{
		W[INDEX(N, i, i)] = 0;
		for(j = i + 1; j < N; j++)
		{
			printf("输入边 V%d <-> V%d 的权重:", i + 1, j + 1);
			scanf("%f", &W[INDEX(N, i ,j)]);
		}
	}
	printf("输入的数据以矩阵形式表示如下:\n");
	printf("---------------------------------\n\n");
	for(i = 0; i < 5; i++)
	{
		for(k = 0; k < 5; k++)
			printf("%6.2f  ", W[INDEX(N, i, k)]);
		printf("\n");
	}
	printf("\n------------------------------\n");
	//初始化数组 S，T
	SC = N - 1;
	TC = 2;
	for(i = 0; i < TC; i++)
		T[i] = 0;
	for(i = 0; i < SC; i++)
		S[i] = i + 1;
	k = 0;
	for(i = 0; i < SC; i++)
		W[INDEX(N, S[i], k)] = W[INDEX(N, S[i], 0)];
	printf("现在开始进行计算:\n");
	while(SC > 0)
	{
		int minj, mint, mint1, mint2;
		float MINW = W[INDEX(N, S[0], T[0])];
		step++;
		j = 0;
		t = 0;
		minj = S[0];
		mint = T[0];
		t1 = 0;
		t2 = 1;
		mint1 = T[t1];
		mint2 = T[t2];
		for(i = 0; i < SC; i++)
		{
			for(k = 0; k < TC; k++)
			{
				if(W[INDEX(N, S[i], T[k])] < MINW)
				{
					MINW = W[INDEX(N, S[i], T[k])];
					j = i;
					t = k;
					minj = S[i];
					mint = T[k];
				}
			}
		}
		if((t1 = t - 1) < 0)
			t1 = t;
		if((t2 = t + 1) >= TC)
			t2 = t;
		mint1 = T[t1];
		mint2 = T[t2];
		if(W[INDEX(N, minj, mint1)] - W[INDEX(N, mint, mint1)] <=
				W[INDEX(N, minj, mint2)] - W[INDEX(N, mint, mint2)])
			Insert(T, t1 + 1, minj, TC);
		else
			Insert(T, t + 1, minj, TC);
		Delete(S, j, SC);
		SC--;
		TC++;
		if(SC <= 0)
		{
			printf("第 %d 步，亦是最后一步状态如下:\n", step);
			printf("-------------------------------------------\n");
			printf("T 集合:");
			for(i = 0; i < TC; i++)
				printf("%d  ", T[i] + 1);
			printf("\nS 集合:");
			for(i = 0; i < SC; i++)
				printf("%d  ", S[i] + 1);
			printf("\nT -> S 的最短边为: W(%d, %d) = %6.2f\n", minj + 1, mint + 1, MINW);
			printf("j, t, t1, t2的值分别为: %d, %d, %d, %d\n", minj + 1, mint + 1, mint1 + 1, mint2 + 1);
			printf("-----------------------------------------\n");
			break;
		}
		else
		{
			printf("第 %d 步状态如下:\n", step);
			printf("-------------------------------------------\n");
			printf("T 集合:");
			for(i = 0; i < TC; i++)
				printf("%d  ", T[i] + 1);
			printf("\nS 集合:");
			for(i = 0; i < SC; i++)
				printf("%d  ", S[i] + 1);
			printf("\nT -> S 的最短边为: W(%d, %d) = %6.2f\n", minj + 1, mint + 1, MINW);
			printf("j, t, t1, t2的值分别为: %d, %d, %d, %d\n", minj + 1, mint + 1, mint1 + 1, mint2 + 1);
			printf("-----------------------------------------\n");
		}
		/*
		else
		{
			for(i = 0; i < SC; i++)
			{
				for(k = 0; k < TC; k++)
				{
					W[INDEX(N, S[i], T[k])] = W[INDEX(N, S[i], T[k])] > W[INDEX(N, S[i], minj)] ? 
															W[INDEX(N, S[i], minj)] : W[INDEX(N, S[i], T[k])];
				}
			}
		}
		*/
	}
	printf("最后结果如下:\n");
	printf("-------------------------------\n");
	printf("路径为:\n");
	for(i = 0; i < TC; i++)
	{
		printf("%d  ", T[i] + 1);
		if(i < TC - 1)
			quan += W[INDEX(N, T[i], T[i + 1])];
	}
	printf("\n最小路径的权之和为: %6.2f\n", quan);
	printf("---------程序结束------------\n");
	free(W);
	free(S);
	free(T);
	return 0;
}

int INDEX(int N, int i, int j)
{
	if(i <= j)
		return ((N - 1) * i - (i * (i - 1)/2) + j);
	else
		return ((N - 1) * j - (j * (j - 1)/2) + i);
}

void Insert(int *V, int i, int j, int C)
{
	int k;
	for(k = C; k > i; k--)
		V[k] = V[k - 1];
	V[k] = j;
}
void Delete(int *V, int i, int C)
{
	int k;
	for(k = i; k < C - 1; k++)
		V[k] = V[k + 1];
}