SE250:HTTB:State-space search

Click here to view an introduction screencast

Introduction to States and Nodes

The first step to understanding state space searching is to understand how a searching problem is represented. Like the other topics involving complex structures, the easiest way to represent a set of states is as connected nodes. These connected nodes can be formed into a tree-like structure, and become a graph.

As an example, I will use a simple 3x3 sliding tile puzzle with a picture on it. Each of the tiles is assigned a number, and the empty space is represented by an underscore (_) it is set up as follows:

1	2	3
4	5	6
_	7	8

This will be the initial state of the puzzle, and the node representing the state would look like this:

From this state of the sliding puzzle, there are only tiles you can move into the empty spot. Each of these possible moves represents the next state in the graph, and each is assigned a node. The possible states are as follows:

Moving the "4" tile into the empty slot:

1	2	3
_	5	6
4	7	8

and moving the "7" tile into the empty slot:

1	2	3
4	5	6
7	_	8

To represent this as a graph, each of the states gets their own node, and the 2 new states link back to the initial state, like this:

The graph is undirected, because the tiles can be moved back and forward at will, but other types of state systems may need directed graphs if this isn't the case.

Using this method, the graph continues to grow until it represents every state and state transition possible (ok this is impossible to draw, so just use your imagination)

A graph of every possible state represents the state space of the problem.

State Space Searches

A state space search is a search of the state space for a specific state. This information is the key to solving problems using state representation. For the example of the sliding puzzle above, the state being searched for would be the one which represents the unscrambled image. Once this state has been found, the solution to the puzzle is as easy as following the state transitions from the initial state to the state that was found by the search.

There are several ways of searching a state space for a state, and they vary in complexity and performance time.

Breadth First Search

In breadth first searching, the search algorithm first goes through and looks at all the closest states (1 transition away) and checks them against the state you are looking for (lets call this the goal state). If the goal state is not found within the states 1 transition away, the algorithm moves on to the states that are 2 transitions away, and then continues moving outward until the entire state space has been covered.

This search implementation is more effective the closer the goal state is to the starting state. As such, it is best used in cases where this has a high probability. Before moving to the next level of the tree, each state in that level is added to a queue. Because of the branching out effect of tree structures, this means that as each level of the tree is searched, there is an exponential increase in memory usage. Each level has the possibility to several more nodes (based on the number of possible state transitions) than the previous level.

Depth First Search

In depth first search, the search algorithm goes through one child state at a time, and searching further down this child state until it reaches a state without a child(ie. 1 subtree at a time), where it backtracks to the closest visited-state with an unvisited-child state and continues searching through this state again, or until it reaches the goal state. Hence the tree is processed in a "Last In First Out" manner, where it "chooses the last visited node with an unvisited child". Given the process is like a "Last In First Out" manner, a depth-first search can be implemented like a stack, where visited states are pushed in from the top, and popped out, when backtrack is required.

One of the main advantage of depth-first search over breadth-first search is the low memory consumption it is required as it traverse through the tree, due to it's Big-O for memory requirement being linearly increased, not exponentially, such as a breadth-first search.

The drawback of such algorithm is when traversing through a large tree of states, if the goal state doesn't lie in the deepest subtree, time will be wasted traversing through useless states. However in the worst case scenario, depth first search can end up in an endless search sequence, due to child state linking with other subtree, hence creating a recursive situation.

This is prevented by the openlist and closedlist. The depth first search using these lists will not visit a node in the closedlist, and as such the recursive scenario does not happen.

Best First Search

Best-first search is an example of an informed search strategy which chooses the path that some pre-defined algorithm considers the way to the goal state.

An example of this is using the Manhattan distance to determine the best way to solve an 8-puzzle.

Iterative deepening search

An iterative deepening search is a combination of a depth-first and breath-first search. Depth-first searches are repeated with an increasing depth constraint. This strategy will explore the nodes in a depth-first manner, but upon reaching some specified depth, will backtrack as if a leaf was reached. If the goal state is not found, the depth limit is increased, and the search repeated.

This is only slightly slower than a breadth-first search, with the benefit of using only as much memory as a depth-first search.

See the screencast

Uninformed vs Informed Search

Uninformed search, also known as the brute-force search, is a trivial but generally an "effective" ways to approach a search problem, due to no requirement of prior knowledge to the problem. An uninformed search algorithm will traverse through ALL possible state until it reaches a goal state. For example, 8-queen problem (mentioned below), there are 178,462,987,637,760 possible states, the uninformed search algorithm will then search through 178,462,987,637,760 states, until it reaches the goal state, with no knowledge of useless states such as all 8 queens being placed on the same row. Hence uninformed search are often the last resort of search algorithm to tackle the problem. Example of such search algorithm are Breadth-First Search and Depth-First Search

Informed search, requires prior knowledge of the search problem, and tackles the problem in a more intelligent way. It will search through the state with given knowledge such as, useless states or possible move from the current state which will lead to the goal state quicker. The knowledge is coded in an algorithm called heuristic, meaning an "educated guess" algorithm. Taking the 8-queen example before, an informed search algorithm will skip the useless states, and have the knowledge of illegal placement of queens after say, 1 queen has been placed on the chess board. Hence informed search will often be faster than an uninformed search. However the drawback being the need to process the problem to gain knowledge before the searching could begin, and in term, the heuristic given might lead away from the goal instead of to it. Example of an informed search is Best First Search which adapt using variety of heuristic such as, A* search algorithm.

Informed vs. Uninformed search and the 8-Queens puzzle screecast

Branch and Bound Pruning

Branch-and-bound pruning is a way to search through a tree for an optimized solution without traversing through the whole tree comparing each outcome. This is done by generating states(nodes) of a search tree best-first according to certain evaluation process, the states are then rated accordingly and the state having the highest rating(being the one likely to have an optimized solution) is traversed through first. The process is then repeated for the children states. The subset having lower rating than any of the children states are then pruned away, due to no possibility of containing any states having better solution than the one already found, thus lowering the amount of traversal required.

Knapsack Problem example using Branch and Bound Pruning

List of screencasts

User	Description
gfun006	Depth Best Search in relation to Lab X
gfun006	Breadth Best Search in relation to Lab X
mabd065	Informed vs. Uninformed search and the 8-Queens puzzle
mabd065	Introduction to State Space Search
hpan027	Iterative deepening search
hpan027	Best-first search
twon069	Knapsack problem using Branch and Bound pruning