4
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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...

Improve this answer
$\endgroup$
3
$\begingroup$

As Vince observes, your problem is TSPP (traveling salesman path problem) on the plane with respect to the $L_\infty$ metric. On the plane, the $L_\infty$ and $L_1$ metrics are equivalent (the unit balls differ by a rotation of $45^\circ$), so your problem is equivalent to TSPP on the plane with respect to the $L_1$ metric. This problem has been addressed on this question.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ For those readers who have less of a background with metrics and unit circles/spheres: Wikipedia article about unit spheres where you can see the $L_\infty$ and $L_1$ circles. $\endgroup$
    – einpoklum
    Commented Apr 5, 2019 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.