旅行商问题的编译器优化

Question

我正在解决旅行商问题，正在查看以下版本：城镇是 2d space 中的点，从每个城镇到所有其他城镇都有路径，长度是点之间的距离。因此，在检查 n 点的所有排列并计算路径长度的情况下，实现简单的解决方案非常容易。

但是我发现对于 n >= 10 编译器做了一些魔术并打印了一个肯定不是实际最短路径的值。我用Microsoft visual studio compiler in release mode with the default settings编译。对于值 (10,30)，它考虑了 30 秒，然后 returns 一些数字似乎是正确的，但事实并非如此（我以不同的方式检查）。而对于 n > 40 它会立即计算出一个结果并且总是 2.14748e+09.

我正在寻找编译器在不同情况下做什么的解释（(10,30) 情况真的很有趣）。还有一个例子，其中这些优化比只是旋转到世界尽头的程序更有用。

vector<pair<int,int>> points;
void min_len()
{
    // n is a global variable with the number of points(towns)
    double min = INT_MAX;
    // there are n! permutations of n elements
    for (auto j = 0; j < factorial(n); ++j)
    {
        double sum = 0;
        for (auto i = 0; i < n - 1; ++i)
        {
            sum += distance_points(points[i], points[i + 1]);
        }
        if (sum < min)
        {
            min = sum;
            s_path = points;
        }
        next_permutation(points.begin(), points.end());
    }

    for (auto i = 0; i < n; ++i)
    {
        cout << s_path[i].first << " " << s_path[i].second << endl;
    }
    cout << min << endl;
}

unsigned int factorial(unsigned int n)
{
    int res = 1, i;
    for (i = 2; i <= n; i++)
        res *= i;
    return res;
}

Answer 1

您的阶乘函数溢出。尝试将其替换为一个返回 int64_t 并查看您的代码需要 3 年才能终止 n > 20.

constexpr uint64_t factorial(unsigned int n) {
  return n ? n * factorial(n-1) : 1;
}

另外，你根本不需要计算这个。 std::next_permutation 函数 returns 0 当所有排列都发生时（从排序位置开始）。

旅行商问题的编译器优化

Compiler optimization on the traveling salesman problem

c++

compiler-optimization