2

I am looking for an algorithm to fidn the longest path between two points on a grid, with the added restriction that you cannot revisit a cell on the grid. (Also, you can only move up, down, left, and right).

Given these restrictions, I imagine that walking the longest path is the same as trying to fill as much of the space as possible. However, I have some difficulting in figuring out how to do this.

Paul Manta
  • 30,618
  • 31
  • 128
  • 208
  • Is the grid rectangular? I think it may be possible to visit all of the points in the grid almost always... unless the grid is really small. – rliu May 12 '13 at 10:18
  • @roliu It is not rectangular. – Paul Manta May 12 '13 at 10:21
  • 1
    Are there obstacles on the grid? Note that for general graphs this is [longest-path problem](http://en.wikipedia.org/wiki/Longest_path_problem), which is [NP-Complete](http://en.wikipedia.org/wiki/NP-complete) – amit May 12 '13 at 10:22
  • @amit There are obstacles in the sense that there may be walls anywhere in the map. I know the general problem is NP-hard (not complete), but I was thinking maybe this specific case can be solved in polinomial time. At any rate, the maps are *aproximatelly* rectangular, so an algorithm that fills out a rectangular map is still going to be pretty helpful. – Paul Manta May 12 '13 at 10:26
  • @amit For example, I could find the largest rectangle that fits in the area I am currently in and fill that one out (I might not visit a few cells, but that's okay). Then do the same for the next rectangle, etc. – Paul Manta May 12 '13 at 10:29
  • 1
    If the edge weights are uniform, I would look into space-filling curves. – G. Bach May 12 '13 at 10:45
  • An algorithm to fill in the rectangle seems feasible but very ugly... it seems like it has a lot of corner cases. I'm not convinced there is an elegant solution to it and you may just have to work through them by hand. I think the way I'd fill the rectangle would be to take the end point `t` and split the grid into four sections using `t` as the center (basically, the origin of a normal cartesian coordinate system). If the start point `s` lies in some section (say the south-west section), I'd fill up the opposite section last (in my example, the north-east section). – rliu May 12 '13 at 10:59
  • How big are the grids/maps? – גלעד ברקן May 12 '13 at 10:59
  • A technique to do this is explained in the Art of Computer Programming, chapter 7.1.4, "ZDDs to represent simple paths". See also exercise 227 (and others). – harold May 12 '13 at 11:13
  • 1
    The heuristic version of Angluin–Valiant gives [pretty good results](http://stackoverflow.com/questions/15898884/fill-2d-grid-with-single-path/15904295#15904295). – David Eisenstat May 12 '13 at 12:10

2 Answers2

0

The longest-path problem is still NP-hard on general grid-graphs (the kind which you are describing).

This is due to the fact that Hamiltonian path is NP-complete on general grid graphs. The reduction is then the same: a fast longest-path solver would immediately give you a fast Hamiltonian path solver, simply by comparing the length of the longest path between every pair of nodes to n-1.

Martin
  • 157
  • 1
  • 3
  • 8
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • Is the Hamiltonian path in a square grid also NP-hard? If not, how might I find such a path? – Paul Manta May 12 '13 at 13:47
  • @PaulManta Rectangular grid graphs have an HP/HC if at least one of the sides has even length (see for example [mathworld](http://mathworld.wolfram.com/GridGraph.html)). If you number the nodes as you would the cells of a matrix with n being the number of rows and m being the number of columns, start the path at (1,1), go down to (n,1), go to (n,2), go up to (2,2), over to (2,3), down again, right, up,etc until you reach (2,m). Then go to (1,m) and back to (1,1). Exactly like you would play Snake, if that helps visualizing it. – G. Bach May 12 '13 at 14:12
  • @PaulManta For rectangular grid graphs, this approach will even give you an HP regardless of whether the length or width of the rectangle is even. The problem of NP-completeness of HP for general grid graphs is that those need not be rectangular; for example, any traversal graph (using BFS/DFS/some other traversal algorithm) of any grid graph would be a grid graph itself since it is a node-induced subgraph of the grid, but it would not be rectangular in general (it also wouldn't have an HP in general, but that's not the point here). – G. Bach May 12 '13 at 14:22
  • Small correction: if you want an HP regardless of whether the side lengths of the rectangular grid graph are even, go all the way up, don't stop at (2,k). – G. Bach May 12 '13 at 15:28
  • @Paul: In case you're confused: G.Bach is not disagreeing with me. You stated in the comments that you have obstacles *(aka arbitrary nodes can be removed)*, which is a more general version of G.Bach's NP-complete hamiltonian-path problem for non-rectangular grid-graphs. *(Also, he made a slight mistake: the even-length rule is for hamiltonian circuits only. **All** complete rectangular grid-graphs (with no obstacles) have a hamiltonian path)*. – BlueRaja - Danny Pflughoeft May 12 '13 at 18:21
  • @BlueRaja-DannyPflughoeft I did mention that rectangular graphs have an HP regardless of whether at least one side has even length. The implication still holds for general rectangular grid graphs; at worst, it was ill-phrased. – G. Bach May 12 '13 at 22:41
0

Here is linear time algorithm for 2D grid: http://www.sciencedirect.com/science/article/pii/S0166218X11003088

If the grid is not rectangular, then the problem is NP-hard and you should use some variation of algorithm for solving travelling salesman problem - e.g. one using integer linear programming.

usamec
  • 2,156
  • 3
  • 20
  • 27
  • He stated in the comments that there are obstacles, so it is not a *complete* grid-graph, only a partial one. The linear-time algorithm *(which was already mentioned by several people in the comments)* does not apply here. – BlueRaja - Danny Pflughoeft May 13 '13 at 01:03