CSCI 151 - Lab 13
Heap Maze Search
In this lab, we will implement a Heap for performing an intelligent search of a maze.
- Download the skeleton for this project.
- Unpack the code into a new Eclipse Java project.
It is possible to do more than just find a solution trail in a maze. We now wish to
find the minimum length path from the explorer to the goal state. While the Stack
interface would be optimal in space, it was not guaranteed to find the minimum length
trail. The Queue interface performed better, but at the expense of remembering
all possible trails at a given level.
With a Heap that implements a Priority Queue, we can balance both space and time in our
search. In this lab, we will implement this Heap, organized to always have the minimum
element available in constant time. If we assign priority in a certain way,
we will be implementing A*
Search, a classic pathfinding algorithm.
Step 1 - TrailEstimator
Our first step is to create the heuristic function for comparing trails. We are
familiar with using a
compareTo method in sorting algorithms, but
a Trail cannot be properly compared to another trail without the context of a puzzle.
Java lets us compare in another way for this circumstance. In the
TrailEstimator class, you will find two methods. This class is a
Comparator for the Trail objects, which will have the proper Puzzle object available.
estimateFor method should return the length of the given Trail, plus
an estimate for the remaining length of the trail. This estimate should be calculated
manhattanDistanceTo method of the Position class.
compare method will then be able to compare two Trail objects, using
using the estimate for each Trail calculated in the above method. Return -1 if the
first Trail estimate is less than the second, 0 if they are equal, and 1 if the first
Trail estimate is greater than the second.
Step 2 - peek and add
With a Comparator object, we can proceed with implementing the Heap. This Heap will
be implementing the Searcher interface. In particular,
we will be implementing a Heap where the minimum node will be the root of the Heap.
Our implementation will use an ArrayList to store all the elements of our Heap.
The first method to implement is
peek. This should return the
root element, which will always be stored in the first position of the ArrayList.
Second, you should implement the
add method. New elements are added to the
end of the ArrayList, and then filtered up repeatedly when the element is found
to be less than its parent. Use the Comparator object to calculate
if an element is greater or less than another element. Based on the structure of the Heap,
you should be able to
calculate the index of the parent for any node using a few mathematical operations.
Step 3 - remove
Elements can be removed from the heap through a similar filtering process. First, save a
copy of the first element of the list. Next, move the element that is last
up to the first position. This could cause a violation of the Heap property
that all parents must be smaller than their children. If the element is less
than only one of its children, swap these two elements. If the element is
less than both of its children, swap the smaller of the two children with the element,
so that we don't break the Heap property any further. Finally, when a swap was
made, repeatedly check the subsequent descendents to guarantee that the Heap
property is always preserved.
Step 4 - isHeap
Finally, you will write a method to check that all of the properties of a Heap are
present. Namely, you must verify that each element is smaller than its children elements.
Because of our use of an ArrayList to track the elements, we will always assume that
the elements form a Heap that is as compact as possible.
Step 5 - Evaluation
Compare the new Heap Searcher to the earlier Stack and Queue implementations.
Create 10 random mazes of size 50x50. For each maze, use the new Shotgun button
to remove some of the walls. Now, for each maze and strategy (Stack, Queue, and Heap),
record the number of visited nodes as a percentage of the total number of open spaces
in the initial maze. Discuss the differences you see between the Stack, Queue, and Heap.
What to Hand In
Submit your TrailEstimator.java and MinHeap.java implementations on Moodle, along with your evaluation
- To earn a D, finish Step 1.
- To earn a C, finish the above and Step 2.
- To earn a B, finish the above and Step 3.
- To earn a A, finish the above and Step 4.
- To earn a 100, finish the above and Step 5.
© Mark Goadrich, Hendrix College