The task

and I can not understand what exactly you need to withdraw

Closed due to the fact that off-topic participants Anton Shchyrov , Harry , user194374, Denis Bubnov , ermak0ff 4 Feb '17 at 9:35 .

It seems that this question does not correspond to the subject of the site. Those who voted to close it indicated the following reason:

  • “Questions asking for help with debugging (“ why does this code not work? ”) Should include the desired behavior, a specific problem or error, and a minimum code for playing it right in the question . Questions without an explicit description of the problem are useless for other visitors. See How to create minimal, self-sufficient and reproducible example . " - Anton Shchyrov, Harry, Community Spirit, Denis Bubnov, ermak0ff
If the question can be reformulated according to the rules set out in the certificate , edit it .

  • 7
    Well, you ask to solve the problem for you. But you were too lazy to even rewrite it, and instead rush to the screenshots - Anton Shchyrov
  • one
    classical problem for graphs. - KoVadim
  • one
    @AntonShchyrov like the question says "Which algorithm to use" and do not decide to me ....... But instead of a screenshot, it’s better to describe the problem with the text, that’s for sure - Alexey Shimansky
  • one
    With so many points, even the search will be fast :) - Harry
  • one
    @KoVadim On graphs - Hamilton's cycle search - is it kind of like NP? ... - Harry

3 answers 3

I liked the @Qwertiy idea with permutation. I wrote the code fluently (the code is very dirty, it was written with the left foot, but it was all right).

#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(xx-yx, xy-yy); } 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 >> px >> py; 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; }

you can write the calculation of the distance in c ++ 11 already

 double dist(point x, point y) { return hypot(xx-yx, xy-yy); }

not so

 double dist(point x, point y) { return sqrt((xx-yx) * (xx-yx) + (xy-yy) * (xy-yy)); }

PS it is necessary to compile with support with ++ 11.

  • Something seems to me that the hypot was recommended not to use, since it is slow ... - Qwertiy ♦
  • next_permutation on the vector in debug is slow. Sometimes it is better to use an array ... - Pavel Mayorov
  • @Qwertiy, why not? .. - Pavel Mayorov
  • @PavelMayorov, and why in the debug? However, I agree that the array. Well, they talked like that, just on Olympiad programming. Like cin / cout, by the way. - Qwertiy ♦
  • @Qwertiy then, that somehow you need to debug the program. And for small N, even a test can often not be normal ... - Pavel Mayorov

I looked at @KoVadim and also sketched on my knee - branching with clippings ...

 #include <vector> #include <iostream> #include <iomanip> using namespace std; struct pnt { double x, y; }; double dist(pnt a, pnt b) // Расстояние между точками { return hypot(ax-bx,ay-by); } 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; }

On input data with 13 points, it worked for half a second, brute force @KoVadim - 37 seconds; for 12 points - 0.17 and 3.1 seconds, respectively ...

Update
The data for the experiment -

 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

(I just worked up to 16 points, well, so as not to overwrite the data file - I only changed the first number)

Compilation - VC ++ 2015, keys cl /O2 /Ot /EHsc /FC /W4 /nologo /MT . IDE hate hate :) use without much need ...
My hypot version is 700 ± 15ms. With the calculation through the root of the squares - just fucking, forgive my French: about 85 ± 15ms. Well, they shoved there ?! Surely some kind of creepy system for avoiding possible overflows ...

The program from @KoVadim under the same compilation conditions with the same data - well, too lazy to run it a dozen times, sorry - gave 38 seconds. The answer is different, but the same minimum distance. After correcting hypot - 2.7 seconds.

People, do not use hypot !!! :) By the way, if you simply predict the table of distances and take data from it, you can raise the speed again at 5.

Here are the approximate (one or two runs) results in 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

Update2

Even for comparison - a complete hypot bust for 13 points calculates 479001600 times, mine - 8302951 ...

Update3

The last option is here. - How to parallelize the program?

  • Something seems to me that the hypot was recommended not to use, since it is slow ... Check what time will it be without it? - Qwertiy ♦
  • Did you launch KoVadim in debug or release? :) - Pavel Mayorov
  • @PavelMayorov My standard keys for all kinds of "knee" programs - cl /O2 /Ot /EHsc /FC /W4 /nologo /MT - Harry
  • one
    @Qwertiy See addition to answer. - Harry
  • one
    @Qwertiy Damn ... Will I ever learn to carefully read the conditions of the tasks? ... I suffer all my life. Okay, I still do a complete brute force, so the order of magnitude will be about the same - there are not too many identical routes, the lexicographic verification is quick ... - Harry

This is the task of a salesman , is solved by brute force (with cut-offs).

Taking into account the fact that there are points on a plane, something else can be optimized, but with n <= 12 I don’t think it makes sense.

  • Something I remember that on the plane can be somehow faster ... No? Oh, no, I lied. Provided there are triangle inequalities, there are fast approximate algorithms ... - Harry
  • @Harry, I have a suspicion that yes, but I do not remember. But here it is 12. Yes, and the lexicographically least way. I'm not even sure how well to use a mask with visited vertices - it can spoil lexicography. - Qwertiy ♦
  • @Harry, you can. In addition, the complexity of busting with clipping will be equal to a large number anyway. For example, if it is known that simple paths are to be found, and if n = 12, then the algorithm will take a very, very long time. I did this. - VostokSisters
  • 2
    @VostokSisters Two points - extreme, in the middle - 10. 10! - it's a bit :) - Harry
  • @Harry, damn it, here I am, I deduced the formula for calculating the searches 3 years ago, but I cannot find it. In general, it is not much less than 12! And 12! - this is dofiga. ten! - yes, in seconds I looked for simple ways, going through all the options with truncations. 12! I was looking for minutes 2. And then already long and long. - VostokSisters