Finding the shortest path to visit all non-blocked squares on a grid

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

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.
开发者_如何学Go
2. Assume you only know the position of a black box when you are in a white box adjacent to it.

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.

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.

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.

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.

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

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