patternMinor
Linear Path Optimization with Two Dependent Variables
Viewed 0 times
linearpathwithoptimizationtwovariablesdependent
Problem
Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best.
There are two runners on a line that goes from $x=0$ to $x=100$. The two runners start at $x=50$. The runners are then given an array of coordinate pairs that they must visit. The catch is, the coordinate pair contains the $x$ value for locations runner 1 and runner 2 must be at the same time. So for example, if they are given a coordinate pair $(40, 70)$, to successfully "complete" that coordinate, runner 1 must go to $x=40$, and runner 2 must go to $x=70$. They can't move on to the next coordinate pair until both have reached their destination.
So given a large array of coordinate pairs, the runners have to visit each coordinate pair in any order they chose. The runners can move at the same time and have the same speed. The trick is how to optimize the order in which they visit the coordinates. For example, if runner 1 is at $x=10$, and runner 2 is at $x=90$, it would be inefficient to chose a coordinate pair like $(80,80)$, because runner 2 would only travel $10$ units, and spend a long time waiting while runner 1 is moving $70$ units. This is sort of like the travelling salesman problem, except there are two people involved dependent on each other, and they can visit any point from any other given point in any order.
Does anyone have any ideas how to create an algorithm that would return the best (or at least good) optimized order in which they would visit these coordinate pairs?
There are two runners on a line that goes from $x=0$ to $x=100$. The two runners start at $x=50$. The runners are then given an array of coordinate pairs that they must visit. The catch is, the coordinate pair contains the $x$ value for locations runner 1 and runner 2 must be at the same time. So for example, if they are given a coordinate pair $(40, 70)$, to successfully "complete" that coordinate, runner 1 must go to $x=40$, and runner 2 must go to $x=70$. They can't move on to the next coordinate pair until both have reached their destination.
So given a large array of coordinate pairs, the runners have to visit each coordinate pair in any order they chose. The runners can move at the same time and have the same speed. The trick is how to optimize the order in which they visit the coordinates. For example, if runner 1 is at $x=10$, and runner 2 is at $x=90$, it would be inefficient to chose a coordinate pair like $(80,80)$, because runner 2 would only travel $10$ units, and spend a long time waiting while runner 1 is moving $70$ units. This is sort of like the travelling salesman problem, except there are two people involved dependent on each other, and they can visit any point from any other given point in any order.
Does anyone have any ideas how to create an algorithm that would return the best (or at least good) optimized order in which they would visit these coordinate pairs?
Solution
You can consider the 1D-position of the 2 runners as one 2D-position.
X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100).
Then all the goal points coordiantes can have a 2D-position in the same way, for instance (40, 70). Now the Travelling salesman problem has to be solved using the Tchebychev distance (infinite norm). I am pretty sure this is NP-complete.
A simple heuristic approach may be to always run to the next closest point (greedy nearest neighboor). Or you can either look for a more sophisticated one...
X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100).
Then all the goal points coordiantes can have a 2D-position in the same way, for instance (40, 70). Now the Travelling salesman problem has to be solved using the Tchebychev distance (infinite norm). I am pretty sure this is NP-complete.
A simple heuristic approach may be to always run to the next closest point (greedy nearest neighboor). Or you can either look for a more sophisticated one...
Context
StackExchange Computer Science Q#106508, answer score: 4
Revisions (0)
No revisions yet.