贪心算法解决TSP问题以C语言的方式实现

TSP问题（Traveling Salesman Problem）是一个著名的NP难问题，其目标是在所有城市之间找到一条最短的路径，使得每个城市只被经过一次。贪心算法是一种简单而有效的方法，可以用来近似解决TSP问题。

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

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

#define N 4 // 城市数量

int graph[N][N] = { // 代表城市之间的距离矩阵
    {0, 10, 15, 20},
    {10, 0, 35, 25},
    {15, 35, 0, 30},
    {20, 25, 30, 0}
};

int visited[N] = {0}; // 标记城市是否被访问过

void tsp(int start) {
    int current = start;
    visited[start] = 1;
    printf("%d->", start);

    for (int i = 0; i < N - 1; i++) {
        int min_distance = INT_MAX;
        int next_city = -1;
        for (int j = 0; j < N; j++) {
            if (!visited[j] && graph[current][j] < min_distance) {
                min_distance = graph[current][j];
                next_city = j;
            }
        }
        visited[next_city] = 1;
        printf("%d->", next_city);
        current = next_city;
    }

    printf("%d\n", start);
}

int main() {
    tsp(0); // 从城市0开始遍历
    return 0;
}

在这个示例代码中，我们使用一个二维数组`graph`来代表城市之间的距离矩阵。`visited`数组用来标记城市是否被访问过。`tsp`函数接受一个起始城市的编号作为参数，然后按照贪心策略依次遍历所有的城市，最后回到起点。

在遍历过程中，我们每次从当前城市开始，找到与其距离最近且未被访问过的城市，把它标记为已访问，并输出它的编号。这个过程重复N-1次，直到遍历所有的城市。

运行上面的代码，输出结果如下：

0->1->3->2->0

这个结果表示我们从城市0开始，依次遍历了城市1、城市3、城市2，最后回到了城市0。虽然这个结果不一定是最优解，但是它可以作为一个较好的近似解。