SE250:HTTB:WIP:State-space search
Thanks guys. I have placed a kind of the final version in the actual HTTB and tried to organise it as much as possible. Thanks a lot. (note: i have taken the dates and users of within the article and put a list of contributors at the end). All original information is still retained here though. Best wishes and good luck for the exams! --Mabd065 10:28, 8 June 2008 (NZST)
Second draft for the final version --Mabd065 10:19, 8 June 2008 (NZST)
Just a question, will you be checking this page now and update the above page accordingly? or should we post new content onto the above page?, Thanks twon069 15:29, 8 June 2008 (NZST)
I'm guessing we still put stuff here. Screencast added Hpan027 02:49, 9 June 2008 (NZST)
Please put any updates in the final version. I think the final cut off was last Sunday! --Mabd065 14:01, 10 June 2008 (NZST) Making some kind of start.
<html> <img src="http://www.fineupload.com/files/state-space-search.jpg"> </html>
--Mabd065 12:33, 7 June 2008 (NZST) (Part of this image is adapted from http://cnx.org)
Possible things which need covering as mentioned in lectures so far
- Relevance to real life (artificial intelligence was mentioned) <- I reckon this could go on as an intro, eg like 2007HTTB, where they had a main page with a little intro on each topic.
(along with a pic)twon069 23:40, 5 June 2008 (NZST) What states/nodes etc are and how they are representedBreadth first searchDepth first searchUninformed/exhaustive search vs informed/intelligent searchBest first searchBranch and bound/tree pruning etc- Examples using things such as the 8-puzzle,
8-queenthing and burglary example - Questions of some kind (possible exam questions may be?)
Hpan027 15:43, 30 May 2008 (NZST)
Iterative deepening- Stuff done in labs?
Hpan027 20:42, 4 June 2008 (NZST)
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:
<html> <img src="http://img233.imageshack.us/img233/9669/slidestateyo5.png" alt="Initial State" /> </html>
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:
<html>
<img src="http://img207.imageshack.us/img207/3277/slide3statespd8.bmp" alt="3 States" />
</html>
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)
Stuff that might be worth mentioning
Best strategy if goal state is close to starting stateExponential increase in memory usageImplemented using a queue
Hpan027 20:49, 4 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.
<html> <embed src="http://www.geocities.com/giant_stone_soldier/DFS.swf" width=550 height=400/> </html>
<html> <embed src="http://www.geocities.com/giant_stone_soldier/TheStack.swf"/> </html>
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.
(an animation showing such scenario)
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)
Stuff that might be worth mentioning
Low memory usage compared to breadth-first searchImplemented using a stack
Hpan027 20:49, 4 June 2008 (NZST)
twon069 00:30, 6 June 2008 (NZST)
Depth First vs. Breadth First
Summary:
Depth First
pros:
- Memory efficient
cons:
- Can get stuck on the wrong branch if the state space is infinite.
Breadth First
pros:
- Won't get stuck on the wrong branch if the state space is infinite. It will eventually find the answer.
- Usually faster than Depth First.
cons:
- Not as memory efficient as depth first
sbas046 12:30, 14 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)
Screencast added Hpan027 02:59, 9 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. 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.
twon069 00:19, 6 June 2008 (NZST) twon069 15:45, 8 June 2008 (NZST)
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)
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.
//insert screencast here
Uh..I'm not sure why this section was pulled entirely by the original author, but I think this should be mentioned. Hpan027 03:35, 9 June 2008 (NZST)
Oh, it was a copy-paste from some website. I took it off the final version and will try to write something up for this section and/or do a screencast. Although anyone else feel free to do this. Hpan027 03:46, 9 June 2008 (NZST)
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 10:28, 8 June 2008 (NZST) |
| mabd065 | Introduction to State Space Search--Mabd065 10:28, 8 June 2008 (NZST) |
| twon069 | Knapsack problem using Branch and Bound pruning |
| hpan027 | Iterative deepening search |
| hpan027 | Best-first search |