|
|
The Labyrinth, and the Monster
Date: 11/14/07
(Algorithms) Keywords: asp
Hello.
Computation is the process of state transition. An algorithm is a permutation of those states in such a way as to produce a correct output. 'Correct' means that what was put in agrees with what came out, and everyone's perceptions of those things.
"The fundamental problem of communication is that of reproducing at one point, either exactly or approximately, a message selected at another point." [Claude Shannon, "A Mathematical Theory of Communication"]
The algorithm is communication. That idea has always meant something to me.
So there's no use wasting words. I have an algorithm.
A while back, I had to solve the common maze-running problem for a course. The instructor gave the usual depth-first and breadth-first search algorithms, but instead of implementing one of those, I spent an extra week or so developing my own algorithm, based on what is, as far as I know, an entirely novel idea.
We have these assumptions: - It is appropriate to represent the maze as a two-dimensional grid;
- Every place on the grid is either blocked (is a wall) or open (is a path);
- Both the starting and the ending point are known;
Suppose you were actually lost in a maze, and that someone else was in there with you. If you were looking for one another, you might call out to them, "Hey, where are you?" and follow the sound of their voice when they answered. The trouble is that there might be a wall in the direction you wanted to go. The most intuitive thing would be to keep moving, tending in the direction of the sound whenever possible, and simply following the wall when you had to.
The basic idea motivating the approach is that knowing the ending point is a very large advantage; it gives some vague notion of what direction to go in. The complicating factor is that the direction of the actual solution path (if there is one) may not agree with the direction of the end to the start "as the crow flies." The challenge, then, becomes one of striking a consensus between the intuitive sense of direction and the actual constraints of the solution path.
Consider: if there is a path between the start and the end of the maze, then, if we iteratively build two lists of every (respective) open space adjacent to the start and (respectively) the end, eventually the two lists will have a common element. This element, represented as an ordered pair of coordinates, lies on the solution path.
Below is a semi-formal, if flawed, pseudo-code implementation from my original program. It should be noted that the original involves a number of redundant operations and, as formulated, is not very efficient. (This is largely because I spent so much time coming up with a correct version of the algorithm that I had to rush the implementation to make the deadline.) Nonetheless, it should cover all the details:
STEP 1: Input maze grid; set UP = {(START_ROW, START_COL)}, DOWN = {(END_ROW, END, COL)}, and ALL = {all open spaces in grid};
STEP 2: while(UP intersection DOWN is empty AND new elements were added to UP or DOWN on the last iteration)
repeat STEP 3 through STEP 5;
STEP 3: DOWN = {all elements located by PingDwn( )} union DOWN;
DOWN = DOWN union {all elements of ALL adjacent to an element of DOWN};
STEP 4: UP = {all elements located by PingUp( )} union UP;
UP = UP union {all elements of ALL adjacent to an element of UP};
STEP 5: ALL = ALL complement (UP union DOWN);
STEP 6: if(the loop exited with no new elements added either to UP or DOWN)
output NO SOLUTION;
EXIT;
else
go to STEP 7;
STEP 7: PATH = {(START_ROW, START_COL), (END_ROW, END_COL)} union (UP intersection DOWN);
STEP 8: while(an element not in PATH could be pinged between any pair of points in PATH)
repeat STEP 9;
STEP 9: for(each pair of elements p1, p2 in PATH)
repeat STEP 3 through STEP 5, subsituting p1 for START and p2 for END;
STEP 10: output maze, description of the solution;
EXIT;
It also serves to more completely describe the "ping" operation; we do so for PingDwn only; the operation for PingUp
is distinct only in that the directions are reversed, and '-' is substituted for '+'.
STEP 1: Input START := (START_ROW, START_COL);
DOWN = {START};
STEP 2: while(elements could be added to DOWN)
repeat STEP 3;
STEP 3: for(each element (i, j) in DOWN)
if((i + 1, j) is CLEAR)
add to DOWN;
if((i, j + 1) is CLEAR)
add to DOWN;
STEP 4: return the list DOWN;
(excerpted from the original documentation
Essentially, the start and the end work together and "meet half-way" to find a solution. Originally, I thought of two waves (as in a sound wave) emitted by both the start and the end and propagating through the maze (in this case as a diagonal in the grid) until they met; the point at which they met would then serve to locate a point on the solution path.
Another interesting aspect of this approach is that the path is built (and correctly), but NOT in order. One failing of the above implementation is that it would be more natural (but again, I was sloppy due to time constraints) to recurse, as:
solve(start, end, PathList){
if(start == end){
return NULL;
}
else{
mid = ping(start, end); /*meet half-way*/
if(NULL == mid){
NO SOLUTION; /*if no common point, no solution*/
goto END;
}
insert(mid, PathList); /*else add mid-way to solution*/
solve(start, mid, PathList);
solve(mid, end, PathList);
}
}
The beauty of this approach is that it forgets the search; every point in the space cooperates to come together. In the old myth, Theseus found his way out of the Labyrinth not on his own, but with the help of Ariadne, on the outside. The cleverness of the labyrthin's engineer couldn't defeat the accord of two people. That's communication.
Source: http://community.livejournal.com/algorithms/94758.html
|