Нахождение минимальной общей длины отрезков для соединения 2N точек - PullRequest
Новая
       42

Нахождение минимальной общей длины отрезков для соединения 2N точек

5 голосов
/ 10 января 2020

Я пытаюсь решить эту проблему с помощью брутфорса, но, похоже, он работает очень медленно, когда ему дают 7 (что составляет 2 * 7 баллов).

Примечание: мне нужно только набрать максимум 2 * 8 баллов

Постановка задачи:

Учитывая 2 * N баллов в плоскость 2d, соедините их попарно, чтобы сформировать 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;
}

Как я могу ускорить этот код?

Ответы [ 2 ]

3 голосов
/ 11 января 2020

Я не думаю, что это то, что вы ищете, но я все равно упоминаю это для полноты картины. Проблема может быть сформулирована как Смешанное целочисленное программирование (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

Тогда мы можем написать:

enter image description here

Решение этой проблемы может быть выполнено с помощью широко доступных MIP-решателей, что приводит к проверенным оптимальным решениям. Небольшой пример с 50 баллами:

enter image description here

2 голосов
/ 10 января 2020

Вы можете решить это итеративно, используя next_permutation () до go через все перестановки одну за другой. Извиняюсь за грязный код, но это должно показать вам, как это сделать: 

struct Point {

    Point(int x, int y) : x(x), y(y) {
    }


    bool operator< (const Point& rhs) {
        const int key1 = y * 1000 + x;
        const int key2 = rhs.y * 1000 + rhs.x;
        return  key1 < key2;
    }

    double dist(const Point& next) {

        const double h = (double)(next.x - x);
        const double v = (double)(next.y - y);
        return sqrt(h*h + v*v);
    }

    int x, y;

};

Вам нужен оператор, чтобы у вас был какой-то ключ сортировки для ваших точек, поэтому next_permutation может go проходить через них в лексикографический возрастающий порядок. double getShortestDist (std :: vector p) {

    double min = 200000;

    std::sort(p.begin(), p.end());

    while(std::next_permutation(p.begin(), p.end())) {

        double sum = 0.0;
        for (int i = 0; i < p.size(); i+= 2) {
            sum += p[i].dist(p[i+1]);
        }
        if (sum < min) {
            min = sum;
        }
    }

    return min;


}


int main(int argc, char*argv[]) {

    static const int arr[] = {
        10, 10, 20, 10, 5, 5, 1, 1, 120, 3, 6, 6, 50, 60, 3, 24, 6, 9, 0, 0
    };
    std::vector<Point> test;

    for (int i = 0; i < 20; i += 2) {
        test.push_back(Point(arr[i], arr[i+1]));
        printf("%d %d\n", arr[i], arr[i+1]);
    }

    printf("Output: %d, %f", test.size(), getShortestDist(test));
}
...