Archive for the Algorithm Category

Algorithm: Find the way in a maze.

Posted in Algorithm on August 4, 2008 by nemosong

My friends had an algorithm project: Finding a way to get out of a maze.

Maze is a 10×10 matrix, and 1 is wall, 0 is a route.
How can a program find the exit?

1. Easy way.
Create a temporary matrix(called array in programming), and record where the program has been.
When it needs to come back to it’s original place, the matrix is used.
Cons: If the matrix is huge, the program doubles its memory size.

2. Smart(efficient) way.
A browse() method visits all possible spots, and if needs to come back, it checks where it shouldn’t check.
For example, if a browse() method detected a way using “DOWN” and create another browse() method, this method cannot detect “UP” but ends there and return to original(parent) browse() method.
Pros: This prevents a browse() method to create a child method for back-tracking.
Uses much less memory space.