Hi,
I am currently working on a problem where I have to do maze navigation
with obstacles in the maze. I have to implement a TSP algorithm to visit a specific number of locations in the maze in the fastest possible time. I am not quite sure how to start, can anyone give me some help on how should I approach this problem and is there any particular data structures I should use. Thank You very much.
> Hi,
>
> I am currently working on a problem where I have to
> do maze navigation
> with obstacles in the maze. I have to implement a TSP
> algorithm to visit a specific number of locations in
> the maze in the fastest possible time. I am not quite
> sure how to start, can anyone give me some help on
> how should I approach this problem and is there any
> particular data structures I should use. Thank You
> very much.
hi...
i suggest the backtracking method would be the best one for the TSP problem...though there could be other soutions this would be the base.
U could use a tree as the base data structure. If not convinient with trees i suggest that u could do the same with linked lists maintaining a nnode for every location visited.
If the positions are in a maze then the first thing you need to do is compute the real distance between the points. As it is a maze the simplest way of doing this is the "left route first"
Just keep taking the left hand turn at each junction. Remeber where you have been so you don't repeat yourself. Embeding the results in a graph can give you the "maze" distance between the positions you need to go to. Then you can perform a TS algorithm on the graph to compute the fastest method of visiting both.
The problem is that you must have been everywhere in the maze to have the data about how to get between the nodes most efficiently. Bit pointless really.
matfud
Technically, there is a better way to solve the problem but the programming required (and the processing power) is immense. What is the person who is requesting, in other words, are they a stickler? because the guy might be expecting THE BEST way of doing it. BTW, there is the possibility that the person could get stuck in a dead end path with that method
Actually, if the problem involves a traversal in a perfect maze (meaning that the underlying graph is tree structured with a single unique path between any two nodes), the problem is fairly simple and does not require a lot of processing power.
The thing to observe is that any single cell, C, (or graph node) disconnects the graph into subgraphs that can be reached through the doors from that single cell. Those subgraphs ONLY connect through that cell. So if you go pick off the required rooms in one of the subgraphs, you MUST return to C if you want to get to any of the nodes that lie in another subgraph. This is forced by the requirement of a single unique path connecting any two cells.
A single pass throught the maze marking blind alleys (blind in the sense that there are NO required target rooms through those doorways) allows you to enter the maze and sweep all the required elements with a simple recursive algorithm. (or if you don't like recursion, you mark the rooms as you go so that you see where you have been.)
No ordering is necessary other than an standard greedy approach, If you step through a doorway to bag some required nodes down that sub graph, don't return to the room until you have picked up every required room that could be reached from that doorway. i.e. clear an entire subgraph before you retrun.
If you enter the maze through a single entrance and must exit the same way, there are no order requirements. The path length will all be the same.
The only time ordering becomes necessary is if you get to start inside the maze in one required room and get to stop inside the maze at a different required room. In that case, you need to first calculate the diameter of the underlying graph so that you know where to start and stop. (Basically you will be running a closed circuit EXCEPT that you get to cut off the one leg from the stop to the start. To make your traversal short you want that path to be as large as possible, ie. the diameter of the underlying graph.)
That traversal is nearly the same. You can pick off subgraphs from a room in any order as long as you delay entering the subgraph that contains the stop point until last from any room. This means that you must mark doorways first so that you know, which doorways lead to the stop room and always take those doors last.
Given that the OP did not specify what type of maze this is and also did not specify any initial conditions, one can only guess whether or not this algorithm fits the situation. The "right hand on the wall" method works on a perfect maze. Because of the underlying tree structure those mazes are particularly simple beasts.
Furthermore, given that the OP does not appear to have engaged in any further dialog since the initial post, one must assume that the homework assignment is past due and that the moment is gone.