?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 數(shù)據(jù)集，其中有 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，可見貪心策略只是局部最優(yōu)解
**********************************************************************************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

// 城市數(shù)量 N
#define N 48
// 城市距離矩陣
int distance[N][N];

/***********************************************************************
 * Function   ：init()
 * Description：從文件中讀取城市坐標(biāo)，并計算城市之間的距離 distance[N][N]
 * Input      ：void
 * Output     ：void
 * Return     ：void
 ***********************************************************************/
void init()
{
	//城市的 x 和 y 坐標(biāo)
	int x[N] = { 0 };
	int y[N] = { 0 };
	//從 data.txt 文件讀取數(shù)據(jù)
	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 路徑和對應(yīng)的總距離
 * Return     ：void
 ***********************************************************************/
void TSPGreedyAlgorithm()
{
	//總路程
	int totalDistance = 0;
	//默認從 0 開始遍歷
	int current = 0;
	//標(biāo)識城市是否被訪問,訪問過置為 1
	bool visit[N] = { false };
	visit[0] = 1;
	printf("TSP 路徑為：%d ->", 1);

	//遍歷 N - 1 次
	for (int i = 1; i < N; i++)
	{
		//設(shè)置較大的距離初始值用來選取最近鄰
		int min_distance = 0x7fffffff;
		//保存當(dāng)前最近鄰城市
		int temp;
		//循環(huán)選取城市
		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;
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-507849.html

到了這里，關(guān)于基于貪心算法的TSP問題（c語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！