14

Let's say you have a grid like this (made randomly):

grid

Now let's say you have a car starting randomly from one of the while boxes, what would be the shortest path to go through each one of the white boxes? You can visit each white box as many times as you want and can't jump over the black boxes. The black boxes are like walls. In simple words you can move from white box to white box only.

You can move in any direction, even diagonally.

Two subquestions:

  1. Assume you know the position of all black boxes before moving.
  2. Assume you only know the position of a black box when you are in a white box adjacent to it.
Ilmari Karonen
  • 49,047
  • 9
  • 93
  • 153
Laz
  • 6,036
  • 10
  • 41
  • 54
  • "what would be the shortest path to go through each one of the white boxes"? What are you asking here? Do you mean "to go to each one of the white boxes"? – amara May 20 '10 at 16:50
  • Yea.. you just need to traverse through ALL the white boxes. – Laz May 20 '10 at 16:52
  • To find the shortest path, you have to do a brute force search. It doesn't really matter if you know the black boxes up front or not. – mdma May 20 '10 at 16:57
  • 1
    duplicate: http://stackoverflow.com/questions/745942/visit-all-nodes-in-a-graph-with-least-repeat-visits – Rubys May 20 '10 at 17:00
  • brute force? come on! @Rubys no its not a duplicate.. – Laz May 20 '10 at 17:06
  • This is NOT the TSP. In tsp you can visit a vertex only ONCE. If that were the case most of these sqaures wud be un-reachable! – Laz May 20 '10 at 17:18
  • @Sysadmin: This is not the traveling salesman problem. In TSP, every node is connected, and you visit each node once. – BlueRaja - Danny Pflughoeft May 20 '10 at 17:18
  • You know what, it really is not a duplicate. My bad. However, it's very similar, so I'll keep the link there. – Rubys May 20 '10 at 17:24
  • @Ram Bhat, @BlueRaja - sry...i did miss out the fact that each node could be visited more than once – SysAdmin May 20 '10 at 17:45

6 Answers6

4

You should model the problem as a complete graph where the distance between two nodes (white boxes) is the length of the shortest path between those nodes. Those path lengths can be calculated by the Floyd-Warshall algorithm. Then, you can treat it as "Traveling salesman", like glowcoder wrote.

EDIT: to make it more clear: you can describe each "interesting" path through the maze by a sequence of different white boxes. Because if you have an arbitrary path visiting each white box, you can split it up into sub-paths each one ending at a new white box not visited so far. Each of this sub-paths from white box A to B can be replaced by a shortest sub-path from A to B, that's why you need the shortest-paths-between-all-pairs-of-nodes matrix.

Doc Brown
  • 19,739
  • 7
  • 52
  • 88
  • This is pretty convoluted. TSP applies directly. Why go through Floyd-Warshall? -1 till you elaborate further. –  May 20 '10 at 18:08
  • @Moron: from Wikipedia, first sentence: "the task is to find a shortest possible tour that visits each city *exactly once*". That is what my suggestion does: allowing to see the problem as a TSP problem of that kind, even if you have to visit each square more than once. – Doc Brown May 20 '10 at 19:23
  • @Doc: I see what you are getting at. I will remove the -1. Still pretty convoluted though. I removed a space to allow me to undo the -1. –  May 20 '10 at 19:32
  • @Moron: if you have a better idea to make it "less convoluted", please let me know. – Doc Brown May 20 '10 at 20:02
  • @Doc: Even if we find the exact optimum solution to the resulting TSP, is it true that we have the optimum answer for the original problem? To make it less convoluted, at least for approximation algorithms, some simple algorithms like the euler trail of the minimum spanning tree exist. This must be a well studied problem. If you have a reference which shows your approach works, great! –  May 20 '10 at 20:21
  • @Moron: if you read my edited section carefully, you will see that it proves the optimality. Apply the replacement of the sub-paths to an optimal solution of the original problem. – Doc Brown May 20 '10 at 20:34
  • @Doc: I didn't see you edit the answer. You are right. That seems to work! Coupled with the fact that it is likely NP-Complete... +1. –  May 20 '10 at 21:14
1

This seems to be an NP-Complete problem.

Hamiltonian Path in grid graph is NP-Complete has been shown here: Hamilton Paths in Grid Graphs.

Note grid graph = subgraph of the complete grid.

