Problem Solving as
State Space Search
State space search
• It is a process used in the field of computer
science, including artificial intelligence (AI),
in which states of an instance are considered,
with the goal of finding a goal state with a
desired property.
1
Outline
• Problem Formulation
– Problem solving as state space search
• Mathematical Model
– Graphs and search trees
• Reasoning Algorithms
– Depth and breadth-first search
Astronaut
Can the astronaut get its supplies Goose
safely across the canal? Grain
Fox
River
• Astronaut + 1 item
allowed in the boat.
• Goose alone eats Grain
• Fox alone eats Goose
2
Problem Solving as State Space Search
• Formulate Goal
• Astronaut, Fox, Goose & Grain across river
• Formulate Problem
– States
• Location of Astronaut, Fox, Goose & Grain
at top or bottom river bank
– Operators
• Astronaut drives boat along 1 or 0 items
to other bank.
• Generate Solution
– Sequence of Operators (or States)
• Move(goose,astronaut), Move(astronaut), . . .
Goose
Grain
Astronaut
Fox
Astronaut
Goose Grain
Grain Fox
Fox
Astronaut Astronaut
Goose Goose
Grain
Fox
Goose
Grain Goose
Fox Fox
Astronaut Astronaut
Grain
3
Astronaut
Goose Grain Goose Astronaut Astronaut
Grain Grain Fox
Astronaut Astronaut Goose Goose
Fox Goose Fox Grain Grain
Fox Fox
Astronaut Astronaut Astronaut
Goose Grain Grain Goose Goose
Grain Fox Fox
Fox
Astronaut Astronaut
Goose Goose Astronaut Grain Goose
Fox Fox Grain
Grain Fox
Astronaut
Goose Fox Goose
Grain Goose Astronaut
Fox Fox Grain
Fox
Astronaut Astronaut Astronaut Goose
Grain Goose Grain Fox
Grain
Astronaut
Goose Grain Goose Astronaut Astronaut
Grain Grain Fox
Astronaut Astronaut Goose Goose
Fox Goose Fox Grain Grain
Fox Fox
Astronaut Astronaut Astronaut
Goose Grain Grain Goose Goose
Grain Fox Fox
Fox
Astronaut Astronaut
Goose Goose Astronaut Grain Goose
Fox Fox Grain
Grain Fox
Astronaut
Goose Fox Goose
Grain Goose Astronaut
Fox Fox Grain
Fox
Astronaut Astronaut Astronaut Goose
Grain Goose Grain Fox
Grain
4
Example: 8-Puzzle
5 4 1 2 3
6 1 8 8 4
7 3 2 7 6 5
Start Goal
• States: integer location for each tile AND …
• Operators: move empty square up, down, left, right
• Goal Test: goal state as given
Classes of Search
Blind Depth-First Systematic exploration of whole tree
(uninformed) Breadth-First until the goal is found.
Iterative-Deepening
Heuristic Hill-Climbing Uses heuristic measure of goodness
(informed) Best-First of a node,e.g. estimated distance to goal.
Beam
Optimal Branch&Bound Uses path “length” measure. Finds
(informed) A* “shortest” path. A* also uses heuristic
5
Graph DS
What is a graph?
• A data structure that consists of a set of nodes
(vertices) and a set of edges that relate the nodes
to each other
• The set of edges describes relationships among the
vertices
6
Graphs
• A graph G = (V, E)
– V = set of vertices
– E = set of edges = subset of V V
– Thus |E| = O(|V|2)
Graph Variations
• Variations:
– A connected graph has a path from every
vertex to every other
– In an undirected graph:
• Edge (u,v) = edge (v,u)
• No self-loops
– In a directed graph:
• Edge (u,v) goes from vertex u to vertex v, notated
uv
7
Graph Variations
• More variations:
– A weighted graph associates weights with
either the edges or the vertices
• E.g., a road map: edges might be weighted w/
distance
– A multigraph allows multiple edges between
the same vertices
Graphs
• We will typically express running times in
terms of |E| and |V|
– If |E| |V|2 the graph is dense
– If |E| |V| the graph is sparse
• If you know you are dealing with dense or
sparse graphs, different data structures may
make sense
8
Representing Graphs
• Assume V = {1, 2, …, n}
• An adjacency matrix represents the graph as
a n x n matrix A:
– A[i, j] = 1 if edge (i, j) E (or weight of
edge)
= 0 if edge (i, j) E
Graphs: Adjacency Matrix
• Example: A 1 2 3 4
1
a 1
2 d
4 2
3
b c
??
3 4
9
Graphs: Adjacency Matrix
• The adjacency matrix is a dense
representation
– Usually too much storage for large graphs
– But can be very efficient for small graphs
• Most large graphs are sparse
– For this reason the adjacency list is often a
more appropriate respresentation
Graphs: Adjacency List
• Adjacency list: for each vertex v V, store
a list of vertices adjacent to v
1
• Example:
– Adj[1] = {2,3}
– Adj[2] = {3}
2 4
– Adj[3] = {}
– Adj[4] = {3} 3
• Variation: can also keep
a list of edges coming into vertex
10
A Graph
Bos
SFO Airline Routes
Wash DC
LA Dallas
A Graph G is represented as a pair <V,E>, where:
• V is a set of vertices {v1 …} < {Bos, SFO, LA, Dallas, Wash DC}
• E is a set of (directed) edges {e1, …} {<SFO, Bos>,
<SFO, LA>
An edge is a pair <v1, v2> of vertices, where <LA, Dallas>
• v2 is the head of the edge, <Dallas, Wash DC>
•and v1 is the tail of the edge . . .} >
A Solution is a State Sequence:
Problem Solving Searches Paths
S
C
A
G
A D
D start
S C
end
A path is a sequence of edges (or vertices)
<S, A, D, C>
Simple path has no repeated vertices.
For a cycle, start = end.
11
A Solution is a State Sequence:
Problem Solving Searches Paths
S
C
A
G
A D
D
S C G
Represent searched paths using a tree.
A Solution is a State Sequence:
Problem Solving Searches Paths
S
C
A B
G
A D C D G
D
S C G C G
Represent searched paths using a tree.
12
Search Trees
Root
Branch Node
(Edge) (vertex)
Search Trees
Parent
(Ancestor)
Siblings
Child
(Descendant)
13
Search Trees
Ancestors
Descendants
Graph Searching/Traversing
• Given: a graph G = (V, E), directed or
undirected
• Explore every vertex and every edge
• Build a tree on the graph
– Pick a vertex as the root
– Choose certain edges to produce a tree
14
Breadth-First Search
• “Explore” a graph, turning it into a tree
– One vertex at a time
– Expand frontier of explored vertices across the
breadth of the frontier
• Builds a tree over the graph
– Pick a source vertex to be the root
– Find (“discover”) its children, then their
children, etc.
Breadth First Search (BFS)
Idea: After visiting node
• Visit siblings, then children
• Visit relatives left to right (top to bottom)
1
S
2 3
A B
6 7
4 5
D C D G
8 C 9 G 10 C G
11
15
Breadth-First Search
• Associate vertex “colors”
– White vertices have not been discovered
• All vertices start out white
– Grey vertices are discovered but not fully explored
• They may be adjacent to white vertices
– Black vertices are discovered and fully explored
• They are adjacent only to black and grey vertices
• Explore vertices by scanning adjacency list of
grey vertices
Breadth-First Search
BFS(G, s) {
initialize vertices;
Q = {s}; // Q is a queue; initialize to s
while (Q not empty) {
u = RemoveTop(Q);
for each v u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1;
v->p = u;
Enqueue(Q, v);
}
u->color = BLACK;
}
}
16
Breadth-First Search: Example
r s t u
v w x y
Breadth-First Search: Example
r s t u
0
v w x y
Q: s
17
Breadth-First Search: Example
r s t u
1 0
1
v w x y
Q: w r
Breadth-First Search: Example
r s t u
1 0 2
1 2
v w x y
Q: r t x
18
Breadth-First Search: Example
r s t u
1 0 2
2 1 2
v w x y
Q: t x v
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2
v w x y
Q: x v u
19
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: v u y
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: u y
20
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: y
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: Ø
21
BFS: The Code Again
BFS(G, s) {
Touch every vertex: O(V)
initialize vertices;
Q = {s};
while (Q not empty) { u = every vertex, but only once
u = RemoveTop(Q);
for each v u->adj {
So v = every vertex
if (v->color == WHITE)
that appears in v->color = GREY;
some other vert’s v->d = u->d + 1;
adjacency list v->p = u;
Enqueue(Q, v);
What will be the running time?
}
u->color = BLACK;
Total running time: O(V+E)
}
}
Depth-First Search
• Depth-first search is another strategy for
exploring a graph
– Explore “deeper” in the graph whenever
possible
– Edges are explored out of the most recently
discovered vertex v that still has unexplored
edges
– When all of v’s edges have been explored,
backtrack to the vertex from which v was
discovered
22
Depth-First Search
• Vertices initially colored white
• Then colored gray when discovered
• Then black when finished
Depth First Search (DFS)
Idea:
• Visit children, then siblings
• Visit siblings left to right, (top to bottom).
1
S
2 7
A B
8 11
3 6
D C D G
4 C 5 G 9 C G
10
Assuming that we pick the first element of Q,
Then where do we add path extensions to the Q?
23
Properties of depth-first search
• Complete? No: fails in infinite-depth spaces
Can modify to avoid repeated states along path
Iterative deepening search
• To avoid the infinite depth problem of DFS, we can decide to
only search until depth L, i.e. we don’t expand beyond depth L.
Depth-Limited Search
• What of solution is deeper than L? Increase L iteratively.
Iterative Deepening Search
•It inherits the memory advantage of Depth-First search.
24
Iterative deepening search L=0
49
Iterative deepening search L=1
50
25
Iterative deepening search lL=2
51
Iterative deepening search lL=3
52
26
Properties of iterative deepening search
• Complete? Yes
54
Example IDS
55
27
