2008年6月18日 星期三

Method to solve a maze

Is there a sure-fire way to solve a maze? Is it really just luck but no skills and intelligences involved?

I approach this question when I was in sixth year of my Highschool. What give me a hint is the Map theory. In map theory you can always represent the points and edges by accessibility matrix, then by analyzing those matrix, you can deduce the various properties of the map. If two maps has identical accessibility matrix, then they are equivalents.

So I analyze the maze problem from this standpoint. I notice that any maze could be partitioned as layers stacked together from inner to outer, which outermost has the biggest length and the innermost has shortest length. Then in each layer, we see there are walls further partition each layers as independent areas. The goal of solving a mazing could reformulate as how to get from a partition within a layer to another partition in another layer. Then it begin to look like a problem within the domain of knowledge of map theory, since it is again about accessibility from one area to another area. How do we know about accessibility in a maze?

Simple, after we partition the layers of the maze, we can represent each area in each layer as a point in the map. So all the points in the same layer share the same level in the map. What make a maze a maze is the differential accessibility of each partitions to the partitions in the next layer. Thus we can again represent the one step inner layer of maze as another set of points in a map. If a partition A in outer layer could access the partition B in the inner layer, then we draw a line connecting them two. Repeat the process and we will have a map that represent the partitions of layers as point, and the path connecting them as lines. Continue the process until we have all partitions and pathways between them represented.

Now we have a map. Then we can write out the Accessibility matrix just like in Map Theory. Now we can apply the knowledge of the map theory to solve a maze. Usually, the objective of solving a maze is started at one partition in the outermost layer to another partition on the other side of the map in the outermost layer through various pathways. We remember from the map theory that the n-th power of the Accessibility martix denote how many ways we could arrive from a point to another point in n-step without turning back. If there exists a pathway from starting point to exit within n-th step, the value of the entry in column and row of respective partitions would be greater than 1. So what did is just to repeat the multiplication of the Accessibility matrix until we see the value of entry in the desired partitions of layers is greater than zero.
We could reconstruct other mazes from the original by switching the orders of layers without changing the pathways if it is possible(i.e. The relationship between the partitions remain the same), since the innermost layer has smallest number of partitions. However we alter the maze, we just need to alter the columns and rows of the changed layer in the Accessibility matrix. If we have done the multiplication, we only need to alter the columns and rows of the changed layer in the Accessibility matrix.(In other form, to do a linear transformation of the matrix.)
A boarder set of Maze questions is not just about whether there exists a pathway from one particular partition in one layer to another particular partition in another layer. It is given a random partition in a random layer in the maze, can we get to another random partition in another random layer within n-th step?
By using this tool, we can generate maze and test the various parameters of its accessibility, and we can also evolve new maze with the parameter we demanded using evolutionary computing(without the necessity of designing the maze ourselves.) Thus we can play a Pac-Man Game without any repetition of the maze. How boring it is to play with the same maze for over 300 rounds as in old days of Apple?

沒有留言: