使用C语言DP求解TSP出现Segmentation fault (core dumped)的原因排查

问题 #

我用C语言实现动态规划解法求解旅行商问题，在ZeroJudge平台的13、14、15号测试用例中出现Segmentation fault (core dumped)错误，自查代码未发现问题。

实现代码 #

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define min(a, b)(a > b ? b : a)
void travel();
int **map,**dp,n;
main()
{
    scanf("%d", &n);
    map = (int **)calloc(n, sizeof(int *));
    dp = (int **)calloc(n, sizeof(int *));
    for(int i = 0 ; i < n ; i++)
    {
        map[i] = (int *)calloc(n, sizeof(int));
        dp[i] = (int *)calloc((1 << (n - 1)), sizeof(int));
    }
    int distance;
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            scanf("%d", &distance);
            map[i][j] = distance;
        }
        dp[i][0] = map[i][0];
    }
    travel();
    printf("%d\n", dp[0][(1 << (n - 1)) - 1]);
    free(map);
    free(dp);
}
void travel()
{
    for(int j = 1 ; j < 1 << (n - 1) ; j++) 
    {
        for(int i = 0 ; i < n ; i++)   
        {
            dp[i][j] = INT_MAX;
            if(j >> (i - 1) & 1)  
            {
                continue;
            }
            for(int k = 1 ; k < n ; k++)
            {
                if(!(j >> (k - 1) & 1))
                {
                    continue;
                }
                dp[i][j] = min(dp[i][j], map[i][k] + dp[k][j ^ (1 << (k - 1))]);
            }
        }
    }
}

题目背景 #

需求 #

给定一组城市及两两城市间的距离，找出从某城市出发，遍历所有城市不重复并返回起点的最短路径总距离。例如访问顺序为1-2-3-4-1时，总距离为10+25+30+15=80。

输入输出规则 #

• 输入：
  • 第一行是整数N（城市数量，3 < N ≤ 35）
  • 接下来N行每行有N个非负整数Di,j，表示从节点i到j的距离，Di,j=0表示无路径
  • 说明：边可能为单向，保证存在至少一条有效TSP路径
• 输出：输出最短路径的总距离

示例输入 #

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

示例输出 #

80

错误根源与修复方案 #

1. 内存超限导致分配失败 #

当N=35时，1 << (n-1)等于2^34，单个dp[i]需要分配2^34个int类型的空间（约64GB），普通程序根本无法申请到这么大的内存，calloc会返回NULL，后续访问dp[i][j]直接触发段错误。这是核心问题——原始DP状态的空间复杂度为O(N*2^N)，对于N=35完全不可行。

2. 索引越界的未定义行为 #

当i=0时，代码中执行j >> (i-1)即j >> (-1)，这是C语言中的未定义行为，会导致位运算结果混乱，进而触发非法内存访问。

3. 内存释放不彻底 #

代码仅释放了map和dp指针数组本身，没有逐个释放map[i]和dp[i]指向的内存块，会造成内存泄漏（虽不是段错误直接原因，但属于不良编码习惯）。

修复方案 #

（1）改用Meet-in-the-Middle分治优化

对于N=35，必须使用分治策略将状态数从O(2^N)降到O(2(N/2))：

• 将城市分为两组（比如前17个和后18个）
• 预处理第一组：记录从起点出发，遍历第一组中任意子集并停在组内某城市的最短路径
• 预处理第二组：记录从第二组某城市出发，遍历第二组剩余城市并返回起点的最短路径
• 枚举第一组的所有访问状态，匹配第二组需要访问的补集状态，合并路径长度取最小值

（2）修正索引错误

调整状态掩码的定义，确保位运算时不会出现负索引：比如掩码仅表示除起点外的城市访问状态，当处理起点（i=0）时，跳过掩码包含自身的判断逻辑。

（3）正确释放内存

在程序结束前，遍历所有map[i]和dp[i]逐个free，再free指针数组：

// 替代原free(map); free(dp);
for (int i = 0; i < n; i++) {
    free(map[i]);
    free(dp[i]);
}
free(map);
free(dp);

内容的提问来源于stack exchange，提问作者Eric