出现Segmentation failure（core dumped）的原因是什么？

Question

我使用C语言，并应用动态编程来解决旅行商问题。 ZeroJudge（初学者在线判断系统）上有这样的问题，但我在第13、14和15个测试用例时遇到了Segmentation failure（核心转储）。我检查了我的代码，但找不到问题。

#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))]);
            }
        }
    }
}

内容

Given a set of cities and the distances between each pair of cities, find the shortest distance sum of a tour that starts from a city, visits all the cities without repetition, and returns to the starting city.
For example, the visiting order is 1-2-3-4-1. The distance sum is 10 + 25 + 30 + 15 = 80.

输入说明

There is only one set of test data. The first line of each set has an integer N, indicating that there are N cities. Then there will be N lines, each line has N non-negative integers Di,j indicating the distance from node i to node j. If Di,j = 0, it is considered that there is no edge.
You can assume that each edge may be unidirectional, and guarantee that there is at least one TSP path.
* 3 < N ≤ 35
* 0 distance between any pair of cities ≤ 10000

输出说明

Output a line of minimum distance sum.

输入示例#1

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

示例输出#1

80

Answer 1

问题陈述在几个地方提到“3 < N ≤ 35”. The program uses

1 << (n - 1)

”，其中

n

包含 N 的值。这会将

int

值 1 移动多达 34 位。然而，在当前的 C 实现中，

int

通常为 32 位，因此移位超过 30 位会溢出，并且 C 标准未定义该行为。

此外，程序尝试在

1 << (n - 1)

中为

int

calloc((1 << (n - 1)), sizeof(int))

元素数组分配空间。这可能会因为请求太大而失败，特别是因为它重复了 N 次。或者

1 << (n - 1)

中的溢出可能会导致请求的内存不足。

您需要一种不会尝试使用太多内存的新算法。