Another interesting problem that eventually got locked.
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.
This problem is a twist on the Traveling Salesman Problem. We don't have to visit an exact number of locations (or movements), but we do have to max it.
Brute forcing this solution involves enumerating all permutations of the movement vectors and iterating through them, marking off max results as we go. An exponential running time can be found using dynamic programming and that will be the focus of a future post.
Algorithm:
There is a custom comparator for the set. This allows us to merely call insert and let the set worry about duplicates based on permutations. We implement a strict weak ordering.
The run time for this algorithm is O(n!), yes factorial. Given a vector of 5 movements, there are 120 different combinations to try. Yikes!
structs.h
main.cpp
Output:
Note that we have each result that matches the max distance. The one reported as the result was simply the last one we found. Restrictions could be put in place to find the max with the min number of moves, etc...
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.
This problem is a twist on the Traveling Salesman Problem. We don't have to visit an exact number of locations (or movements), but we do have to max it.
Brute forcing this solution involves enumerating all permutations of the movement vectors and iterating through them, marking off max results as we go. An exponential running time can be found using dynamic programming and that will be the focus of a future post.
Algorithm:
Quote
Each movement is added to a vector.
Sort the movements by x value. This allows us to use the std::next_permutation
For each permutation of the movements vector
--iterate through the movements
----add x and y to the current x and y (we start at the origin and maintain a running tally)
----calculate the current euclidean distance
----if the dist is greater than the current max, add the result to a result set
After we are done run through the result set and get rid of any dist less than the current max. (The first local maxes will be in here, hence the removal).
Sort the movements by x value. This allows us to use the std::next_permutation
For each permutation of the movements vector
--iterate through the movements
----add x and y to the current x and y (we start at the origin and maintain a running tally)
----calculate the current euclidean distance
----if the dist is greater than the current max, add the result to a result set
After we are done run through the result set and get rid of any dist less than the current max. (The first local maxes will be in here, hence the removal).
There is a custom comparator for the set. This allows us to merely call insert and let the set worry about duplicates based on permutations. We implement a strict weak ordering.
The run time for this algorithm is O(n!), yes factorial. Given a vector of 5 movements, there are 120 different combinations to try. Yikes!
structs.h
#ifndef __STRUCTS_H #define __STRUCTS_H #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <iterator> using namespace std; struct Movement{ Movement(int a, int b):x(a),y(b){} int x; int y; friend ostream& operator<<(ostream&, const Movement&); }; bool operator <(const Movement& lhs, const Movement& rhs){ return lhs.x < rhs.x; } bool operator ==(const Movement& lhs, const Movement& rhs){ return ((lhs.x == rhs.x) && (lhs.y == rhs.y)); } ostream& operator<<(ostream& os, const Movement& rhs){ os << "(" << rhs.x << "," << rhs.y << ")"; return os; } struct Point { Point():x(0),y(0) {} Point(int a, int b):x(a),y(b) {} Point(const Point& p):x(p.x),y(p.y) {} int x; int y; friend ostream& operator<<(ostream&, const Point&); Point& operator+=(const Movement& rhs){ this->x += rhs.x; this->y += rhs.y; return *this; } }; ostream& operator<<(ostream& os, const Point& rhs){ os << "[" << rhs.x << "," << rhs.y << "]"; return os; } struct Result { Result():dist(0),moves(0) {} int dist; int moves; vector<Movement> movements; friend ostream& operator<<(ostream&, const Result&); }; ostream& operator<<(ostream& os, const Result& rhs){ os << "Result: dist:" << rhs.dist << " moves: " << rhs.moves << " >> (0,0) "; for(const Movement& m : rhs.movements) os << m << " "; return os; } //comparison functor to put Results in a set //check the dist/max, then check length of movements //then check if it's a permuation and throw it away if it is - path ordering does not matter struct result_cmp { bool operator()(const Result& lhs, const Result& rhs){ if (lhs.moves < rhs.moves) return true; if (lhs.dist < rhs.dist) return true; if(lhs.movements.size() < rhs.movements.size()) return true; if(lhs.movements.size() == rhs.movements.size()) { if (is_permutation(lhs.movements.begin(), lhs.movements.end(), rhs.movements.begin())){ return false; } //no perm, enforce strict weak ordering for(int i = 0; i < lhs.movements.size(); i++){ if(lhs.movements.at(i) < rhs.movements.at(i)) return true; } } return false; } }; #endif
main.cpp
#include "structs.h" int euc_dist(const Point& start, const Point& end){ int dx = start.x - end.x; int dy = start.y - end.y; return sqrt(dx*dx + dy*dy); } void calculate_all_dists(const Point& start, vector<Movement>& movements, set<Result, result_cmp>& results){ cout << "Starting at: " << start << " with " << movements.size() << " max moves\n"; Point tmp(start); sort(movements.begin(), movements.end()); int count = 0; int x = 0, y = 0; Result result; do { for(int i = 0; i < movements.size(); i++) { x += movements.at(i).x; y += movements.at(i).y; Point end(x,y); int tmp_dist = euc_dist(start, end); if (tmp_dist >= result.dist) { result.movements.clear(); result.dist = tmp_dist; result.moves = i+1; for(int j = 0; j <= i; j++) result.movements.push_back(movements.at(j)); results.insert(result); } } ++count; } while(next_permutation(movements.begin(), movements.end())); cout << "Total permutations: " << count << endl; cout << "Max distance: " << result << endl; //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 < result.dist) results.erase(it); it++; } } int main(){ Point start(0,0); vector<Movement> movements; set<Result, result_cmp> results; //initial sample set movements.push_back(Movement(2,-2)); movements.push_back(Movement(-2,-2)); movements.push_back(Movement(0,2)); movements.push_back(Movement(3,1)); movements.push_back(Movement(-3,1)); calculate_all_dists(start, movements, results); for(const Result& result : results) cout << result << endl; return 0; }
Output:
Quote
Starting at: [0,0] with 5 max moves
Total permutations: 120
Max distance: 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: 2 >> (0,0) (2,-2) (3,1)
Result: dist:5 moves: 3 >> (0,0) (-3,1) (-2,-2) (0,2)
Result: dist:5 moves: 3 >> (0,0) (0,2) (2,-2) (3,1)
Total permutations: 120
Max distance: 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: 2 >> (0,0) (2,-2) (3,1)
Result: dist:5 moves: 3 >> (0,0) (-3,1) (-2,-2) (0,2)
Result: dist:5 moves: 3 >> (0,0) (0,2) (2,-2) (3,1)
Note that we have each result that matches the max distance. The one reported as the result was simply the last one we found. Restrictions could be put in place to find the max with the min number of moves, etc...
1 Comments On This Entry
Page 1 of 1
ishkabible
22 November 2017 - 07:46 PM
So the first optimization is to realize that addition of vectors is associative and commutative so we can just test every subset instead of every permutation making the running time O(2^n) so there's at least one more brute force solution that's better. I'm sure there are better options but that's one quick optimization.
Page 1 of 1
← October 2019 →
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 | 31 |
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
1 user(s) viewing
1 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)