用c语言写贪心法求tsp问题的代码
时间: 2024-01-08 20:03:20 浏览: 40
以下是使用C语言编写的贪心算法求解TSP问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 100 // 最大城市数
#define INF INT_MAX // 定义无穷大
int n; // 城市数
int start; // 起点
int distance[MAX_N][MAX_N]; // 距离矩阵
int visited[MAX_N]; // 记录每个城市是否被访问过
int path[MAX_N]; // 记录访问路径
// 计算两个城市之间的距离
int calc_distance(int city1, int city2) {
return distance[city1][city2];
}
// 选择距离当前城市最近的未访问城市
int select_next_city(int current_city) {
int min_distance = INF;
int next_city = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && distance[current_city][j] < min_distance) {
min_distance = distance[current_city][j];
next_city = j;
}
}
return next_city;
}
// 使用贪心算法求解TSP问题
void tsp_greedy() {
// 初始化
for (int i = 0; i < n; i++) {
visited[i] = 0;
path[i] = -1;
}
path[0] = start;
visited[start] = 1;
// 选择下一个城市
for (int i = 1; i < n; i++) {
int current_city = path[i-1];
int next_city = select_next_city(current_city);
visited[next_city] = 1;
path[i] = next_city;
}
// 将最后一个城市与起点相连形成回路
path[n-1] = start;
}
int main() {
// 读入城市数和距离矩阵
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &distance[i][j]);
}
}
// 随机选择一个起点
start = rand() % n;
// 使用贪心算法求解TSP问题
tsp_greedy();
// 输出访问路径和回路的总长度
int total_distance = 0;
printf("Path: ");
for (int i = 0; i < n; i++) {
printf("%d ", path[i]);
if (i > 0) {
total_distance += calc_distance(path[i-1], path[i]);
}
}
printf("\nTotal distance: %d\n", total_distance);
return 0;
}
```
其中,`distance`是一个二维数组,表示各个城市之间的距离;`visited`和`path`分别是记录每个城市是否被访问过和记录访问路径的数组。程序读入城市数和距离矩阵,随机选择一个起点,使用贪心算法求解TSP问题,并输出访问路径和回路的总长度。