2
$\begingroup$

My algorithm-fu is really weak and I do not know how to express following problem in terms of any other problem known to me:

Given a small rectilinear grid and coordinates of four cells in this grid (let's call these cells A, B, C and D) find a shortest path which connects cells A => B => C => D (in this order, with no return back to A) so that each intermediate cell is visited at most once. Connections between cells can be only rectilinear (each cell can be connected only to the cells on its left/right/top/bottom).

Initially I thought of this problem as something similar to a wire routing on a PCB grid and searched for related algorithms, but all I found were optimal algorithms (Maze Runner, Lee) which usually described only networks with at most two connectors (or other extremely trivial cases), or algorithms which give non-optimal solutions (for example, Line Search).

Then I thought it might be possible to solve it with some path finding algorithm (A* with some fancy cost function, maybe) but I have no idea how to apply the requirements to such approach.

I think it might be something related to TSP, but I am not able to see this relation, nor even if I knew one, I do not know how to solve such problem in general. Note that I need an optimal solution, and even if problem is NP-hard (which I think it is), the problem size is guaranteed to be small enough for me to be able to find the asked path in a reasonable time.

I tried a few approaches:

  • For each permutation of {AB, BC, CD} find shortest path for each pair. But two problems here:
    • From all possible shortest segments connecting AB and BC, I do not know which one to pick, and the choice influences the shape of segments for remaining pair(s). I can try them all, but then:
    • I think (not sure tho) that solution might not include any shortest segment at all (i.e. final, optimal solution might consist solely of sub-optimal elementary segments). Am I right?
  • The only way I found to make problem easier is to limit the search to the bounding box of the cells of interest (with small adjustments if some cells are located on the same row/column or on an edge, then bounding box needs to be expanded by one or two cells).
  • Another approach that I thought of (did not try yet) is to apply following algorithm:

    • Remove all rows and columns from the grid which do not contain A, B, C nor D - this step would make the grid 'dense', so there would be no empty rows/cols between obligatory cells,
    • Calculate (possibly brute force with some DFS, or maybe even precalculate and hardcode) a solution for this reduced grid,
    • 'Explode' this reduced solution by inserting empty rows and columns back, extending the connecting edges appropriately.
    • However, this algorithm is something I came up myself with, I have not tested yet, I could not find anything similar described anywhere (what makes me think it would not work ;) ), it's not supported by anything but just a desperate idea :)

Can this problem be expressed as a (possibly some special case of) TSP? If so, how can I reduce it so I could apply algorithms for solving this case of TSP? If not, what approach would you suggest?

EDIT: Below you can find two examples of non-trivial, tricky input (paths are added by me and I think they are correct ones, but maybe there are shorter ones I cannot see? ;) )

  0123456789     01234567   
 ╔══════════╗   ╔════════╗  
0║ B┐D A─┐  ║  0║A─┐D┐   ║  
1║ ││└──┐│  ║  1║C┐└┐│   ║  
2║ ││   ││  ║  2║││ ││   ║  
3║ ││   ││  ║  3║│└─B│   ║  
4║ │└───C│  ║  4║└───┘   ║  
5║ └─────┘  ║  5║        ║  
6║          ║   ╚════════╝  
 ╚══════════╝   
$\endgroup$
  • $\begingroup$ This question looks like very well written. Can you show a non-trivial specific example? If the problem comes from an online source, can you provide a URL? If it comes from your real life, then can you provide a bit background? $\endgroup$ – Apass.Jack Oct 9 '18 at 2:20
  • $\begingroup$ @Apass.Jack I got this problem as a riddle from my friend, and he got it from some competitive coding web site like UVA Online Judge, CodeWars, or something (he loves those!), or maybe his uni. It was wrapped in some humoristic narrative about a TRON-like lightbike driver who needs to travel CPU City from point A to point D through checkpoints B and C (TRON reference for those who need it: youtube.com/watch?v=-3ODe9mqoDE ). But at the moment, I do not have the exact statement of the task, unfortunately :( $\endgroup$ – Maciek Oct 9 '18 at 8:02

Your Answer

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

Browse other questions tagged or ask your own question.