Shortest Path algorithm of a different kind

tags:

algorithm

views:

380

answers:

+12 Q:

Shortest Path algorithm of a different kind

Hey guys,

Lets say you have a grid like this (made randomly)

alt text

Now lets 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 cant 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.

edit :

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

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

glowcoder 2010-05-20 16:57:42

-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 2010-05-20 17:20:52

@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 2010-05-20 17:30:32

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.

glowcoder 2010-05-20 17:34:23

@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.

Moron 2010-05-20 17:37:54

@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 2010-05-20 17:38:58

@BlueRaja: It seems to be NP-Complete. Check out the link in my answer.

Moron 2010-05-20 18:19:55

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 2010-05-20 16:59:43

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 2010-05-21 10:01:02

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 2010-05-21 10:12:03

+5 A:

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 2010-05-20 17:10:34

This is pretty convoluted. TSP applies directly. Why go through Floyd-Warshall? -1 till you elaborate further.

Moron 2010-05-20 18:08:12

@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 2010-05-20 19:23:24

@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.

Moron 2010-05-20 19:32:12

@Moron: if you have a better idea to make it "less convoluted", please let me know.

Doc Brown 2010-05-20 20:02:39

@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!

Moron 2010-05-20 20:21:51

@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 2010-05-20 20:34:11

@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.

Moron 2010-05-20 21:14:08

+1 A:

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.

Moron 2010-05-20 18:16:42

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 2010-05-20 18:43:43

@bnaul: A reduction similar to http://stackoverflow.com/questions/2359345/non-cycle-path-to-all-nodes/2360303#2360303 will probably work.

Moron 2010-05-20 18:48:40

+1 A:

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 2010-05-20 20:09:37

+1 A:

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 2010-06-30 20:56:42

ansaurus

tags:

views:

answers:

Shortest Path algorithm of a different kind

related questions