旅行售货员问题C语言回溯法实现

旅行售货员问题是指一个旅行售货员要拜访n个城市，他需要选择一条路径，使得经过每个城市恰好一次，并且路径的总长度最小。这是一个经典的组合优化问题，可以用回溯法实现。

以下是使用C语言实现旅行售货员问题的回溯法代码：

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

#define N 4 // 城市个数

int visited[N]; // 记录城市是否被访问
int path[N]; // 记录路径
int min_path[N]; // 记录最短路径
int graph[N][N] = { // 城市之间的距离
    {0, 10, 15, 20},
    {10, 0, 35, 25},
    {15, 35, 0, 30},
    {20, 25, 30, 0}
};
int min_dist = INT_MAX; // 最短路径长度

void tsp(int cur, int dist) {
    if (cur == N) { // 所有城市都已经访问过
        if (dist + graph[path[N-1]][path[0]] < min_dist) { // 更新最短路径
            min_dist = dist + graph[path[N-1]][path[0]];
            for (int i = 0; i < N; i++) {
                min_path[i] = path[i];
            }
        }
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!visited[i]) { // 如果城市i没有被访问过
            visited[i] = 1; // 标记城市i为已访问
            path[cur] = i; // 将城市i加入路径
            tsp(cur+1, dist+graph[path[cur-1]][i]); // 继续访问下一个城市
            visited[i] = 0; // 回溯到上一个城市
        }
    }
}

int main() {
    visited[0] = 1; // 从城市0开始访问
    path[0] = 0;
    tsp(1, 0); // 计算最短路径
    printf("最短路径长度为：%d\n", min_dist);
    printf("最短路径为：");
    for (int i = 0; i < N; i++) {
        printf("%d ", min_path[i]);
    }
    printf("\n");
    return 0;
}

在上述代码中，我们使用了一个全局变量`visited`来记录每个城市是否被访问过，使用`path`数组来记录当前的路径，使用`min_path`数组来记录最短路径，使用`graph`数组来表示城市之间的距离。我们使用递归函数`tsp`来实现回溯法，其中`cur`表示当前访问到的城市编号，`dist`表示当前路径长度。在`tsp`函数中，我们首先判断是否所有城市都已经访问过，如果是，则更新最短路径；否则，我们遍历所有没有被访问过的城市，将其加入路径，并继续访问下一个城市。在访问完当前城市之后，我们回溯到上一个城市，将当前城市标记为未访问过，继续遍历其他城市。

最后，我们在`main`函数中调用`tsp`函数，计算出最短路径，并输出结果。