Minimum steps needed to partially cover a sequence of points on a grid

Question

Problem statement: You are in a 2D grid where you can move in any of the 4 directions, no obstacles. You start at position (0, 0).

We say that you partially cover a point $(x,y)$ if your position has the same abscissa or the same ordinate (or both).

You are given an ordered sequence of n points $(x_1,y_1), ..., (x_n,y_n)$, which you need to partially cover in that order. Find the distance of shortest path which partially covers the sequence of points.

Constraints (just to give an order of magnitude): $n=20 000$ and $0<=x,y<=5000$, and time execution should be <5s.

My approach:

At first I thought this might be a dynamic programming problem. But now I just don't see how it could be applied.

Brute force approach: Starting from $(0, 0)$ there are only two good paths that cover the first point $(x_1, y_1)$: go to $(x_1, 0)$ or $(0, y_1)$.

Then there are only four paths that are good candidates to cover the 1st, and 2nd point:

• $(x_1, 0)->(x_2,0)$
• $(x_1, 0)->(x_2,y_1)$
• $(0, y_1)->(0, y_2)$
• $(0, y_1)->(x_1, y_2)$.

And so on. We can explore the tree of all good possible paths, where at the step n, we can choose between $2^n$ paths. Of course we only need to keep track for each path of its final position and the total distance.

Pruning exploration approach: Now my idea is to do this exploration, in breadth-first order (BFS exploration), but with some pruning. At each step I can eliminate some possibilities. Indeed consider two paths, which both cover the first $n$ points.

• path $p$ with last position $(p_x, p_y)$ and total distance $p_d$,
• and path $q$ with last position $(q_x, q_y)$ and total distance $q_d$,
• If $p_d > q_d + abs(q_x-p_x)+abs(q_y-p_y)$, then we know for certain that the path $p$ is worse than path $q$, no matter what is the position of the next point $(x_{n+1}, y_{n+1})$
• I can then eliminate at each depth of the BFS all the possibilities for which that last condition is true
• Issue: this pruning does eliminate a lot of possibilities, but not enough it seems.

Question1: Does this problem have a name? I think it can be re-stated as a linear integer programming optimisation problem. Or it may be re-formulated as some kind of vertex cover problem?

Question2: Can I improve my solution? More clever pruning, change exploration strategy (Depth-first-search, something else)? Is there a different, better approach?

Answer 1

There is a straightforward dynamic programming algorithm. You only need to know, for each $i,j$, the length of the shortest path to $(x_i,y_j)$ that covers the first $i$ points, and the length of the shortest path to $(x_j,y_i)$ that covers the first $i$ points. I'll let you discover why that suffices.

You should be able to take it from here. See our resources on dynamic programming for a systematic framework for approaching dynamic programming algorithms: https://cs.stackexchange.com/tags/dynamic-programming/info