State Space Search Efficiencies

State Space Search

State Space Search gets its name from algorithms used to search for a goal state in a space containing many states. A search begins with a start state and searches for a defined goal state or states. Teaser is an example of a puzzle that can be easily solved using a state space search algorithm. This puzzle consists of a triangular boad containing 15 holes. Each hole may or may not contain a peg. See the description of Teaser.

We will number the holes in Teaser as follows		a typical Teaser start state
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14	=>	1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
Figure 1.1		Figure 1.2

In the puzzle's starting configuration (state) all of the 15 holes but one contain pegs. The puzzle is played by jumping one peg over another into an open hole as one would jump in playing a game of checkers, removing the jumped-over piece. The object of the game is to remove all but one peg with legal moves. For the purpose of this description the words node, state and configuration will be used interchangeably. By making jumps one is able to transform (or move from) one configuration or state to another in search of a goal state (i.e., only one peg ramaining on the board). During the search we generate all of the successor states of a given state by considering each possible move.

This general approach can be employed to solve many problems from finding the fastest route from one city to another to seating guests at a dinner table in a manner consistent with certain retrictions regarding who can sit next to whom.

State Space Search Algorithms

There are several search algorithms that are considered to fall into the category of state-space search. Perhaps the three best known are

depth-first
breadth-first and
best-first

Pure depth-first and breadth-first search are normally employed when all transitions from one state to another cost the same. For example, in the Teaser (peg) puzzle above there is no cost differential in selecting one jump (move) over another.

However, many other problems that can be solved using state-space search do have different costs associated with different moves. For example, if we wish to find the fastest route from from Norfolk, VA to Los Angeles, CA our first possible moves might include travelling from Norfolk to Richmond, VA or travelling from Norfolk to New York, NY. Most likely the cost of travelling from Norfolk to Richmond will be less than the cost of travelling from Norfolk to New York. When different moves may have different costs the best-first method is normally employed.

All three algorithms(depth-first, breadth-first and best-first) are based upon a common algorithm. The algorithms all employ an open list and a closed list.

The open list contains states that we have encountered in our search for the goal state but whose successor states have not yet been generated. The closed list contains states whose successor states have been generated.
Variations in the algorithm come from several sources.

The data structure used for the open list.
The data structure used for the closed list.
Auxilliary data structures employed to speed up the search.
Efficiencies achieved from clever representations of the puzzle.
Efficiencies achieved from characteristics inherent in the particular puzzle being solved.
Heuristics that may steer the search more directly toward a goal.

The Generic State Space Search Algorithm

Place the start state on the open list
While more states remain on the open list
1. Remove the first state, s, from the open list
2. Place s on the closed list
3. If s is a goal then exit with success
4. Generate the successors (children) of s by applying valid moves to s.
5. For each successor, c, of s
  if c is not on the open list or the closed list then add c to the open list
End While

This is the basic algorithm that others are derived from. Potentially every possible state could be examined using state space search. So for puzzles with MANY possble states state space search could continue searching for an unacceptably long length of time.

Optimal Solutions vs A Solution

Basic Depth-First and Breadth-First Search
For puzzles where every move costs the same one should use the basic depth-first or breadth-first search. A depth-first search is most appropriately used where the number of moves to a solution is known. For example Teaser begins with exactly 14 pegs and a solution must end with exactly one peg. Since every move removes one peg a solution to Teaser requires exactly 13 moves. A depth-first search looks at a state, then its child, then its child's child, etc. in searching for a goal. I.e., depth-first tries successive moves; moving down the search tree; one level deeper after each move. Thus we would employ a depth-first search to find a solution to Teaser. In order to implement a depth-first search we simply implement the open list in the generic algorithm as a stack. Adding a state to the open list employs the push operation and removing a state from the open list employs the pop operation. Simply implementing the open list as a stack causes the generic state space search algorithm to perform a depth-first search.

Another common puzzle is sometimes called the 15-puzzle. It consists of 15 tiles and one open space arranged on a 4X4 grid. The tiles are numbered from 1 to 15 and the puzzle is solved by arranging the tiles in order from 1 to 15. The start state is a random permutation of the tiles. Moves are made by sliding a tile into the single open space.

a start state

a goal state

2	5	12	9
3	15		11
13	4	7	10
6	8	14	1

	1	2	3
4	5	6	7
8	9	10	11
12	13	14	15

Figure 2.1

Figure 2.2

Since the number of moves required to produce the solution varies depending upon the start state a breadth-first search is appropriate to solve this puzzle. In a breadth-first search, after a state is examined, all of the successors (children) of that state are examined. Thus, in a breadth-first search we move through the search tree level by level; examining all of the nodes at level i before examining all of the nodes at level i+1. In order to implement a breadth-first search we simply implement the open list in the generic algorithm as a queue. Adding a state to the open list employs the enque operation and removing a state from the open list employs the deque operation. Simply implementing the open list as a queue causes the generic state space search algorithm to perform a breadth-first search.

Efficiencies in Breadth-First and Depth-First Search

State Storage
We can improve the speed of breadth-first and depth-first search by addressing the two traditional limitations - time and space. Data stored in main memory can be accessed much more quickly that data stored on disk. However available main memory storage is typically small compared to available disk storage with the relative factor being typically between 10 and 1000. A clever means of storing a state can mean that a puzzle search can be done entirely in main memory. This can often transform a search implementation from "too slow to find a solution" to "finds a solution". Additionally, compacting state storage often means that a state can be retrieved from memory faster thus further speeding up processing.

Teaser provides a very simple example of efficient storage. Since Teaser has 15 holes, each puzzle state can be represented with 15 bits. A one in the bit position indicates that the hole is occupied by a peg and a 0 indicates that the hole is empty. Since a 16-bit integer is a built-in data type for almost every computer language that data type seems a likely candidate for representing one state. This 2-byte representation while probably reasonably space-efficient is not optimal. In addition to the obvious wasted bit, some 16-bit integers do not correspond to valid puzzle states. For example, it is not possible to have all of the holes empty or all of the holes filled. I do not know the actual number of impossible configurations so I cannot determine how far from optimal this 16-bit implementation is.
Symmetry also provides an opportunity for both efficiency and inefficiency. For example in Teaser there are three states where a single unoccupied hole is located at one of the vertices of the triangle. These three states are equivalent in the sense that one can be transformed into any other by a simple rotation. E.g., the puzzle state with a single hole in the bottom left vertex can be rotated 60 degrees to become the puzzle state with a single hole at the top. Thus any solution for the puzzle that has one of these as a start state yields a symmetric solution to the other two. Reflections also provide a means to identify equivalent states.

State Access

Variations For Different Graph Structures

Trees
Acyclic Digraphs
General Graphs

Searching Weighted Graphs

Top of this page Top of page

Home page