C语言动态规划法解决TSP问题

TSP问题是指旅行商问题，即给定一组城市和每对城市之间的距离，求解访问每一座城市一次并返回起始城市的最短路径。

动态规划法可以用来解决TSP问题，其主要思路是将问题分解为子问题，并将子问题的解合并起来得到原问题的解。具体来说，可以采用以下步骤：

1. 状态定义：定义状态f[S][i]表示从起点出发，经过集合S中的所有点，最终到达点i的最短路径长度。

2. 状态转移：对于集合S中的每个点j，都可以从集合S-j中的某个点k转移而来，即f[S][i] = min{f[S-j][k] + dis[k][i]}，其中dis[k][i]表示点k到点i的距离。

3. 边界条件：当集合S中只有一个点时，f[S][i] = dis[0][i]，其中0表示起点。

4. 最终结果：最终结果为f[2^n-1][0]，其中n为城市的数量。

下面是一个使用动态规划法解决TSP问题的C语言代码示例：

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

#define MAXN 15
#define INF 0x3f3f3f3f

int n, m;
int dis[MAXN][MAXN];
int f[1 << MAXN][MAXN];

int tsp() {
    memset(f, INF, sizeof(f));
    f[1][0] = 0;
    for (int S = 1; S < (1 << n); ++S) {
        if ((S & 1) == 0) continue;
        for (int i = 0; i < n; ++i) {
            if ((S >> i) & 1) {
                for (int j = 0; j < n; ++j) {
                    if ((S ^ (1 << i)) == (1 << j)) {
                        f[S][i] = dis[0][i];
                    } else if ((S >> j) & 1) {
                        f[S][i] = f[S][i] < f[S ^ (1 << i)][j] + dis[j][i] ? f[S][i] : f[S ^ (1 << i)][j] + dis[j][i];
                    }
                }
            }
        }
    }
    return f[(1 << n) - 1][0];
}

int main() {
    scanf("%d %d", &n, &m);
    memset(dis, INF, sizeof(dis));
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        dis[a][b] = dis[b][a] = c;
    }
    int ans = tsp();
    printf("%d\n", ans);
    return 0;
}

其中，dis数组存储了每对城市之间的距离，f数组用于记录状态，tsp函数返回最短路径长度。在主函数中，先读入城市数量和距离信息，然后调用tsp函数计算最短路径长度，并输出结果。