Vault

ECS170-L4

2 min read

📗 -> 04/07/25: Lecture 4. Formulating a Problem as Search & Uninformed Search

[Lecture Slide Link]

🎤 Vocab

❗ Unit and Larger Context

Outline

Formulating a Problem as Search

  • Tree Search vs Graph Search (AIMA 3.3)
  • Evaluating Search Algorithms (AIMA 3.3)
    Uninformed Search
  • Uninformed Search vs Informed Search (AIMA 3.4)
  • Four Search Algorithms (BFS, UCS, DFS, Iterative Deepening) (AIMA 3.4)
  • Comparison of Search Algorithms (AIMA 3.4)

✒️ -> Scratch Notes

Paths with repeated states are non optimal (finding node A again in the tree)
Two typical solutions:

  • Ignore if likelihood of repetition is very low. Do a tree-like search
  • Do a graph search, keep a list of reached/visited states. Dependent on all states fitting easily in memory.

Graph Search: no state occurs on more than one path
During the search, states are in one of three disjoint subsets:

  1. Expanded node (visited and explored)
  2. Nodes in the frontier (reached but not expanded)
    • Functionally, has to do with being in the queue to be explored
  3. Nodes that have not been reached

Graph search algorithm is the same as tree search, with the addition of the explored set

Evaluating search algorithms

  1. Completeness - If there is a solution, is the algo guaranteed to find it?
    • Sometimes this can be do to time complexity, a DFS algorithm might get stuck in an infinite loop if poorly implemented
  2. Cost Optimality - Will the algorithm find the optimal/lowest cost solution?
  3. Time Complexity - How much time to find a solution
  4. Space Complexity - How much space is needed to find a solution?

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

🧪 -> 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

Graph View

Backlinks