主页 / 问题 / 622980
Accepted
Дмитрий Белоусов
Asked:2020-02-03 21:02:40 +0000 UTC2020-02-03 21:02:40 +0000 UTC

应该用什么算法来解决这个问题？[关闭]

  • 772

任务

我不知道要输出什么

олимпиада

3 个回答

  1. 这是旅行推销员问题，通过枚举（带截止值）解决。

    考虑到点在一个平面上，可以优化其他东西，但是对于n<=12我觉得没有意义。

    • 3
  2. Best Answer

    我喜欢@Qwertiy 的排列组合想法。我写的代码很流畅（代码很脏，用左脚写的，但一切都算对了）。

    #include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>

using namespace std;

struct point {
    double x;
    double y;
};

double dist(point x, point y) {
    return hypot(x.x-y.x, x.y-y.y);
}

double calc_len(const vector<point> &v, const vector<int> &d) {
    double l = 0;
    for (int i = 1; i < d.size(); i++) {
        l += dist(v[d[i-1]], v[d[i]]);
    }
    return l;
}

int main() {
    vector<point> v;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        point p;
        cin >> p.x >> p.y;
        v.push_back(p);
    }
    vector<int> d;
    vector<int> min_r;
    double min_len = std::numeric_limits<double>::max();
    for (int i = 0; i< n; i++) { d.push_back(i); }
    do {
        double len = calc_len(v, d);
        cout << len << endl;
        if (len < min_len) {
            min_len = len;
            min_r = d;
        }
    } while ( std::next_permutation(begin(d)+1,end(d)-1) );
    cout << "len = " << min_len << endl;
    cout << "[";
    for (int x:min_r) { cout << " " << x+1; }
    cout << "]" << endl;
    return 0;
}

    c++11中的距离计算已经可以这样写了

    double dist(point x, point y) {
    return hypot(x.x-y.x, x.y-y.y);
}

    不是这样的

    double dist(point x, point y) {
    return sqrt((x.x-y.x) * (x.x-y.x) + (x.y-y.y) * (x.y-y.y));
}

    PS 您需要在支持 c++11 的情况下进行编译。

    • 3

  3. 我看着@KoVadim 并在我的膝盖上画了草图 - 用剪裁分支......

    #include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

struct pnt { double x, y; };

double dist(pnt a, pnt b)    // Расстояние между точками
{
    return hypot(a.x-b.x,a.y-b.y);
}

double path_len(const vector<pnt>& x, // Длина (части) выбранного пути
                const vector<int>& p, size_t l)
{
    double pl = 0.0;
    for(size_t i = 1; i <= l; ++i)
        pl += dist(x[p[i-1]],x[p[i]]);
    // Расстояние до последней точки, если еще не достали
    if (l != p.size()-1) pl += dist(x[p[l]],x[x.size()-1]);
    return pl;
}

struct Func
{
    double min;               // Текущее минимальное расстояние
    const vector<pnt> * r;    // Массив точек
    vector<int>         save; // Сохраненная перестановка

    Func(const vector<pnt>& x):r(&x)
    {
        min = 0.0;
        for(size_t i = 1; i < x.size(); ++i)
            min += dist(x[i-1],x[i]);
    }

    // Проверка ветви
    bool operator()(const vector<int>& x, size_t l)
    {
        // Режем все, где неверное начало или конец
        if (x[0] != 0) return false;
        if (l != x.size()-1 && x[l] == x.size() - 1) return false;
        // Текущая длина
        double cur = path_len(*r,x,l);
        // Если больше минимальной - режем ветвь
        if (cur > min + min*DBL_EPSILON) return false;
        // Сохранение нового пути
        if (l == x.size()-1)
        {
            if (abs(min-cur) < 10.0*min*DBL_EPSILON)
            {
                if (save > x) save = x;
            }
            else
            {
                min = cur;
                save = x;
            }
        }
        return true;
    }
};

// Ветвление и обрезка
template<typename Func>
bool branches(size_t N, Func& f, vector<int>*v_ = nullptr, size_t level = 0)
{
    // Вспомогательный вектор
    vector<int> * vv = (level == 0) ? new vector<int> : v_;
    if (level == 0) for(size_t i = 0; i < N; ++i) vv->push_back(i);
    vector<int>& v = *vv;

    for(size_t i = level; i < N; ++i)
    {
        // Очередная перестановка
        std::swap(v[level],v[i]);
        if (f(v,level) && level < N-1) branches(N,f,vv,level+1);
        std::swap(v[i],v[level]);

    }
    if (level == 0) delete vv;
    return true;
}


int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    vector<pnt> x;
    for(int i = 0; i < N; ++i)
    {
        cout <<"Point " << (i+1) << ": ";
        double xx, yy;
        cin >> xx >> yy;
        x.push_back(pnt{xx,yy});
    }
    Func f(x);
    branches(N,f);
    cout << f.min << endl;
    for(auto i: f.save) cout << (i+1) << "  ";
    cout << endl;

}

    在 13 点的输入数据上，它在半秒内工作，@KoVadim 的迭代 - 37 秒；获得 12 分 - 分别为 0.17 秒和 3.1 秒......

    更新
    实验数据 -

    13
0 0 1 0 2 0 3 0 0 1 1 1 2 1 3 1 0 2 1 2 2 2 3 2 0 3 1 3 2 3 3 3

    （我刚工作了16个点，嗯，为了不重写数据文件，我只改了第一个数）

    编译 - VC++ 2015，键cl /O2 /Ot /EHsc /FC /W4 /nologo /MT。我讨厌忍受 IDE :) 在没有特殊需要的情况下使用......
    我的变体hypot- 700±15ms。通过平方根的计算——他妈的，请原谅我的法语：大约 85±15 毫秒。他们在里面放了什么？可能是某种绕过可能溢出的可怕系统......

    来自@KoVadim 的程序在相同的编译条件下使用相同的数据 - 好吧，懒得运行十几次了，抱歉 - 给了 38 秒。答案不同，但最小距离相同。校正后hypot- 2.7 秒。

    人，不要用hypot！:) 顺便说一句，如果你只是预先计算距离表并从中取数据，你可以再次提高5的速度。

    以下是以 ms 为单位的近似（一次或两次运行）结果：

    Точек         KoVadim        Harry    Harry (hypot)  Harry (предвычисление
                                                      таблицы расстояний)
  12             230          30          180           12
  13            2700          75          700           24
  14           34700         380         3880           97
  15          484000        1950        23000          414
  16                        9400                      1880

    更新2

    同样用于比较 - 详尽搜索hypot13 个点计算 479001600 次，我的 - 8302951 ...

    更新3

    请参阅此处的最后一个选项 -如何正确并行化程序？

    • 3

相关问题