c语言tsp问题贪心法代码

TSP问题是旅行商问题的英文缩写，是指在给定多个城市之间的距离及旅行的数量限制条件下，找出一条最短路径使得旅行商能够恰好经过每个城市一次并返回起始城市。

TSP问题的贪心法解决方案是一种启发式算法，它试图寻找局部最优解，并以此作为全局最优解的近似。

以下是一个用C语言实现TSP问题贪心法的代码示例：

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

#define N 4  // 城市的数量
#define INF 1000000  // 表示无穷大的距离

int tsp_greedy(int graph[N][N], int path[N]) {
    int visited[N];  // 标记城市是否已访问
    int current = 0;  // 当前城市编号
    int next;  // 下一个城市编号
    int min_dist;  // 最小距离
    int total_dist = 0;  // 总距离

    for (int i = 0; i < N; i++) {
        visited[i] = 0;  // 初始化所有城市为未访问状态
    }
    visited[0] = 1;  // 设置起始城市为已访问

    for (int i = 0; i < N - 1; i++) {
        min_dist = INF;
        next = -1;
        
        // 寻找下一个最近的未访问城市
        for (int j = 0; j < N; j++) {
            if (!visited[j] && graph[current][j] < min_dist) {
                next = j;
                min_dist = graph[current][j];
            }
        }

        if (next == -1) {  // 未找到下一个城市，表示无解
            return -1;
        }
        
        visited[next] = 1;  // 标记下一个城市为已访问
        path[i] = next;  // 记录路径
        total_dist += min_dist;  // 更新总距离
        current = next;  // 更新当前城市编号
    }

    path[N - 1] = 0;  // 最后一个城市为起始城市
    total_dist += graph[current][0];  // 更新总距离

    return total_dist;
}

int main() {
    int graph[N][N] = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    int path[N];
    int total_dist;

    total_dist = tsp_greedy(graph, path);

    if (total_dist == -1) {
        printf("无解\n");
    } else {
        printf("最短路径为：0 -> ");
        for (int i = 0; i < N - 1; i++) {
            printf("%d -> ", path[i]);
        }
        printf("0\n");
        printf("总距离为：%d\n", total_dist);
    }

    return 0;
}

该代码通过贪心算法的思路，每次选择离当前城市最近的未访问城市，来构建近似的最优路径。它首先初始化所有城市为未访问状态，然后从起始城市出发，依次选择下一个距离最短的未访问城市，直到所有城市都被访问完毕，并返回起始城市作为最后一个城市。最终输出路径和总距离。由于TSP问题是NP困难问题，贪心法并不能保证一定可以得到全局最优解，但它是一种简单并且常用的近似算法。