0

I have this layout of a maze that I am having trouble thinking of how to implement a solution for:

MazeToSolve.png

I know there are many resources for maze solving algorithms e.g. http://www.astrolog.org/labyrnth/algrithm.htm but I am not sure which algorithm is best suited for the given maze.

There are three areas labelled “*” which are the locations that MazeSolver needs to go to before being able to exit the maze from the entrance at the top of the map.

I would appreciate pseudo code of solving the maze islands part. I would be looking for a simple solution and optimal time is not really an issue. The thing is even though an overview of the maze is provided beforehand to the solver, it may not be completely accurate at when the maze solver actually does the maze so its a little more complicated than coding it before hand or using an algorithm that uses omniscient view of the maze and needs to "half" human/doable if you get what I mean...

While the robot/robot programmer will be supplied with a map of the mine for each rescue, the map may be out of date due to new mining or due to damage from the event.

For this application the robot is required to first of all locate all the rescue areas and determine if they are occupied. The robot will have to be totally autonomous. When these have been investigated the robot should then do a check of all the passageways for humans.

The robot should also be self-navigating. While a GPS system is a natural choice, in this case it cannot be used due to the thickness of the rock ceiling preventing any GPS signals, therefore you are also required to design a navigation system for the robot. For this end, small hardware alterations, such as additional sensors or deployable radio beacons, may be added to the robot. Please note that at least one of the shelters is located in an “Island”.

Bill Bo
  • 3
  • 3
  • unless you know the precise positions of the "islands" you'll have to brute-force search through the entire graph anyways, so it doesn't matter what algorithm you use. I'd suggest DFS for simplicity –  Oct 31 '15 at 20:58
  • Ok assuming the location of the islands is given, what I mean is that it is possible for some of passages may be blocked. – Bill Bo Oct 31 '15 at 21:08
  • How is the maze given to your program? Describe the input format. – rob mayoff Oct 31 '15 at 21:10
  • Ok ill give some context – Bill Bo Oct 31 '15 at 21:11

2 Answers2

0

Assuming you are not looking for a shortest path to get out of the maze - just any path, create some order for your Islands: island1,island2,...,islandk.

Now, assuming you know how to solve a "regular" maze, you need to find paths from:

start->island1, island1->island2, ...., islandk->end

Some comments:

  • Solving "regular" maze can be done using BFS, or DFS (the later is not optimal though).
  • If you are looking for a more efficient solution, you can use all-to-all shortest path rather than multiple "regular" maze solving.
  • If you are looking for a shortest path, this is a variation of Traveling Salesman Problem. Possible solution is discussed here.
  • If you want to also pass through all passages, you can do it using a DFS that continues until all nodes are discovered. Again, this won't be the shortest such path, but finding the shortest path is going to be NP-Hard.
Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • how would I be able to check all passages with this – Bill Bo Oct 31 '15 at 21:16
  • @BillBo If you need to check all passages, you are going to need to do a DFS, and follow it until all passages are discovered. If you are looking for shortest such solution - that's gonna be a problem, since it is basically a variant of Traveling Salesman. – amit Oct 31 '15 at 21:19
0

This problem is related to the Travelling salesman problem problem, which is NP-Hard, so I wouldn't expect any quick solutions for larger number of islands.

For small number of islands, you can do this: for each 2 islands (including your starting position), compute the shortest path between them. Since you are interested in distances between relatively low fraction of vertices, I recommend using the Dijkstra's algorithm, since it is relatively easy and can be done by hand (for reasonably large graf).

Now you have the shortest distances between all points of interest and it is when you need to find the Hamiltonian optimal path between them. Fortunately, the distances satisfy a metric, so you can have 2-approximation (easy, even by hand) or even 3/2-approximation (not so easy) algorithms, but no polynomial algorithms are known.

For perfect solution with 3 islands you have to check only 6 ways how to visit them (easy), but for 6 islands you can visit them in 720 ways, and for n in n! so good luck with that.

kajacx
  • 12,361
  • 5
  • 43
  • 70