c++ - 找到连接 2N 个点的线段的最小总长度

Question

我正在尝试通过蛮力解决这个问题，但是当给定 7（即 2*7 点）时，它似乎运行得很慢。

注意：我只需要将它运行到最大 2*8 点

问题陈述：

给定二维平面中的 2*N 个点，将它们成对连接以形成 N 条线段。最小化所有线段的总长度。

例子：

输入： 5 10 10 20 10 5 5 1 1 120 3 6 6 50 60 3 24 6 9 0 0

输出：118.4

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

class point{
public:
    double x, y;
};

double getLength(point a, point b){
    return hypot((a.x - b.x), (a.y - b.y));
}

static double mini = INT_MAX;

void solve(vector <point> vec, double sum){
    double prevSum = sum;
    if(sum > mini){
        return;
    }
    if(vec.size() == 2){
        sum += getLength(vec[0], vec[1]);
        mini = min(mini, sum);
        return;
    }
    for(int i = 0; i < vec.size() - 1; i++){
        for(int j = i + 1; j < vec.size(); j++){
            sum = prevSum;
            vector <point> temp = vec;
            sum += getLength(temp[i], temp[j]);
            temp.erase(temp.begin() + j);
            temp.erase(temp.begin() + i);
            solve(temp, sum);
        }
    }
}

int main(){
    point temp;
    int input;
    double sum = 0;
    cin >> input;
    vector<point> vec;
    for(int i = 0; i < 2 * input; i++){
        cin >> temp.x >> temp.y;
        vec.push_back(temp);
    }
    solve(vec, sum);
    cout << fixed << setprecision(2) << mini << endl;
}

我怎样才能加快这段代码？

标签： c++algorithmperformanceoptimizationbrute-force

Answer 1

我不认为这就是你要找的东西，但无论如何我还是为了完整性而提到它。该问题可以表述为混合整数规划(MIP) 问题。

我们有距离：

d(i,j) = distance between point i and j (only needed for i<j)

和决策变量

x(i,j) = 1 if points i and j are connected (only needed for i<j)
         0 otherwise

然后我们可以写：

可以使用广泛可用的 MIP 求解器来解决此问题，并得出经过验证的最佳解决方案。一个50分的小例子：