基于贪心算法的TSP问题（c语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了基于贪心算法的TSP问题（c语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

data.txt

1 6734 1453
2 2233 10
3 5530 1424
4 401 841
5 3082 1644
6 7608 4458
7 7573 3716
8 7265 1268
9 6898 1885
10 1112 2049
11 5468 2606
12 5989 2873
13 4706 2674
14 4612 2035
15 6347 2683
16 6107 669
17 7611 5184
18 7462 3590
19 7732 4723
20 5900 3561
21 4483 3369
22 6101 1110
23 5199 2182
24 1633 2809
25 4307 2322
26 675 1006
27 7555 4819
28 7541 3981
29 3177 756
30 7352 4506
31 7545 2801
32 3245 3305
33 6426 3173
34 4608 1198
35 23 2216
36 7248 3779
37 7762 4595
38 7392 2244
39 3484 2829
40 6271 2135
41 4985 140
42 1916 1569
43 7280 4899
44 7509 3239
45 10 2676
46 6807 2993
47 5185 3258
48 3023 1942

代码

/*********************************************************************************************************************
 * TSP 算例来自TSPLIB，att48.tsp 数据集，其中有 48 个城市，距离为伪欧式距离
 * TSPLIB is a library of sample instances for the TSP (and related problems)from various sources and of various types.
 * 目前最佳解总距离为 10628，其中距离的计算方式为 sqrt((x*x + y*y)/10)
 * 使用贪心策略求解，解集总距离为 12861，可见贪心策略只是局部最优解
**********************************************************************************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

// 城市数量 N
#define N 48
// 城市距离矩阵
int distance[N][N];

/***********************************************************************
 * Function   ：init()
 * Description：从文件中读取城市坐标，并计算城市之间的距离 distance[N][N]
 * Input      ：void
 * Output     ：void
 * Return     ：void
 ***********************************************************************/
void init()
{
	//城市的 x 和 y 坐标
	int x[N] = { 0 };
	int y[N] = { 0 };
	//从 data.txt 文件读取数据
	FILE* fp;
	if ((fp = fopen("data.txt", "r")) == NULL)
		//if ((fp = fopen("..//kroB100.txt", "r")) == NULL)
	{
		printf("can not open the file!");
		exit(0);
	}
	while (!feof(fp))
	{
		int count;
		fscanf(fp, "%d", &count);
		fscanf(fp, "%d%d", &x[count - 1], &y[count - 1]);
	}
	fclose(fp);
	//计算城市之间距离
	for (int i = 0; i < N - 1; i++)
	{
		distance[i][i] = 0;				// 对角线为0
		for (int j = i + 1; j < N; j++)
		{
			double dis = sqrt((pow((double)x[i] - x[j], 2) / 10 + pow((double)y[i] - y[j], 2) / 10));
			int disInt = (int)dis;
			distance[i][j] = dis == disInt ? disInt : disInt + 1;
			distance[j][i] = distance[i][j];
		}
	}
	distance[N - 1][N - 1] = 0;
}

/***********************************************************************
 * Function   ：TSPGreedyAlgorithm()
 * Description：贪心策略求解 TSP 问题
 * Input      ：void
 * Output     ：TSP 路径和对应的总距离
 * Return     ：void
 ***********************************************************************/
void TSPGreedyAlgorithm()
{
	//总路程
	int totalDistance = 0;
	//默认从 0 开始遍历
	int current = 0;
	//标识城市是否被访问,访问过置为 1
	bool visit[N] = { false };
	visit[0] = 1;
	printf("TSP 路径为：%d ->", 1);

	//遍历 N - 1 次
	for (int i = 1; i < N; i++)
	{
		//设置较大的距离初始值用来选取最近邻
		int min_distance = 0x7fffffff;
		//保存当前最近邻城市
		int temp;
		//循环选取城市
		for (int j = 1; j < N; j++)
		{
			if (!visit[j] && distance[current][j] < min_distance)
			{
				min_distance = distance[current][j];
				temp = j;
			}
		}
		visit[temp] = 1;
		current = temp;
		totalDistance += min_distance;
		printf(" %d ->", temp + 1);
	}
	totalDistance += distance[current][0];
	printf(" %d\n", 1);
	printf("TSP 总距离为：%d\n", totalDistance);
}

int main()
{
	init();
	TSPGreedyAlgorithm();
	return 0;
}

基于贪心算法的TSP问题（c语言）