Move the blank down . Move the blank left . We must ensure that we don t move the blank off the board - so sometimes not all four moves are candidates. If we specify a beginning state and a goal state, we can give a state space accounting of the problem-solving process. Four procedures, describing each of the possible moves of the blank, define the arcs in the state space.
Cycles are possible in the state space graph.
The goal description is a particular board configuration. When this is reached, the search terminates and the path from the start to the goal state is the desired series of moves. The Traveling Salesperson Suppose a salesperson must visit 5 cities then return home. We want the shortest path. The path A, D, C, B, E, A, with associated cost of 450 miles, is one possible circuit.