1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 4 at 20:07
  • 1
    $\begingroup$ Can you share where you encountered this task? Can you credit the original source? $\endgroup$
    – D.W.
    Jan 5 at 1:15
  • $\begingroup$ 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? $\endgroup$ Jan 6 at 2:30
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I would say this is not an answer D.W. ... $\endgroup$ Jan 5 at 23:49
  • $\begingroup$ @CarlosLinaresLópez, OK! I can see why you'd say that. Any time you see something that does not appear to be an answer, you're always welcome to flag it as 'not an answer'. If you'd like a chance to give additional explanation, you can flag as 'in need of moderator intervention' and provide additional explanation. In this case one of the other mods will review that flag (we don't handle flags on our own posts). $\endgroup$
    – D.W.
    Jan 5 at 23:54
  • $\begingroup$ No need to take it so seriously D.W. I can see the problem is rather simple and that all you are trying is to help providing a nice hint. It is only that I got surprised seeing this posted as an answer instead of a comment. Happy new year! $\endgroup$ Jan 6 at 2:36
  • 1
    $\begingroup$ @CarlosLinaresLópez, thank you, and happy new year to you too! I'd be happy if others would like to see this moved to a comment. I'm reluctant to write a full algorithm given that this appears to be a contest-style question where the poster has declined to identify the source of the question. I was thinking that this provides the core insight needed to solve the problem, but if others disagree that this should be an answer I'm fine with that decision. $\endgroup$
    – D.W.
    Jan 6 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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