Uninformed Search Strategies

Uninformed Search

• Uses only information available in the problem definition
• Lacks domain knowledge

Strategies

• Breadth-first search (BFS) expands the shallowest node first
• Depth-first search (DFS) expands the deepest node first
• Depth-limited search (DLS) performs depth-first search with a depth limit
• Iterative-deepening search (IDS) uses depth-limited search with an increasing limit
• Uniform-cost search (UCS) expands the least-cost node

Characteristics of Breadth-First Search (BFS)

• BFS expands the shallowest node first
• Complete if branching factor (b) is finite
• Time complexity is O(b^d), where d is the depth
• Space complexity is O(b^d)
• Note: If the goal test is applied at expansion, space complexity becomes O(b^(d+1))
• Optimal if cost is the same for each step
• Implementation uses a FIFO queue for the fringe

Limitations of Breadth-First Search (BFS)

• Memory requirements and exponential time complexity are significant challenges
• Illustrative example: a branching factor of b=10, 1 million nodes/second, and 1,000 bytes/node
  • Depth of 2 requires 107 kilobytes
  • Depth of 4 requires 10.6 megabytes
  • Depth of 6 requires 1 gigabyte
  • Depth of 8 requires 103 gigabytes
  • Depth of 10 requires 10 terabytes
  • Depth of 12 requires 1 petabyte
  • Depth of 14 requires 99 petabytes
  • Depth of 16 requires 10 exabytes

Characteristics of Depth-First Search (DFS)

• DFS expands the deepest node first
• Not complete because it fails in infinite-depth spaces and spaces with loops, but it can be modified to check repeated states along a path to become complete in finite spaces
• Time complexity is O(b^m), where m is the maximum depth; this can be worse than BFS if m is much larger than d
• May be faster than BFS if solutions are dense
• Space complexity is O(bm), a linear space complexity
• Needs only a single path from root to leaf
• Not optimal
• Implementation uses a LIFO stack for the fringe

Benefits of Depth-First Search (DFS)

• Can reduce memory requirements
• Example: BFS requires 10 exabytes while DFS needs 156 kilobytes at depth=16

Depth-Limited Search (DLS)

• Performs DFS with a preset depth limit (l)
• Selects a depth L to explore with DFS
• Nodes at level l have no successors

Iterative Deepening Search (IDS)

• Combines benefits of BFS and DFS
• Applies DLS, iteratively increasing the limit (l)
• Any city can be reached from another in at most L steps with L < 36
• Stops when a solution is found or DLS returns a failure (no solution)
• Because most nodes reside at the bottom of the search tree, iteratively re-generating the top is not a huge waste

Uniform-Cost Search (UCS)

• Arcs in the search graph can have weights (different costs attached)
• BFS finds the shortest path, which may be costly, but UCS wants the cheapest solution, not shallowest
• Modifies BFS by prioritizing minimum cost, not depth
• Expands nodes (n) with the lowest path cost, g(n)
• Explores increasing costs
• To travel from Chicago to Sault Ste Marie, BFS might find Chicago-Duluth-Sault Ste Marie, but UCS would find the shorter path of Chicago-Pittsburgh-Toronto-Sault Ste Marie

Properties of Uniform-Cost Search (UCS)

• Complete if solution has a finite cost
• Time complexity is O(b^(C*/)), where C* is the cost of the optimal solution and is a bound on the cost
• Space complexity, # of nodes with G ≤ cost of solution is O(b^(C*/))
• UCS is optimal
• Implementation uses a queue ordered by path cost g(n), lowest first, implemented with a Heap
• While complete and optimal it explores the space in every direction due to lack of goal information

Search Exercise

• Determine the order of visited nodes and the path returned by BFS, DFS, and UCS
• Perform "Examples using the map," starting in Las Vegas and seeking to reach Calgary
• Breadth-first search visits the following cities in order: Las Vegas, Los Angeles, Salt Lake City, El Paso, Phoenix, San Francisco, Denver, Helena, Portland, Dallas, Santa Fe, Kansas City, Omaha, Calgary
• Depth-first search visits the following cities in order: Las Vegas, Los Angeles, El Paso, Dallas, Houston, New Orleans, Atlanta, Charleston, Nashville, Saint Louis, Chicago, Duluth, Helena, Calgary
• Uniform-cost search visits the following cities in order: Las Vegas, Los Angeles, Salt Lake City, San Francisco, Phoenix, Denver, Helena, El Paso, Santa Fe, Portland, Seattle, Omaha, Kansas City, Calgary