c实现旅行售货员问题回溯法代码

旅行售货员问题是一个经典的组合优化问题，它的目标是在给定一组城市以及每对城市之间的距离，找到一条最短的路径，使得每个城市恰好被访问一次，并且最终回到起点城市。

回溯法是解决该问题的一种常见方法，其基本思想是从起点出发，逐步选择下一个城市，并计算当前路径的长度，直到遍历完所有城市后回到起点。在选择下一个城市时，需要满足两个条件：未被访问过且到当前城市的距离最短。

以下是一个简单的C语言实现旅行售货员问题的回溯法代码，其中假设城市编号从0开始，距离由二维数组dist[][]表示：

#include <stdio.h>
#define N 5   // 城市数量

int dist[N][N] = { // 城市间距离
    {0, 10, 20, 30, 40},
    {10, 0, 25, 35, 15},
    {20, 25, 0, 45, 30},
    {30, 35, 45, 0, 50},
    {40, 15, 30, 50, 0}
};

int path[N];      // 存储当前路径
int visited[N];   // 标记城市是否已访问
int min_dist = 0x7fffffff; // 最短路径长度

void tsp(int cur_city, int cur_dist, int cnt) { // cur_city：当前所在城市编号，cur_dist：当前路径长度，cnt：已访问城市数量
    if (cnt == N) { // 遍历完所有城市
        if (cur_dist + dist[cur_city] < min_dist) { // 如果形成一条更短的路径
            min_dist = cur_dist + dist[cur_city];   // 更新最短路径长度
            for (int i = 0; i < N; i++) {
                printf("%d -> ", path[i]);             // 输出路径
            }
            printf("%d\n", path);
        }
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i]) {                           // 如果该城市未被访问
            visited[i] = 1;                          // 标记为已访问
            path[cnt] = i;                           // 存储路径
            tsp(i, cur_dist + dist[cur_city][i], cnt + 1); // 继续遍历
            visited[i] = 0;                          // 回溯
        }
    }
}

int main() {
    path = 0;        // 起点为城市0
    visited = 1;     // 标记起点已访问
    tsp(0, 0, 1);       // 从起点开始遍历
    printf("最短路径长度为：%d\n", min_dist);
    return 0;
}