Part I
Part II
It turns out I was incorrect at the end of part II. There is in fact a polynomial time algorithm for this problem:
Courtesy of ishkabible and this question.
The algorithm is as follows:
I had to do a little re-learning, as I hadn’t done trigonometry is quite a while. Calculating the bearing distance (via atan2) gives us an angle of degrees from point i to point i+j clockwise. Subtracting 180 degrees culls our search space to only movements that would put us further from the origin. Thus, this algorithm is effectively a greedy search and will give us a max, but unfortunately not all maxes like the previous examples. Improvements could include some state keeping and branching to walk back when we hit an end of a path that is not greater than the max. Thus, in this scenario, ordering of elements does have bearing on which max is returned.
Code:
Output:
Part II
It turns out I was incorrect at the end of part II. There is in fact a polynomial time algorithm for this problem:
Quote
You are on a 2D graph starting at the origin (0,0). Given n vector movements (x,y), what is the max euclidean distance you can be from the origin? You can only use each movement once, but are not required to use each one.
Courtesy of ishkabible and this question.
The algorithm is as follows:
For each movement i in the set move from the origin to the spot denoted by i For each movement j in the set if i == j continue calculate the bearing angle from i to the point i+j and subtract 180 if the degree result is >= 0 then we are moving away from the origin, add the movement sum the temp distance and check to see if it is greater than our currently tracked max if so, add it to the result set cull the result set to have only the highest distances
I had to do a little re-learning, as I hadn’t done trigonometry is quite a while. Calculating the bearing distance (via atan2) gives us an angle of degrees from point i to point i+j clockwise. Subtracting 180 degrees culls our search space to only movements that would put us further from the origin. Thus, this algorithm is effectively a greedy search and will give us a max, but unfortunately not all maxes like the previous examples. Improvements could include some state keeping and branching to walk back when we hit an end of a path that is not greater than the max. Thus, in this scenario, ordering of elements does have bearing on which max is returned.
Code:
//return the bearing degree (we'll subtract 180 to see if we're moving farther away from the origin) double bearing(double a1, double a2, double b1, double b2) { static const double TWOPI = 6.2831853071795865; static const double RAD2DEG = 57.2957795130823209; double theta = atan2(b1 - a1, a2 - b2); if (theta < 0.0) theta += TWOPI; return RAD2DEG * theta; } void calculate_all_dist_polynomial_time(const Point& start, vector<Movement>& movements, set<Result, result_cmp>& results){ cout << "[polynomial] Starting at: " << start << " with " << movements.size() << " max moves\n"; Point tmp(start); int count = 0; int max_dist = 0; // O(n^2) for(int i = 0; i < movements.size(); i++){ Result result; int x_sum = 0; int y_sum = 0; Movement& one = movements.at(i); x_sum += movements.at(i).x; y_sum += movements.at(i).y; result.movements.push_back(movements.at(i)); for(int j = 0; j < movements.size(); j++){ Movement& two = movements.at(j); if(one == two) continue; //don't evaluate the same one, does not take care of edge case of multiple of the same value double degree = bearing(x_sum, y_sum, (x_sum+two.x), (y_sum+two.y)); if ((degree - 180) >= 0){ result.movements.push_back(movements.at(j)); x_sum += movements.at(j).x; y_sum += movements.at(j).y; Point end(x_sum, y_sum); result.dist = euc_dist(start, end); result.moves = result.movements.size(); if(result.dist >= max_dist){ results.insert(result); max_dist = result.dist; } } } } //cull out any < max distance elements that were added before actual max was discovered set<Result, result_cmp>::iterator it = results.begin(); while(it != results.end()){ if (it->dist < max_dist) results.erase(it); it++; } }
Output:
Quote
[polynomial] Starting at: [0,0] with 5 max moves
Result: dist:5 moves: 2 >> (0,0) (-3,1) (-2,-2)
Result: dist:5 moves: 3 >> (0,0) (-3,1) (-2,-2) (0,2)
Result: dist:5 moves: 2 >> (0,0) (-3,1) (-2,-2)
Result: dist:5 moves: 3 >> (0,0) (-3,1) (-2,-2) (0,2)
1 Comments On This Entry
Page 1 of 1
ishkabible
07 January 2018 - 07:29 PM
Uhmmm rereading this I realized I made a mistake in part II. It shouldn't be within + or - 90 degrees it should be + or - 45 degrees. That should probably cause it to find all maximums.
Page 1 of 1
← September 2021 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 |
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
4 user(s) viewing
4 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)