ECS170-L5

📗 -> 04/09/25: ECS170-L5

---

[Lecture Slide Link]

🎤 Vocab

❗ Unit and Larger Context

Summary

Graph search uses more memory than tree-like search but avoids repeated states

Search Algorithm Evaluation

• Completeness
• Cost Optimality
• Time Complexity
• Space complexity

Four Uninformed search algorithms

• Breadth First Search
• Uniform-Cost Search
• Depth First Search
• Iterative Deepening Depth First Search

✒️ -> Scratch Notes

More notations for our analysis:

b (branching factor) - Maximum number of successors of a search node
d (depth) - Number of actions in optimal solution
m (maximum depth) - Maximum actions on any path

BFS

• Is complete, will correctly determine solution or no solution
• Will find the shortest solution first
• Total number of nodes generated is: -> Time complexity and Space complexity

Memory requirements quickly become a problem:
Consider 𝑏=10, 𝑑=10, memory = 1000 bytes/node, speed = 1M nodes/sec
- Search time (1010): 3 hours
- Search space (1010): 10 Terabyte

Uninformed search vs Informed search

Uninformed Search (blind search)

Strategies have no information about states beyond those provided in the problem definition
All they can do is generate successors and distinguish a goal state from a non-goal state
All search strategies are distinguished by the order in which nodes are expanded

Example Algos:

BFS - FIFO

• Explain more about it above
• Time and Space complexity:

DFS - LIFO

• Time:
  • Terrible if m >> d
  • Potentially more efficient than BFS if solutions are dense
• Space:
  • Only store nodes in the current path () and all frontier nodes ()
  • Linear space complexity!

Uniform Cost Search (Also known as Best First Search)

• Instead of expanding the shallowest node like BFS, uniform cost search expands the node with the lowest path cost
• Implementation similar to BFS, but applies the path cost
  • Orders frontiers by , explores the lowest path cost
  • Effectively, Best First Search
  • Will find the path with the lowest cost
• Cannot be characterized in Time/Space complexity with b, d, m
  BFS is optimal if all step costs (actions) are equal, but UCS is optimal for any cost function

Iterative Deepening:

• Seeks to address issues with DFS:
  • Fails in infinite-depth search spaces
  • Can be very inefficient if m >> d (m=maximum depth, d=depth of solution)
• Idea #1 (Depth Limited Search): Set a limit I on search depth
  • Prevents infinite growth of early paths that do not contain goal node
  • Succeeds if d <= I; Fails otherwise
• Idea #2 (Iterative Deepening Search, or Iterative Deepening DFS)
  • Set an initial limit I
  • At each next depth with no goal, increase I
    May seem wasteful to regenerate initial states multiple times, but it is not significant. Most nodes are the bottom level of the search tree (growing by a factor of m, or I in this case). When search space is large, this reduces cost

Completeness - Complete
Cost Optimality - Optimal if step costs are equal, like BFS
Time Complexity - O(b^d)
Space Complexity -

Informed Search or Heuristic Search

Strategies that know whether one non-goal state is “more promising” than another

🧪 -> Refresh the Info

Did you generally find the overall content understandable or compelling or relevant or not, and why, or which aspects of the reading were most novel or challenging for you and which aspects were most familiar or straightforward?)

Did a specific aspect of the reading raise questions for you or relate to other ideas and findings you’ve encountered, or are there other related issues you wish had been covered?)

🔗 -> Links

Resources

• Put useful links here

Connections

• Link all related words