用C语言动态规划实现TSP

TSP（Traveling Salesman Problem）是一个经典的旅行商问题，它要求在给定的一些城市之间找到一条最短的路径，该路径从一个城市开始，经过所有其他城市恰好一次，最后回到起始城市。下面是用C语言实现TSP问题的动态规划算法：

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

#define N 4 // 城市数量

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

int dp[1<<N][N]; // 动态规划数组

int tsp(int S, int v) { // S表示已经访问的城市集合，v表示当前所在的城市
    if (S == (1<<N)-1 && v == 0) // 已经访问完所有城市，回到起点
        return 0;
    if (dp[S][v] != -1) // 已经计算过，直接返回
        return dp[S][v];
    int res = INT_MAX;
    for (int u = 0; u < N; u++) { // 枚举下一个要访问的城市
        if (!(S>>u & 1)) { // 该城市还未访问过
            res = tsp(S|1<<u, u) + dist[v][u]; // 计算从当前城市到下一个城市的距离
            dp[S][v] = res; // 记录计算结果
        }
    }
    return res;
}

int main() {
    for (int i = 0; i < 1<<N; i++) {
        for (int j = 0; j < N; j++) {
            dp[i][j] = -1; // 初始化为-1
        }
    }
    printf("最短路径长度为%d\n", tsp(1, 0)); // 从0号城市开始访问
    return 0;
}

在这个算法中，我们使用了一个大小为2^N * N的二维数组dp来记录已经访问过的城市集合S和当前所在城市v的最短路径长度。在计算dp[S][v]时，我们枚举下一个要访问的城市u，计算从当前城市v到下一个城市u的距离，并将该距离与从u出发访问剩下城市的最短路径长度相加，得到从S中剩余未访问城市到达u的最短路径长度，然后取所有可能的路径中的最小值作为dp[S][v]的值。最终，我们返回从起点0出发访问所有城市的最短路径长度。