Many scheduling, optimization, and game-playing problems require that a program calculate a shortest or least expensive ``path'' through a ``maze'' of possible choices.
For this assignment, you are asked to write a program that calculates a least-expensive path from the entry point to the exit point of an N-by-N maze. (N is of course a positive integer.) The maze looks like a chessboard, where the entry point is the board's upper left corner, and the exit point is the lower right corner. You must move a marker from the entry point to the exit, one square at a time. The marker can be moved horizontally (left or right) and vertically (up and down) but not diagonally.
The complication is that each square is labelled with a nonnegative integer cost or ``toll,'' and you must calculate a path from entry to exit whose total cost is least of all paths.
Here is an example maze, depicted as a 3-by-3 grid, where the entry point is square 0,0, and the exit is 2,2:
0 1 2
+-----------+
0 | 1 | 3 | 5 |
+-----------+
1 | 2 | 4 | 0 |
+-----------+
2 | 1 |18 | 2 |
+-----------+
An exhaustive examination of all paths from 0,0 to 2,2
reveals that the path,
0,0 1,0 1,1 1,2 2,2 has a cost of 9, which is least of
all paths.
A famous result in algorithm theory states that there is no ``efficient'' algorithm to find the best solution, and the only known algorithms execute in order of time exponential to the size of the maze. (If the maze has M possible spaces, the total number of examinations of spaces needed to find the shortest path through the maze will be of the order of 2M.)
The program begins by presenting this dialog to its user:
+------------------------------+ | Type filename of maze: | | +--------------------------+ | | | | | | +--------------------------+ | | OK CANCEL | +------------------------------+The user types the name of a sequential file that holds the maze to be searched. The format of the maze goes like this: The first line of the file gives the size of the grid, and the lines that follow give the nonnegative integers, separated by blanks, for the squares in each row of the grid. For example, the 3-by-3 maze depicted earlier would be coded in the input file like this:
3 1 3 5 2 4 0 1 18 2
The program reads the file, saves the information, and calculates a least-cost path. It prints the answer in a command window:
For maze: 1 3 5 2 4 0 1 18 2 a least-cost path is: 0,0 1,0 1,1 1,2 2,2 Cost = 9If a maze has multiple paths, each having least cost, the program need print only one of them.
Since the maze is a grid of squares, each of which holds a nonnegative integer, we might as well implement the pictured maze as an int[][] array that holds the costs in its cells.
The program must calculate paths through the maze, so what is a ``path''? For this problem, a path is a noncyclic sequence of squares. (Why noncyclic? There are two reasons---think about it.) This suggests that we must use a class Square and a class Path to model the paths.
A Square is characterized by its x,y-coordinates and its associated cost; for example, the middle square of the 3-by-3 maze shown earlier is this form of object:
Square +-------- | x == 1 | y == 1 | cost == 4A Path object holds a sequence of Squares. For example, here is a partial path from the entry to the middle of the 3-by-3 maze:
Path +---------------------------------------------- | +-----------------------------------------+ | | Square | Square | Square | | | +-------- | +-------- | +-------- | | | | x == 0 | | x == 1 | | x == 1 | | | | y == 0 | | y == 0 | | y == 1 | | | | cost == 1 | | cost == 2 | | cost == 4 | | +-----------------------------------------+
Now that we have modelled Square and Path objects, we solve the maze traversal problem in the same way we generate permutations of a set of letters---we use a stack structure that holds partially completed Paths. Here is the standard permutation-generating algorithm, reworded for searching the maze, using a stack:
1. Read and save input maze.
2. Construct a Path containing only the entry square, 0,0. Push this Path.
3. Enter a while loop, which loops as long as the stack is nonempty:
Pop a Path, call it ``Current'';
Has Current reached the exit?
If yes, get Current's total cost to see if it should be saved as the best,
least-cost path found so far.
If no, then get Current's end square and calculate
all the adjacent squares that might be added to Current.
For each square that is a legal next move and also not already
in Current,
construct a new Path that is Current extended by the next move,
and push the new Path.
4. (The while loop has finished, so) print the least-cost Path.
This algorithm is your program's controller.
Here is the specification of class Square:
| Constructor Summary | |
Square(int x_val,
int y_val,
int c)
Square constructs the square |
|
| Method Summary | |
int |
cost()
cost returns the square's cost |
boolean |
equals(Square s)
equals compares this square to another, s, to see if they represent the same position in the maze. |
java.lang.String |
toString()
toString constructs and returns a string that shows the square's x,y-coordinates |
int |
x()
x returns the square's x-value |
int |
y()
y returns the square's y-value |
and here is the specification of class Path:
| Constructor Summary | |
Path()
Constructor Path constructs a path with nothing in it |
|
| Method Summary | |
boolean |
alreadyContains
(Square s)
alreadyContains checks to see if a Square is already contained in this path |
Path |
extendedBy(Square next)
extendedBy constructs a new Path that looks just like this one except that the new Path is extended by one more square |
Square |
lastSquare()
lastSquare returns the last, end square in this path |
java.lang.String |
toString()
toString constructs a string that depicts the sequence of squares contained in this path. |
int |
totalCost()
totalCost returns the total cost in taking this path |
As a gift, the codings of these two classes are given to you. You can find them in package PathTools at http://www.cis.ksu.edu/~schmidt/300s05/Assign/Assn4. Both class Square and class Path contain toString methods that compute printable representations of their objects; use these for testing, debugging, and printing the final answer.
For testing purposes, use your IDE's debugger to monitor the path objects that are pushed and popped from the stack. If you don't use a debugger, then insert System.out.println statements that print the paths that are pushed and popped from the stack, so that you can monitor how the search is working. Start your testing with small mazes, e.g., 1-by-1 and 2-by-2. After you have convinced yourself that your algorithm is operating correctly, comment out the println statements before you submit your program for grading.
It is simplest to place your input file in the same folder that also holds your program's packages.
Create Assign4.jar and submit at http://www.cis.ksu.edu/~schmidt/300s05/Assign/submit.html.