贪心算法实现旅行商问题c语言

以下是一个简单的TSP贪心算法C语言实现：

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

#define N 10

typedef struct {
    double x;
    double y;
} city;

double distance(city a, city b) {
    return sqrt(pow(a.x-b.x,2) + pow(a.y-b.y,2));
}

int main() {
    // 生成城市坐标
    city coord[N];
    for (int i=0; i<N; i++) {
        coord[i].x = (double)rand() / RAND_MAX * 10;
        coord[i].y = (double)rand() / RAND_MAX * 10;
    }

    // 计算任意两个城市之间的距离
    double dist[N][N];
    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            dist[i][j] = distance(coord[i], coord[j]);
            dist[j][i] = dist[i][j];
        }
    }

    // 初始化访问城市的顺序
    int route[N];
    int visited[N];
    visited[0] = 1;
    route[0] = 0;

    // 选择最近的未访问城市作为下一个访问城市
    for (int i=1; i<N; i++) {
        int last = route[i-1];
        int next = -1;
        double minDist = INFINITY;
        for (int j=0; j<N; j++) {
            if (j == last) {
                continue;
            }
            if (visited[j] == 1) {
                continue;
            }
            if (dist[last][j] < minDist) {
                minDist = dist[last][j];
                next = j;
            }
        }
        route[i] = next;
        visited[next] = 1;
    }

    // 计算总的行走距离
    double totalDist = 0;
    for (int i=0; i<N-1; i++) {
        totalDist += dist[route[i]][route[i+1]];
    }
    totalDist += dist[route[N-1]][route[0]];

    // 输出结果
    printf("访问城市的顺序:\n");
    for (int i=0; i<N; i++) {
        printf("%d ", route[i]);
    }
    printf("\n");
    printf("总行走距离: %lf\n", totalDist);

    return 0;
}

该算法的基本思路与Matlab实现类似，从起点出发，每次选择最近的未访问城市作为下一个访问城市，直到所有城市都被访问过为止。同样地，这个算法也只考虑了当前最优解，而没有考虑全局最优解，因此不能保证得到最优解。