Uninformed Search
General Tree Search Paradigm
function tree-search(root-node)
fringe successors(root-node)
while ( notempty(fringe) )
{node remove-first(fringe) //lowest f value
state state(node)
if goal-test(state) return solution(node)
fringe insert-all(successors(node),fringe) }
return failure
end tree-search
Fringe is synonymous with Frontier and Open List
Explored List is synonymous with Closed List
(LIFO)
Evaluating Search strategies
• A search strategy is defined by picking the order of node expansion
• Strategies are evaluated along the following dimensions:
Evaluating Search strategies
• A search strategy is defined by picking the order of node expansion
• Strategies are evaluated along the following dimensions:
– completeness: does it always find a solution if one exists?
Guarantees finding a solution whenever one exists
Evaluating Search strategies
• A search strategy is defined by picking the order of node expansion
• Strategies are evaluated along the following dimensions:
– completeness: does it always find a solution if one exists?
Guarantees finding a solution whenever one exists
– time complexity: How long (worst/ average case) does it take to find a solution?
Number of nodes generated
Evaluating Search strategies
• A search strategy is defined by picking the order of node expansion
• Strategies are evaluated along the following dimensions:
– completeness: does it always find a solution if one exists?
Guarantees finding a solution whenever one exists
– time complexity: How long (worst/ average case) does it take to find a solution?
Number of nodes generated
– space complexity: How much space is used by the algorithm?
Maximum number of nodes in memory
Evaluating Search strategies
• A search strategy is defined by picking the order of node expansion
• Strategies are evaluated along the following dimensions:
– completeness: does it always find a solution if one exists?
Guarantees finding a solution whenever one exists
– time complexity: How long (worst/ average case) does it take to find a solution?
Number of nodes generated
– space complexity: How much space is used by the algorithm?
Maximum number of nodes in memory
– optimality: does it always find an optimal solution?
Least-cost solution (Global minima)
Evaluating Search strategies
• A search strategy is defined by picking the order of node expansion
• Strategies are evaluated along the following dimensions:
– completeness: does it always find a solution if one exists?
Guarantees finding a solution whenever one exists
– time complexity: How long (worst/ average case) does it take to find a solution?
Number of nodes generated
– space complexity: How much space is used by the algorithm?
Maximum number of nodes in memory
– optimality: does it always find an optimal solution?
Least-cost solution (Global minima)
– systematicity: does it visit each state at most once?
Repeated states
Search strategies
a
b c
d e f g h
• Time and space complexity are measured in terms of
– b: maximum branching factor of the search tree
Maximum number of successors of any state
– d: depth of the least-cost solution
Depth of the shallowest goal node in the search tree
Minimal length of a path between the initial and a goal state
– m: maximum depth of the state space (may be ∞)
(Shortest First)
because we are visiting each node at each level.
BFS is not optimal when step costs are different because shortest path may
not be the cheapest path. Both paths are same when step costs are same.
(Cheapest first)
BFS is not optimal when step
costs are different because
shortest path may not be the
cheapest path. Both paths are
same when step costs are same.
Yes (b is finite)
Ex. weights in decreasing order
with geometric progression
O(b(C*/e))
O(b(C*/e))
Breadth-First Search
Depth-First Search
Uniform Cost Search
Homework
DFS
http://www.youtube.com/watch?v=dtoFAvtVE4U
UCS
http://www.youtube.com/watch?v=z6lUnb9ktkE
Memory Limitation
• Suppose:
2 GHz CPU
1 GB main memory
100 instructions / expansion
5 bytes / node
200,000 expansions / sec
Memory filled in 100 sec … < 2 minutes
Time vs. Memory
Idea 1: Beam Search
Beam Search tries to reduce space complexity of BFS
• Maintain a constant sized frontier
• Whenever the frontier becomes large
– Prune the worst nodes
Optimal: no
Complete: no
Idea 2: Depth-limited Search
• Avoid the infinite depth problem of DFS
• Decide to only search until depth L
– don't expand beyong depth L
• What if solution is deeper than at depth L?
Optimal: no
Complete: no
Idea 3: Iterative deepening search
Increase L iteratively
Iterative Deepening Search (IDS) tries to reduce time
complexity of DFS.
It inherits the memory advantage of DFS.
Iterative deepening search L=0
Iterative deepening search L=1
Iterative deepening search L=2
Iterative deepening search L=3
Iterative deepening search
• Number of nodes generated in a depth-limited search to depth d with branching
factor b:
• NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd
Iterative deepening search
• Number of nodes generated in a depth-limited search to depth d with branching
factor b:
• NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd
• Number of nodes generated in an iterative deepening search to depth d with
branching factor b:
• NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd
Iterative deepening search
• Number of nodes generated in a depth-limited search to depth d with branching
factor b:
• NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd
• Number of nodes generated in an iterative deepening search to depth d with
branching factor b:
• NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd
• Asymptotic ratio: (b+1)/(b-1)
• For b = 10, d = 5,
•
– NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
–
– NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
–
• Overhead = (123,456 - 111,111)/111,111 = 11%
Iterative deepening search
• Complete?
– Yes
• Time?
– (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
• Space?
– O(bd)
• Optimal?
– Yes, if step cost = 1
– Can be modified to explore uniform cost tree (iterative lengthening)
• Systematic?
Cost of Iterative Deepening
b ratio ID to DLS
2 3
3 2
5 1.5
10 1.2
25 1.08
100 1.02
Forwards vs. Backwards
Forward search: fan out should be small
Backward search: fan in should be small
Bi-directional search
• Complete? Yes
• Time? BiSearch: meets at d/2 depth,
– O(bd/2) So we do two searches of d/2 depth
• Space?
– O(bd/2)
• Optimal?
– Yes if uniform cost search used in both directions
Summary of algorithms
A
BFS: A,B,G
DFS: A,B,C,D,G
B IDDFS: (A), (A, B, G)
C Note that IDDFS can do fewer
D expansions than DFS on a graph
G shaped search space.
BFS: A,B,G
A
DFS: A,B,A,B,A,B,A,B,A,B
B IDDFS: (A), (A, B, G)
C Note that IDDFS can do fewer
D expansions than DFS on a graph
G shaped search space.
Search on undirected graphs or directed graphs with cycles…
Cycles galore…
Graph (instead of tree) Search:
Handling repeated nodes
• Repeated expansions is a bigger issue for DFS than for BFS or IDDFS
• Trying to remember all previously expanded nodes and comparing the
new nodes with them is infeasible
• Space becomes exponential
• duplicate checking can also be expensive
• Partial reduction in repeated expansion can be done by
• Checking to see if any children of a node n have the same state as the
parent of n
• Checking to see if any children of a node n have the same state as any
ancestor of n (at most d ancestors for n—where d is the depth of n)
General Graph Search Paradigm
function tree-search(root-node)
fringe successors(root-node)
explored empty
while ( notempty(fringe) )
{node remove-first(fringe)
state state(node)
if goal-test(state) return solution(node)
explored insert(node,explored)
fringe insert-all(successors(node),fringe, if node not in explored)
}
return failure
end tree-search
Fringe is synonymous with Frontier and Open List
Explored List is synonymous with Closed List
Graph Search
• Procedure GRAPHSEARCH
• Create a search graph G consisting solely of start node s.
• Put s on a list called OPEN
• Create a list called CLOSED that is initially empty.
• Loop: If OPEN is empty, exit with failure
• Select first node on OPEN, remove it from OPEN and put it on CLOSED. Call this
node n.
• If n is goal node, exit successfully with the solution obtained by tracing a path
along the pointers from n to s in G
Graph Search
• Expand node n generating the set M of its successors and install them as
successors of n in G.
• Establish a pointer to n from those members of M that were not already in G. Add
these members of M to OPEN.
• For each member of M already in G, decide whether or not to redirect its
pointer to n.
• For each member of M already on CLOSED, decide for each of its descendants
in G whether or not to redirect its pointer.
• Reorder the list OPEN, either according to
• some arbitrary scheme or
• heuristic merit
Breadth-First goes level by level
Visualizing Breadth-First & Uniform Cost Search
This is also a proof of
optimality…
UCS explores all nodes along all directions
within a certain cost
Breadth-First goes level by leve
Problem
• All these methods are slow (blind)
© Jen
Theodore
• Solution add guidance (“heuristic estimate”)
“informed search”
