A-mazing Algorithm

You are here

Share

People have been trying to find their way through mazes since ancient times. Consider the subjects of ancient Athens, forced each year to send seven youths and seven maidens to Minos, the king of Crete, as tribute. These 14 captives were then sent into an exitless maze that housed the youth-and-maiden-eating Minotaur at its center.

Theseus, son of Aegeus, king of Athens, with the help of the besotted Ariadne, daughter of Minos, put an end to the Minotaur and the maze’s notoriety. Just as he was about to enter, Ariadne slipped him a ball of thread. One end of the thread was tied to the maze entrance, and Theseus unwound the ball as he roamed the maze in search of the beast at its center. Of course, he managed to kill the Minotaur and, thanks to Ariadne’s thread, found his way out of the maze in safety.

The first lesson to be learned from this story is: don’t venture into a maze unprepared. If you’ve forgotten to bring a spool of thread from home, be ready to go to some trouble to get out. From ancient times, the best method for finding one’s way through a maze required leaving threads or signposts. Even for a computer, the only other approach that did not require a very large amount of memory was randomness. If every time you came to an intersecting path, you randomly decided (by flipping a coin, for example) which direction to take, you would eventually get to the point in the maze you were aiming for. Enter Dr. Omer Reingold of the Computer Science and Applied Mathematics Department. Reingold recently came up with a method that’s deterministic (not based on randomness) yet economical when it comes to memory use.

Why should a computer scientist care about mazes? Because a maze can be used as a model for a network – of computers, airline flight routes, roads, etc. In fact, the ability to find a path through a maze or network is a fundamental problem lying at the very heart of much of computer science. Many complex calculations contain deeply hidden mazes. Questions asked by computer scientists in this field are: How much time and how much memory are needed to calculate the steps needed to get from point A to point B in a maze or on a road map? The time question was solved decades ago, the memory question only partially. It’s known that the algorithm (a computer’s plan of action) for finding the way based on random turnings consumes a very small amount of memory. All that’s required is to remember the present position of the “captive” in the maze. In comparison, deterministic algorithms have been memory-hungry when it comes to solving mazelike problems.

Recently, Reingold managed to find a solution to this basic quandary, which has engaged many a computer scientist for the last 35 years. Reingold’s algorithm is both deterministic and able to keep memory use down to levels nearly as low as those of the randomness-based algorithms. Armed with the new algorithm, the modern Theseus can enter his maze equipped with an explicit set of navigating instructions -- for example: Turn right at the second intersection, pass three more intersections and turn left, and so on. What’s more, the same series of simple instructions works for every maze and every map.

How does the new algorithm work? Reingold’s method of reducing the memory load is as surprising as it is counterintuitive. His first step is to further complicate the maze, adding new paths and intersections. These are laid out in such a way as to convert the original maze into a type known to computer scientists as an “expander graph.” The algorithm for finding a route through an expander graph is known to be a simple one that uses little memory. Reingold’s technique conserves the basic layout of the original while building the enlarged maze. Thus, from the route that has been plotted through the expanded maze, it is possible to reconstruct the correct trail through the smaller one, again using minimal memory.

Reingold’s work will likely offer computer scientists a new approach to many problems awaiting solution. In particular, it contains vital clues that randomness may not be the only way to spare computer memory. Though randomness is convenient for planning algorithms, Reingold’s innovative work hints at the possibility that for each algorithm that uses randomness, one can find a deterministic one that will carry out the same tasks using a comparably low outlay of memory.

Dr. Omer Reingold’s research is supported by the Center for New Scientists. Dr. Reingold is the incumbent of the Walter and Elise Haas Career Development Chair.