Author: Chris Wyatt
| Assigned: | 11/27 |
| Due: | 12/11 by 11:59 pm |
| Starter Code: | P5.zip |
In this assignment you will implement one of two data structures that enable a state-space search algorithm called A* (pronounced A-star) that is applied to solve a simple sliding-tile puzzle. The algorithm and puzzle solving code are provided, you only have to implement and test the data structure.
Sliding-tile puzzles are classical problems in state-space search. We will be considering the eight-tile puzzle. It consists of an 3x3 board of eight tiles labeled A-H and a single blank (missing) tile. This is called the state of the puzzle. A tile may slide into the blank position vertically or horizontally giving rise to other states. The goal of the puzzle is to find the tile moves need to reach a particular goal state. For example consider the following puzzle state
ABC
DEF
GHThere are two possible states resulting from sliding H right into the blank space, or sliding F down into the blank space.
ABC ABC
DEF DE
G H GHFThe state space search proceeds by searching through moves until a goal state is reached. This is similar to the maze problem from P4 but the number of possible board states is much larger. Thus we need a more efficient search algorithm that can use additional information, called a heuristic. The optimal algorithm (using the same information) is called A*.
Like the beadth-first search from P4 the A* algorithm can be described generically using a type State and operations on a problem instance:
problem.initial() returns the initial state of the problemproblem.goal(state) returns true if state is the goal state, else falseproblem.actions(state) returns a list of states resulting from possible transitions from stateWe only need add two additional variables, traditionally called the path-cost and f-cost. The path cost, g, is the number of state-transitions from the initial state to the current state. The f-cost is the path-cost plus a state-dependent value called the heuristic, h, that estimates how far from the goal state the current state is; that is f = g+h.
function astar_search(problem) returns a solution or failure
s = problem.initial()
if problem.goal(s) return s
frontier is a min priority queue with s as the initial element
explores is an empty set
while true
if frontier is empty return failure
s = pop next state from frontier
add s to explored
for each state s' in problem.actions(s) do
if s' not in explored or frontier then
if problem.goal(s') then return s'
insert s' into the frontier
else if s' is in the frontier with a higher path-cost
replace the state in the frontier with the current s'The supporting data structures for A* are a priority queue modified to allow for inclusion tests and replacement, and a set. Unlike in P4 it is infeasible to implement the inclusion tests using a simple test array because again, the number of states in general is very large.
We can apply this algorithm to our puzzle solver easily. The puzzle state is simply a given arrangment of tiles. State transitions (actions) are determined by the location of the blank slot. We will simplify things somewhat by only keeping track of the path-cost rather than the actual sequence of moves.
An implementation of the A* algorithm is provided in the module PuzzleSolver (puzzle_solver.hpp and puzzle_solver.cpp) using the State module (the template in state.hpp and state.tpp). The puzzle board and supporting functionality is provided in the Puzzle module (puzzle.hpp and puzzle.cpp).
The algorithm requires implementations of the data structures frontier_queue and explored_set. The explored_set in the provided code uses unordered_set, the hash-table implementation in the standard library. Since the frontier is not a normal priority queue, this is the data structure you will be implementing. The API of this module is defined in frontier_queue.hpp and described below.
There is a set of tests for the puzzle solver in test_solver.cpp. When your frontier queue is implemented properly, these tests should pass. Each test takes two strings in the form "012345678", where 0 = A, 1 = B, ... 7 = H, and 8 = BLANK and converts them to Puzzle instances. It then checks the solution path-cost from one puzzle to another is the correct one, including the symmetric case (swap intial and goal puzzle).
The frontier queue template should be implemented in frontier_queue.hpp and frontier_queue.tpp as a min heap using dynamic allocation as necessary and have the following complexity for each member (see the header file comments for details):
Note: You may use any combination of containers or algorithms from the C++11 standard library to implement the frontier queue. You will need to read and understand most of the code provided to you.
You should implement tests for your frontier_queue data module in the catch-based test test_frontier_queue.cpp. The CMakeLists.txt in the starter code is setup to run the provided puzzle solver tests as well as your test.
You can use the grader to check your tests compile, run, and pass as well as check your frontier_queue enables the puzzle solver to pass its tests, by uploadieg the files: frontier_queue.hpp, frontier_queue.tpp, and test_frontier_queue.cpp. There is a build target called "submission" configured by default to create this file with the correct contents in your build directory.
Once you are satisfied your code satisfies the project specification, upload the zip file containing your submission, through Canvas at the assignment link). The list of files to include is: frontier_queue.hpp, frontier_queue.tpp, and test_frontier_queue.cpp. Again, the build target called "submission" is configured by default to create this file with the correct contents in your build directory.
You should not submit the other files from the starter code, nor your build directory.
There are 70 points allocated to this assignment.
The design portions of the grade will be assessed by the TA using the following criteria: