贪心算法解决tsp问题的代码

以下是利用C语言编写的求解TSP问题的贪心算法程序：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 1000

int n; // 城市数量
double x[MAX_N], y[MAX_N]; // 城市坐标
int used[MAX_N]; // 已经使用过的城市
double dist[MAX_N][MAX_N]; // 城市间距离

// 计算两个城市之间的距离
double calc_dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return sqrt(dx * dx + dy * dy);
}

// 计算从当前城市出发，到剩余城市的最短距离
double dfs(int v, int depth, double len) {
    if (depth == n) {
        return len;
    }
    double min_len = 1e9;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            double next_len = dfs(i, depth + 1, len + dist[v][i]);
            min_len = fmin(min_len, next_len);            used[i] = 0;
        }
    }
    return min_len;
}

int main() {
    // 读入城市数量和坐标
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &x[i], &y[i]);
    }
    // 计算城市间距离
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = calc_dist(i, j);
        }
    }
    // 从每个城市出发，计算最短距离
    double ans = 1e9;
    for (int i = 0; i < n; i++) {
        used[i] = 1;
        double len = dfs(i, 1, 0);
        ans = fmin(ans, len);
        used[i] = 0;
    }
    // 输出最短距离
    printf("%.2f\n", ans);
    return 0;
}