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

TSP问题（Traveling Salesman Problem）是一个著名的NP难问题，其[目标](https://geek.csdn.net/educolumn/06c7a9ffb1969a0ad080048a16f82c4e?spm=1055.2569.3001.10083)是在所有城市之间找到一条最短的路径，使得每个城市只被经过一次。贪心算法是一种简单而有效的方法，可以用来近似[解决](https://geek.csdn.net/educolumn/03368addd5d267af1b4c6df01bb4af26?spm=1055.2569.3001.10083)TSP问题。 以下是一个以C[语言](https://geek.csdn.net/educolumn/05c8de7581a582e6d46821757663ed30?spm=1055.2569.3001.10083)实现贪心算法[解决](https://geek.csdn.net/educolumn/03368addd5d267af1b4c6df01bb4af26?spm=1055.2569.3001.10083)TSP问题的示例[代码](https://geek.csdn.net/educolumn/1572ef9b473b4e00f6b2bf6d428b7c27?spm=1055.2569.3001.10083)： #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; ```