As an example, consider the problem of finding our way out of a maze in the fewest number of steps. In this case, a maze might be represented as 1's (a floor on which we can walk) and 0's (a wall that we cannot penetrate, climb over, or go under).
01234567890123 0 00000010000010 1 01111111110010 2 00100010011110 3 01111111110010 4 01010101111100 5 01111111111110 6 01000000000010If we begin at position row 3, column 1, and try to reach an exit in the least number of steps, it is not exactly clear which direction we should go. There are two directions we can try, and, once we start, additional possibilities immediately occur. There are a lot of possible paths!
In situations such as this, we need a simple method of generating all possible paths from the start to the exit, and then we simply choose the shortest. Unfortunately, this may be a very large search space. Imagine a maze in which every position had three new possible positions to move to! The number of paths of length 13 would be 1,594,323. We certainly cannot consider all of these!
Since we are looking for the shortest path, we might want to examine short paths first. Incidentally, there are fewer short paths than long paths, so this might be more efficient than another ordering of the possible paths. It is also comforting to know that if we can reach a location in the maze in n-steps, there is no need to consider any paths that might reach this same location in more than n-steps. Thus we can immediately eliminate a large number of longer paths by employing this method.
The search method we will use is called breadth first search. The search begins by examining small, partial solutions, and then systematically extends each of these possible solutions into larger ones until a solution is found. In this way, the first solution found will always be an optimal one!
We begin the breadth first search by listing all of the cells we can get to in one move: (4,1) and (3,2) (row number, column number)
These are the "end-points" of all possible paths of length 1 from the starting point. From each of these, we list all possible next-cells: (3,1), (5,1), (2,2), or (3,3). We can discard (3,1) since we were there before (it was possible to get there with no moves)! We are left with three possible end-points for paths of length 2. Extending these paths, (and eliminating cells that we already visited) we obtain the list: (6,1), (5,2), (3,4), (1,2). and (4,3).
To program this algorithm, we must keep a list of path end-points still under consideration so we can extend those paths at the next widest search level. A queue provides the necessary structure for this search. The queue will contain a list of all "end-points" still under consideration in our search for the shortest path to an exit.
The algorithm begins with one cell in the queue: the start cell. In addition, we keep track of the length of the shortest path that can reach each new end-point.
Enqueue the start cell with path-length of 0
mark this cell as having been visited.
While queue is not empty and exit not reached..
Remove the next end-point cell from the queue.
Let n represent its path-length.
If this is an exit,
set the exit flag to terminate the loop.
Otherwise,
for each adjacent unvisited, non-wall cell ...
Mark it as having been reached by a path of length n+1
Add it to the queue with path-length n+1
When finished, we can trace our way back to
the start node by following the decreasing path-length marks. This diagram shows
the cells that were marked by the algorithm (not all of the 3's need be marked
as the algorithm stops when an exit is found at (6,1)).
01234567890123 0 1 3 2 2 3 0123 4 1 5 23 6 3
The shortest path (from exit back to start) is (6,1), (5,1), (4,1), (3,1).
Task 1 Examine the files MAZECELL, COORDINATE, and MAZE and answer the following questions:
A Maze is a collection of Maze_cells stored at various Coordinate positions within the Maze. The Maze uses coordinate (0,0) as the top-left or north west corner of the maze. Just below (or south) is (1,0) and just to the right (east) is (0,1). Write a C++ statement that will declare a Coordinate for the cell located 2 steps east and 3 steps south of the top left corner. Name the Coordinate variable home.
_____________________________________
If current is a Coordinate of a cell in a maze, what expression (use a member function) would represent the Coordinate of a cell immediately below (south of) current?
___________________________________________
Complete the following statement that determines whether the Maze_cell at Coordinate current of the Maze M is a floor or a wall cell. Again, use appropriate methods.
cout << (____________________________________) ? "wall" : "floor" << endl;
If the variable foo is declared as Coordinate foo; then describe the input format that is expected for the statement: cin >> foo; //describe the format the user must use to enter the data and give an example
________________________________________________________________________________
_________________________________________________________________________________
How would you store (in the Maze M) the fact that the cell at Coordinate here could be reached from the starting position by a path of length 7? Hint - use a Maze method.
__________________________________________________
Explain what the member function Adjacent() does and what it returns (look at the implementation):
____________________________________________________________________________
____________________________________________________________________________
Why (how) does the following statement work and what will it do? You may need to look in another header file for the complete explanation!
cout << M.Adjacent(here) << endl;
___________________________________________________________________________________
___________________________________________________________________________________
___________________________________________________________________________________
___________________________________________________________________________________
___________________________________________________________________________________
Task 2: The BFS member function of the Maze class is not completed. Use the algorithm in the background information to complete it. Write your solution in BFS.CPP. Compile and test your function. Print the file BFS.CPP when finished.
Task 3: There is an error in the
Queue class. It has to do with a memory leak! Remove the comment characters
from the pre-processor directive //#define CATCHBUG at the top of
the file main file (Amazing.cpp).
This will enable a report of internal accounting of nodes allocated and
deallocated. Run the program to observe the error. Try to find the error,
correct it, and test your correction! Hint -- it is very small and requires
only one additional line of code! Explain the problem here:
Turn in this sheet and the printout of the file BFS.CPP after you have completed the lab. That's it for this lab and for the lab course. Hope you enjoyed the labs. Have a good break.