main.c

旅行商问题的动态规划解法 (XMU)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

struct node {
		int length;
		int prevcity;
};

int main()
{
		clock_t start,end;
		int n;
		int i, j, k, l;
		int max, temp, min, minprev;
		int ** city;
		struct node ** f;
		int ** sets;
		char filename[20];

		printf("请输入文件名:\n");
		scanf("%s", filename);
		if (! freopen(filename, "r", stdin)){
			printf("文件打开失败");
			return 0;
		}
		//freopen("TSP20.txt", "r", stdin);

		//printf("请输入需要遍历的城市数:\n");
		scanf("%d", &n);
		max = 1;
		for (i = 1; i <= n; i++)
				max = max << 1;

		//printf("请输入各城市间的路径:\n");
		city = (int **) malloc((n + 1) * sizeof(int *));
		f = (struct node **) malloc((n + 1) * sizeof(struct node *));
		for (i = 1; i <= n; i++) {
				city[i] = (int *) malloc((n + 1) * sizeof(int));
				f[i] = (struct node *) malloc(max * sizeof(struct node));
				for (j = 1; j <= n; j++)
						scanf("%d", &city[i][j]);
		}

		start = clock();

		//用位表示城市，若值为1表示城市出现。set[i]记录有i个城市的集合
		sets = (int **) malloc((n - 1) * sizeof(int *));
		for (i = 1; i < n - 1; i++)
			sets[i] = (int *) malloc(max * sizeof(int));
		sets[1][0] = n - 1;   //sets[i][0]用于记录包含i个元素的集合个数
		for (i = 1, temp = 2; i < n; i++, temp = temp << 1)
			sets[1][i] = temp;
		for (k = 2; k < n - 1; k++) {
			sets[k][0] = 0;
			l = k - 1;
			for (i = 2, temp = 2; i <= n; i++, temp = temp << 1)
				for (j = 1; j <= sets[l][0]; j++)
					if (temp > sets[l][j])	//避免相同组合反复加入set中
						sets[k][++sets[k][0]] = temp + sets[l][j];
		}



		for (i = 2; i <= n; i++) {
				f[i][0].length = city[i][1];
				f[i][0].prevcity = 1;
		}

		for (k = 1; k < n - 1; k++) {
			for (i = 2; i <= n; i++) {
				for (l = 1; l <= sets[k][0]; l++) {
					min = INT_MAX;
					if (sets[k][l] & (1 << (i - 1)))   // i在set中
						continue;
					for (j = 2, temp = 2; j <=n; j++, temp = temp << 1) {
						if (sets[k][l] & temp) // j在set中
							if (min > city[i][j] + f[j][sets[k][l] - temp].length) {
								min = city[i][j] + f[j][sets[k][l] - temp].length;
								minprev = j;
							}
					}
					f[i][sets[k][l]].length = min;
					f[i][sets[k][l]].prevcity = minprev;
				}
			}
		}

		i = max - 2;
		min = city[1][2] + f[2][i - 2].length;
		minprev = 2;
		for(j = 3, temp = 4; j <= n; j++, temp = temp << 1)
				if (min > city[1][j] + f[j][i - temp].length) {
						min = city[1][j] + f[j][i - temp].length;
						minprev = j;
				}
		f[1][i].length = min;
		f[1][i].prevcity = minprev;
		end = clock();


		printf("一条最短路线的长度:\n");
		printf(" %d\n", min);
		printf("路线如下:\n");
		printf(" 1 --");
		j = minprev;
		temp = max - 2;		
		while (j != 1) {
				printf(" %d --", j);
				temp = temp - (1 << (j - 1));
				j = f[j][temp].prevcity;	
		}
		printf(" 1\n");
		printf("寻找此路线所花费的时间为:\n %f", (double)(end - start) / CLOCKS_PER_SEC );
}