Of course, I haven't read that paper, so confirm it first, especially the diagonal movement allowed part.

  • How does this reduce to finding a Hamiltonian path? He explicitly says that you can visit each white box as often as you want, which is not the case in a Hamiltonian path. – bnaul May 20 '10 at 18:43
  • @bnaul: A reduction similar to http://stackoverflow.com/questions/2359345/non-cycle-path-to-all-nodes/2360303#2360303 will probably work. –  May 20 '10 at 18:48
1

Doc has got it. I'll add that the black boxes only change the distance between all pairs of white boxes. Further elaboration - if there's a black box on the diagonal between any two white boxes (easily checked), you need to calculate a shortest path to get the distance. Once you have a distance matrix, then solve a TSP or a Hamiltonian Path by solving a TSP after creating a dummy node with length zero to all other nodes.

The key is that in order to formulate and solve the TSP (or any problem formulation for that matter), you MUST have a distance matrix to start with. The distance matrix isn't specified at the start so it must be developed from scratch.

Grembo
  • 1,223
  • 7
  • 6
1

while the TSP based heuristic is a reasonable approach, it's not clear it gives the optimal answer. The problem (as Moron points out) is the spanning trail problem, and in the link provided in the comment, there are many special cases for which there are linear time optimal solutions. One catch that makes the OP's problem different from the grid graph formulation used in the cited paper is the ability to traverse diagonally, which changes the game quite a bit.

Suresh
  • 602
  • 5
  • 13
0

This is similar to the Knights Tour problem, where a typical solution evaluates all possible routes originating from the starting square. When a tour cannot be completed, then backtracking is used to return to back up on previous decisions. Your problem is more relaxed since you can visit squares more than once. The Knights tour and Travelling Saleman problems typically require visiting each square exactly once.

See http://en.wikipedia.org/wiki/Knight's_tour

mdma
  • 56,943
  • 12
  • 94
  • 128
  • If you can visit squares more than once, how do you determine when a tour cannot be completed (and hence it's time to start backtracking)? Usually this is determined when all nearby squares have already been visited - but that no longer applies if you can visit them twice :-) – psmears May 21 '10 at 10:01
  • You can do reachability analysis from sqaure to square - e.g. evaluate all paths from a source square to a target square. Here, you avoid cycles, we just need a path, so each square is visited just once. As an example, consider a board where the black squares down the center partition it into two halves. The squares in the half you start on are reachable, the squares in the other half are not. – mdma May 21 '10 at 10:12
-1

Try building it as a graph (where each node has at most 8 other nodes) and treat it like the http://en.wikipedia.org/wiki/Travelling_salesman_problem

corsiKa
  • 81,495
  • 25
  • 153
  • 204
  • -1 The fact that it can be reduced to an NP-complete problem (which you have not even shown) is no more help than telling him to brute force it. – BlueRaja - Danny Pflughoeft May 20 '10 at 17:20
  • @BlueRaja: only because you do not like the answer, it is not wrong. I would have given -1 to glowcoder because his answer ignores the fact that TSP normally needs every city to be visited exactly once, which is not the appropriate model here, because one needs to visit some white boxes more than once. – Doc Brown May 20 '10 at 17:30
  • The TSP does not require each to be visited exactly once. It merely cares about the shortest path between two cities regardless of it travels through a city it already travelled to along the way. No matter how you slice it this is an NP hard problem, and I believe it is best approached using the same approach as TSP. – corsiKa May 20 '10 at 17:34
  • @BlueRaja, @Doc Brown. Spanning trail(each vertex at least once) in grid graphs (subgraph of grid) is NP-Complete. Here is the link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3040. @DocBrown: Finding the shortest walk which visits each vertex at least once in general graphs is also NP-Complete, it is easy to prove. Try it. –  May 20 '10 at 17:37
  • @glowcoder: Any problem in NP (and thus also in P) can be modeled by TSP, and thus can be solved using TSP-algorithms, so this answer is not helpful (there could still potentially be an efficient solution to this problem). What *would* be helpful is showing that an efficient solution to this problem would give an efficient solution to TSP, thereby proving it to be NP-complete (in which case, this solution is about as good as you're going to get). I believe this is the case, but no one here has shown it yet. – BlueRaja - Danny Pflughoeft May 20 '10 at 17:38
  • @BlueRaja: It seems to be NP-Complete. Check out the link in my answer. –  May 20 '10 at 18:19