Implementing single-pair shortest path search.1
Apply the graph solver design pattern.
Graph algorithms are typically implemented as separate graph solver classes. This allows the graph solver to maintain its own state (such as
edgeTomaps) without interfering or modifying the graph data. In this assignment, we act as a client of the
AStarGraphAPI to implement the A* search algorithm.
Debug a graph algorithm involving multiple data structures.
A* search relies on maintaining a priority queue and multiple maps to determine which vertex to visit next. Implementing and, moreover, debugging this algorithm gives us experience working with more complex systems that have multiple interacting components, each of which maintain a small slice of information about the overall computational process.
data repositories to get the
astar assignment. After you update the skeleton code, you can right click on the
data/ folder, and then click pull.
Problems to be solved by your AI will be provided in the form a graph. More specifically, they will be given as a class that implements the
AStarGraph interface, which is an API for the single-pair shortest path problem.
The interface has only two methods: one to return a list of all outgoing edges from a given vertex, and another to return the estimated distance between any two vertices. In lecture, this estimate was called a heuristic.
Perhaps surprisingly, this simple interface captures a huge swath of real-world problems, including various puzzles that we’ll explore in this homework, as well as the route navigation directions for HuskyMaps.
Recall that the A* algorithm requires that we start with a priority queue that contains every possible vertex. In practice, this can be difficult to achieve due to the memory limits of real computers. Even a simple problem like the 15 puzzle has trillions of possible configurations—far more than we could ever fit into a regular computer’s memory. (For reference, 1 gigabyte is only 1 billion bytes; you’d need tens of terabytes just to store all these configurations.)
To save memory, we will implement a different version of A* search with one fundamental difference. Instead of starting with all vertices in the priority queue, we’ll start with only the start vertex in the priority queue.
This necessitates that we also change our relaxation operation. In the version from lecture, a successful relaxation operation updated the priority of the target vertex, but never added anything new. Now that the priority queue starts off mostly empty, a successful relaxation must add the target vertex if it is not already in the priority queue.
Explore the A* vs. Memory Optimized A* Demo2.
- In the lecture version, once a vertex was removed from the priority queue, it was gone forever. This meant that each vertex was visited at most one time. In this new version of A*, the algorithm can theoretically revisit the same vertex many times.
Even with this optimization, some A* problems are so hard that they can take billions of years and terabytes of memory to solve. If the algorithm takes longer than some timeout value to find the goal vertex, the algorithm should stop running and report that a solution was unable to be found.
AStarSolver class that implements the
AStarGraph<Vertex> uses a generic type for vertices, the input graph’s vertices may be a reference type. Thus, make sure to use the
equals method whenever you want to compare two vertices for equality.
The result class returns an object of type
SolverOutcome. If you open the
ShortestPathsSolver file, you’ll see that this is a special entity known as an
enum, which is similar to a class. Basically, an
enum is just a type that stores exactly one of several possible constants and has no methods.
If you don’t want to use your
ArrayHeapMinPQ to solve this homework, you may use the provided
TreeMapMinPQ, which also implements
TreeMapMinPQ is slower and more memory-hungry than
ArrayHeapMinPQ, its operations still take O(log N) time, which is good enough for this assignment.
An example solver is given in the
LazySolver class. This solver simply tries the first edge it sees and if that edge doesn’t lead to the solution, it (incorrectly) claims that the puzzle is unsolvable. You might find
LazySolver helpful as a reference. As with other reference code, do not copy and paste code! This is likely only going to make you miserable later when you try to debug something that you didn’t write yourself and don’t understand.
This assignment comes with a fully-featured autograder. However, it will probably be easier to test on your local machine. We’ve provided a number of example programs and puzzles that use the
In these demos, the exact number of states explored may differ a bit depending on how your priority queue breaks ties.
The example from lecture is given in
DemoLectureExampleSolution. This class uses the
WeightedDirectedGraph, which represents a weighted directed graph. Run
DemoLectureExampleSolution to get the following output.
Total states explored in 0.001s: 3 Search was successful. Solution was of length 4, and had total weight 10.0: 0 => 1 => 4 => 6
DemoAlternateExampleSolution file provides the graph from the A* vs. Memory Optimized A* demo above.
In a word ladder puzzle, we try to convert one word in English to another by either changing, adding, or removing individual letters such that every transition results in a valid English word. Suppose we start with the word “horse” and we want to turn it into “nurse”.
Total states explored in 0.874s: 198 Search was successful. Solution was of length 9, and had total weight 8.0: horse->hose->home->come->core->cure->pure->purse->nurse
The 15 puzzle is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870’s. The original version is played on a 4-by-4 grid with 15 square tiles labeled 1 through 15 and a blank square, though there are also 2-by-2 and 4-by-4 variants. The goal of this puzzle is to rearrange the tiles so that they are in order using as few moves as possible. The player is permitted to slide tiles horizontally or vertically into the blank square.
As an example of a solution, the following shows a sequence of legal moves from an initial board (left) to the goal board (right) on the 3-by-3 version.
1 3 1 3 1 2 3 1 2 3 1 2 3 4 2 5 => 4 2 5 => 4 5 => 4 5 => 4 5 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 initial 1 left 2 up 5 left goal
This is also just a graph, where each possible state of the board has up to 4 neighbors corresponding to sliding the left, top, right, or bottom neighbor of the blank into the blank. As with word ladders, every edge has weight equal to 1.
Commit and push your changes to GitLab before submitting your homework to Gradescope.
Josh Hug. 2019. A* vs. Memory Optimized Demo. In CS 61B: Data Structures, Spring 2019. https://docs.google.com/presentation/d/1YFwTj_GPKueSarYeMa75qJHc8hfn894kxY-4WI7d5U4/edit ↩