Scribd
Upload
259 views48 pages

Search Agents Uninformed Search: Artificial Intelligence

This document discusses uninformed search strategies used in artificial intelligence. It describes four main strategies: breadth-first search (BFS), depth-first search (DFS), depth-limited search (DLS), and iterative-deepening search (IDS). BFS expands the shallowest nodes first, DFS expands the deepest nodes first, DLS uses DFS with a depth limit, and IDS repeatedly performs DLS with increasing depth limits. The document provides analysis of the time and space complexity of each strategy. It also includes an example comparing the order of node visits and solution paths for BFS, DFS, and uniform-cost search on a map.

Uploaded by

syed hamza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
259 views48 pages

Search Agents Uninformed Search: Artificial Intelligence

This document discusses uninformed search strategies used in artificial intelligence. It describes four main strategies: breadth-first search (BFS), depth-first search (DFS), depth-limited search (DLS), and iterative-deepening search (IDS). BFS expands the shallowest nodes first, DFS expands the deepest nodes first, DLS uses DFS with a depth limit, and IDS repeatedly performs DLS with increasing depth limits. The document provides analysis of the time and space complexity of each strategy. It also includes an example comparing the order of node visits and solution paths for BFS, DFS, and uniform-cost search on a map.

Uploaded by

syed hamza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 48

Artificial Intelligence

Lecture 04
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
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
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.


Credit
• Artificial Intelligence, A Modern Approach. Stuart Russell and
Peter Norvig. Third Edition. Pearson Education.

http://aima.cs.berkeley.edu/

You might also like