State space Search
3.1.3  State space representation of problem
Representing
Xs and Os
as statespace problem.
Image courtesy of
Ralph Morelli.
See
Luger Fig II.5
State space representation of problem:

All the states the system can be in are represented as nodes of a graph.

An action that can change the system
from one state to another (e.g. a move in a game)
is represented by a link from one node to another.

Links may be unidirectional (e.g. Xs and Os, chess, can't go back)
or bidirectional (e.g. geographic move).

Search for a solution.

A solution might be:
 Any path from start state to goal state.
 The best (e.g. lowest cost)
path from start state to goal state
(e.g. Travelling salesman problem).

It may be possible to reach the same state through many different paths
(obviously true in Xs and Os).

There may be loops in the graph (can go round in circle).
No loops in Xs and Os.
 Xs and Os
 Directed acyclic graph
 Unidirectional. No loops. Multiple paths to the same state.
 Multiple goal states.
 Gametree complexity
 9 first moves, 8 replies, 7 replies, ...
 9! (9 factorial)
= 362,880
different paths.
 In fact, 9! is an upper bound
 many of these games will terminate with a win before reaching end of path.
 Number of paths < 9!
 Unlike chess, could do exhaustive search.
 Statespace complexity
 How many unique states exist?
 Could have blank, X or O in each of 9 squares.
 That is 3^{9} = 19,683 different states.
 In fact, this is an upper bound
 many of these states don't exist.
e.g. 9 X's.
 These states don't exist:
 (Number of Xs)  (Number of Os) = 2 or more
 (Number of Os)  (Number of Xs) = 2 or more
 Q. Is this a complete list of nonexistent states?
Travelling salesman problem
Travelling salesman problem
Travelling salesman problem.
Start at A, visit all cities, return to A.
Links show cost of each trip (distance, money).
Find trip with minimum cost.
Solution is a path.
e.g. [A,D,C,B,E,A]
Image courtesy of
Ralph Morelli.
See
Luger Fig 3.9
Q. What is the shortest path?
Representing
Travelling salesman problem as statespace problem.
Image courtesy of
Ralph Morelli.
See
Luger Fig 3.10.
Start at A, 4 choices for first step, 3 choices for next, 2 choices, 1 choice.
4! paths =
24 paths
Q. What assumption did we make?
Q. When do we stop the search?

In general, how many paths are there?

Given n cities, (n1) choices for 1st stop, (n2) choices for next stop, etc.
Q. What assumption did we make?
(n1)! paths
With many cities or nodes this soon becomes intractable.
Restrict search / Problemspecific heuristics
Reduce statespace
Branch and bound
 Keep track of best path so far.
This is a
bound on future candidates.
As soon as best possible extension to a
partiallyconstructed path (the
branch)
exceeds bound,
that partial path and all its extensions are removed.
Reduces space but still exponential
(const)
^{n}
number of paths.
With large state spaces (e.g. 50 cities)
need to use heuristic.
e.g. Nearest neighbour: "Go to the nearest unvisited city."
Finds solution quick! (Only tries one path!)
Luger changes his numbers to show
example of "Nearest neighbour" heuristic failing on
Travelling salesman problem:
Image courtesy of
Ralph Morelli.
See
Luger Fig 3.11
3.2  Searching a statespace graph
Backtracking
 exhaustive search,
try each path in order, until find goal.
The following shows the "Depthfirst search" version of exhaustive search.
Start at A. Search state space systematically until find goal.
When multiple children, go down 1st child.
If fails, back to parent, down 2nd child, and so on.
Note there are multiple paths to F.
If F has already been found to be a deadend when we went there from B,
the algorithm should not go there a second time (from C).
Image courtesy of
Ralph Morelli.
See
Luger Fig 3.14
Algorithm:
Definitions used in algorithm below:

SL  state list  states in current path
 path keeps changing  states added/removed as we go
 until get path that ends in goal.
 NSL  new state list  nodes whose existence we have become aware of,
but have not visited yet.
 DE  dead ends  nodes proven not to lead to goal.
 CS  current state.
Algorithm:
function newchildren ( state )
{
returns not all the children of state,
but the new ones to look at
i.e. those not on DE, SL or NSL
}
SL := [Start] // CS is part of the chain
NSL := [Start]
DE := []
CS := Start
while NSL not empty do
{
if CS = goal
return SL
else if newchildren(CS) not empty
{
place newchildren(CS) on NSL
CS := first element of NSL // move down to new state
add CS to SL // CS is part of the chain
}
else // newchildren(CS) empty, so backtrack
{
while (SL not empty) and (CS == first element of SL)
{
add CS to DE
remove first element of SL
remove first element of NSL
CS := first element of NSL
}
add CS to SL
}
}

Trace:
First we work down the tree:
AFTER CS SL NSL DE
ITERATION
0 A [A] [A] []
1 B [B A] [B C D A] []
2 E [E B A] [E F B C D A] []
3 H [H E B A] [H I E F B C D A] []
Now the first backtrack:
H has no new children.
H will have been last link on SL, and last state added to NSL,
if we use
LIFO (stack)
structure.
So while
[H E B A] not empty and H is first element,
back up to parent, SL =
[E B A],
NSL =
[I E F B C D A]
then go down:
SL =
[I E B A]
4 I [I E B A] [I E F B C D A] [H]
Now I is dead and
so is parent E
I goes to DE, SL =
[E B A], NSL =
[E F B C D A], CS = E
CS is still first element of SL, so loop
again
E goes to DE, SL =
[B A], NSL =
[F B C D A], CS = F, loop exits
5 F [F B A] [F B C D A] [E I H]
6 J [J F B A] [J F B C D A] [E I H]
7 C [C A] [C D A] [B F J E I H]
Here we only add G to NSL, since F is already in DE:
8 G [G C A] [G C D A] [B F J E I H]
Features:
 DE stops it examining states that are known completely already.
 Only goes to new states (not in SL path), so can't loop.
3.2.3  Depthfirst search, Breadthfirst search
Image courtesy of
Ralph Morelli.
Depthfirst search
(e.g. Backtrack above)
examines the nodes in the order:
A, B, E, K, S, L, T, F, M, C, G, N, H, O, P, U, D, I, Q, J, R
Breadthfirst search
does each level first before moving lower,
examines the nodes in the order:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U
Definitions:
 OPEN  states known to exist but not yet examined
 CLOSED  states examined
Algorithm:
function newchildren ( state )
{
return children of state that are not already on OPEN or CLOSED
}
OPEN := [Start]
CLOSED := []
while OPEN not empty
{
remove LHS state from OPEN, call it X
if X is goal
return success
else
{
put X on CLOSED
put newchildren(X) on RHS of OPEN
}
}

Trace:
AFTER OPEN CLOSED
ITERATION
0 [A] []
1 [B C D] [A]
2 [C D E F] [B A]
3 [D E F G H] [C B A]
4 [E F G H I J] [D C B A]
5 [F G H I J K L] [E D C B A]
6 [G H I J K L M] [F E D C B A]
7 [H I J K L M N] [G F E D C B A]
...
 OPEN is FIFO

When finds goal, there is no record of how it got there.
To save that, might store (state, parent) pairs on OPEN and CLOSED.
Breadthfirst v. Depthfirst
 Breadthfirst is guaranteed to find the (joint) shortest path to the goal.
Whereas Depthfirst might find a goal deep in the structure,
yet not realise that a different choice at the start could have led straight there.
 If path length matters, Depthfirst could keep going
after finding goal
and find multiple paths, compare lengths.
 Problem with Depthfirst is tree might grow forever (or at least exponentially).
Often, Depthfirst is given a depth bound of n levels
after which it will backtrack.
 Problem with Breadthfirst is if there is a high
Branching factor,
OPEN grows very big.
e.g. Every node has B children.
Down at level n, there will be B^{n} nodes.
When Breadthfirst gets down to level n,
all of these will be added to OPEN before it examines the first one
(see trace, step 4 above).

Breadthfirst good if goal is fairly small number of steps away.
Not good if goal is large number of steps away with high branching factor.
 e.g. Breadthfirst not possible in Chess.
 Depthfirst memory cost much lower
 does not have to keep all nodes across a given level on open list.
 Depthfirst good if path to goal will be long.
Won't waste time searching shallow states.
Gets deep into state space quickly.
But may miss optimal path.
Iterative deepening depthfirst search
Depthfirst with bound of 1 level.
If goal not found, depthfirst with bound of 2.
If goal not found, depthfirst with bound of 3.
...
Guaranteed to find shortest path.
Image above.

Depthfirst search (problem  path down might never end)
A, B, E, K, S, (backtrack to E), L, T, (backtrack to B), F, M, ...

Breadthfirst search (problem  has to hold exponentially growing number of cousins in memory)
A, B, C, D, (recover B from memory), E, F, (recover C), G, H, (recover D), I, J, (recover E), K, L, ...

Iterative deepening depthfirst search (low memory, limited path length)
A, B, C, D
A, B, E, (backtrack to B), F, (backtrack to A), C, G, (backtrack to C), H, (backtrack to A), D, I, (backtrack to D), J
A, B, E, K, (backtrack), L, (backtrack), ...
...
Uninformed search
These are all
Uninformed search
algorithms.
Generic algorithms for any search problem.
No problemspecific information.
No problemspecific heuristic to guide/restrict search.