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

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?

• Papers or books by Jacques Pitrat could give you more ideas. See also his blog. I hope to (re)implement some of them in RefPerSys in 2022. Jan 4 at 20:07
• Can you share where you encountered this task? Can you credit the original source?
– D.W.
Jan 5 at 1:15
• Maybe there is a typo: when discussing the four paths under "My approach" it seems to me that the second path should get to (X1, y2) and the fourth one should lead to (x2,y1). Is this correct? Jan 6 at 2:30

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.