Artificial Intelligence
Search Agents
Uninformed search
Uninformed search
Use no domain knowledge!
Strategies:
1. Breadth-first search (BFS): Expand shallowest node
Uninformed search
Use no domain knowledge!
Strategies:
1. Breadth-first search (BFS): Expand shallowest node
2. Depth-first search (DFS): Expand deepest node
Uninformed search
Use no domain knowledge!
Strategies:
1. Breadth-first search (BFS): Expand shallowest node
2. Depth-first search (DFS): Expand deepest node
3. Depth-limited search (DLS): Depth first with depth limit
Uninformed search
Use no domain knowledge!
Strategies:
1. Breadth-first search (BFS): Expand shallowest node
2. Depth-first search (DFS): Expand deepest node
3. Depth-limited search (DLS): Depth first with depth limit
4. Iterative-deepening search (IDS): DLS with increasing limit
Uninformed search
Use no domain knowledge!
Strategies:
1. Breadth-first search (BFS): Expand shallowest node
2. Depth-first search (DFS): Expand deepest node
3. Depth-limited search (DLS): Depth first with depth limit
4. Iterative-deepening search (IDS): DLS with increasing limit
5. Uniform-cost search (UCS): Expand least cost node
Breadth-first search (BFS)
BFS: Expand shallowest first.
BFS search
BFS Criteria
BFS criteria?
BFS
• Complete Yes (if b is finite)
• Time 1 + b + b2 + b3 + . . . + bd = O(bd)
• Space O(bd)
Note: If the goal test is applied at expansion rather than gen-
eration then O(bd+1)
• Optimal Yes (if cost = 1 per step).
• implementation: fringe: FIFO (Queue)
Question: If time and space complexities are exponential,
why use BFS?
BFS
How bad is BFS?
BFS
How bad is BFS?
Time and Memory requirements for breadth-first search for a branching factor
b=10; 1 million nodes per second; 1,000 bytes per node.
BFS
How bad is BFS?
Time and Memory requirements for breadth-first search for a branching factor
b=10; 1 million nodes per second; 1,000 bytes per node.
Memory requirement + exponential time complexity are the
biggest handicaps of BFS!
DFS
DFS: Expand deepest first.
DFS search
DFS
DFS criteria?
DFS
• Complete No: fails in infinite-depth spaces, spaces with loops
Modify to avoid repeated states along path.
⇒ complete in finite spaces
• Time O(bm): 1 + b + b2 + b3 + . . . + bm = O(bm)
bad if m is much larger than d
but if solutions are dense, may be much faster than BFS.
• Space O(bm) linear space complexity! (needs to store only
a single path from the root to a leaf node, along with the
remaining unexpanded sibling nodes for each node on the
path, hence the m factor.)
• Optimal No
• Implementation: fringe: LIFO (Stack)
DFS
How bad is DFS?
Recall for BFS...
Depth =16.
We go down from 10 exabytes in BFS to . . . in DFS?
DFS
How bad is DFS?
Recall for BFS...
Depth =16.
We go down from 10 exabytes in BFS to 156 kilobytes in DFS!
Depth-limited search
• DFS with depth limit l (nodes at level l has no successors).
• Select some limit L in depth to explore with DFS
• Iterative deepening: increasing the limit l
Depth-limited search
• If we know some knowledge about the problem, may be we
don’t need to go to a full depth.
Idea: any city can be reached from another city in at most L
steps with L < 36.
Iterative Deepening
• Combines the benefits of BFS and DFS.
• Idea: Iteratively increase the search limit until the depth of the
shallowest solution d is reached.
• Applies DLS with increasing limits.
• The algorithm will stop if a solution is found or if DLS returns
a failure (no solution).
• Because most of the nodes are on the bottom of the search
tree, it not a big waste to iteratively re-generate the top
• Let’s take an example with a depth limit between 0 and 3.
Iterative Deepening
Limit = 0
Iterative Deepening
Limit = 1
Iterative Deepening
Limit = 2
Iterative Deepening
Limit = 3
Uniform-cost search
• The arcs in the search graph may have weights (different cost
attached). How to leverage this information?
Uniform-cost search
• The arcs in the search graph may have weights (different cost
attached). How to leverage this information?
• BFS will find the shortest path which may be costly.
• We want the cheapest not shallowest solution.
Uniform-cost search
• The arcs in the search graph may have weights (different cost
attached). How to leverage this information?
• BFS will find the shortest path which may be costly.
• We want the cheapest not shallowest solution.
• Modify BFS: Prioritize by cost not depth → Expand node n
with the lowest path cost g(n)
Uniform-cost search
• The arcs in the search graph may have weights (different cost
attached). How to leverage this information?
• BFS will find the shortest path which may be costly.
• We want the cheapest not shallowest solution.
• Modify BFS: Prioritize by cost not depth → Expand node n
with the lowest path cost g(n)
• Explores increasing costs.
UCS algorithm
Uniform-cost search
Go from Chicago to Sault Ste Marie. Using BFS, we would find
Chicago-Duluth-Sault Ste Marie. However, using UCS, we would
find Chicago-Pittsburgh-Toronto-Sault Ste Marie, which is actually
the shortest path!
Uniform-cost search
• Complete Yes, if solution has a finite cost.
• Time
– Suppose C ∗: cost of the optimal solution
– Every action costs at least (bound on the cost)
– The effective depth is roughly C ∗/ (how deep the cheapest
solution could be).
∗
– O(bC /)
C ∗ /
• Space # of nodes with g ≤ cost of optimal solution, O(b )
• Optimal Yes
• Implementation: fringe = queue ordered by path cost g(n),
lowest first = Heap!
Uniform-cost search
While complete and optimal, UCS explores the space in
every direction because no information is provided about
the goal!
Exercise
Question: What is the order of visits of the nodes and the
path returned by BFS, DFS and UCS?
Exercise: BFS
Exercise: BFS
Exercise: BFS
Exercise: BFS
Exercise: BFS
Exercise: BFS
Exercise: BFS
Exercise: BFS
Exercise: BFS
Exercise: DFS
Exercise: DFS
Exercise: DFS
Exercise: DFS
Exercise: DFS
Exercise: DFS
Exercise: DFS
Exercise: DFS
Exercise: DFS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Exercise: UCS
Examples using the map
Start: Las Vegas
Goal: Calgary
BFS
Order of Visit: Las Vegas, Los Angeles, Salt Lake City, El Paso, Phoenix, San Francisco,
Denver, Helena, Portland, Dallas, Santa Fe, Kansas City, Omaha, Calgary.
Examples using the map
Start: Las Vegas
Goal: Calgary
DFS
Order of Visit: Las Vegas, Los Angeles, El Paso, Dallas, Houston, New Orleans, Atlanta,
Charleston, Nashville, Saint Louis, Chicago, Duluth, Helena, Calgary.
Examples using the map
Start: Las Vegas
Goal: Calgary
UCS
Order of Visit: Las Vegas, Los Angeles, Salt Lake City, San Francisco, Phoenix, Denver, Helena,
El Paso, Santa Fe, Portland, Seattle, Omaha, Kansas City, Calgary.
Credit
• Artificial Intelligence, A Modern Approach. Stuart Russell and
Peter Norvig. Third Edition. Pearson Education.
http://aima.cs.berkeley.edu/
