SE250:HTTB:WIP:State-space search:Draft

Introduction to State Space Search

Click here to view an introduction video

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

The best way to illustrate the search pattern is to use animation. <html> <embed src="http://www.geocities.com/giant_stone_soldier/BFS.swf" width=550 height=400/> </html>

Tsen009 20:58, 6 June 2008 (NZST)

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.

twon069 01:44, 4 June 2008 (NZST)

Best First Search

Best first search uses an evaluation function and always chooses the next node to be that with the best score. However, it is exhaustive, in that it should eventually try all possible paths. It uses an agenda as in breadth/depth first search, but instead of taking the first node off the agenda (and generating its successors) it will take the best node off, ie the node with the best score. The successors of the best node will be evaluated (ie have a score assigned to them) and added to the list.

Best-first algorithms are often used for pathfinding in combinatorial search.

A path-finding problem might use the algorithm in this form:

1. Start with OPEN containing just the initial state 2. Until a goal state is found or there is no node left on OPEN do:

 i)Pick the best node on OPEN
 ii)Generate its successors 
 iii)For each successor do:
     a]Pick the best node on OPEN
     b]Generate its successors
     c]For each successor do:
       i)If it has not been generated before: evaluate it, add it to OPEN and record its parent.
       ii)If it has been generated before: change the parent if this new path is better than previous one.

hlin079 03:18, 4 June 2008 (NZST)

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.

Hpan027 20:42, 4 June 2008 (NZST)

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

twon069 00:19, 6 June 2008 (NZST)

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.

twon069 16:54, 7 June 2008 (NZST)

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