A* Search

Implementing single-pair shortest path search.¹

Learning Goals

• 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 distTo and edgeTo maps) without interfering or modifying the graph data. In this assignment, we act as a client of the graph data type by using the AStarGraph API to solve any problem that can be reduced to A* search.

• 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.

Table of contents

1. Getting Started
2. AStarGraph
3. Memory-Optimizing A* Search
4. AStarSolver
5. Testing
6. Submission

Getting Started

Pull the skeleton and 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.

Before you begin the assignment, you might find these resources helpful in addition to the lecture slides. Make sure to properly cite any third-party code if you end up incorporating them into your submission:

• A* Insertion Demo Slides
• A* Pseudocode from Section
• Josh Hug’s Shortest Paths lecture recording
• Pathfinding Algorithms Visual Comparison (build a complex maze and compare Dijkstra vs A*!)

AStarGraph

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.

Memory-Optimizing A* Search

Recall that the A* algorithm requires that we start with a priority queue that contains every possible vertex. In practice, this seemingly innocuous requirement can be difficult to achieve due to the memory limits of real computers. For even a simple problem, like the 15 puzzle, there are 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* Demo².

Note

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

Implement an AStarSolver class that implements the ShortestPathsSolver interface.

Tips

Since 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 ExtrinsicMinPQ. While 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.

Testing

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 ShortestPathSolver interface.

In these demos, the exact number of states explored may differ a bit depending on how your priority queue breaks ties.

example

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

The DemoAlternateExampleSolution file provides the graph from the A* vs. Memory Optimized A* demo above.

wordladderpuzzle

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

slidingpuzzle

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.

Submission

Commit and push your changes to GitLab before submitting your homework to Gradescope.