Title: EAI / 03_uninformed_search

Q: Define the 4 items of a search problem.
A: 1. initial state
2. successor function \(S(x)\)
3. goal test
4. path cost

Q: What is the solution of a search problem?
A: A sequence of actions leading from the initial state to a goal state.

Explain tree-like search.

Q: What can cause a linear search problem to turn into an exponential one?
A: Failure to detect repeated states.

Explain the graph search algorithm.

What is the difference between a state and a node?

Q: What are the metrics on which search strategies are evaluated on?
A: - completeness
- time complexity
- space complexity
- optimality

Q: Explain completeness.
A: does it always find a solution if one exists?

Q: Explain time complexity.
A: number of nodes generated/expanded

Q: Explain space complexity.
A: maximum number of nodes in memory

Q: Explain optimality.
A: does it always find a least-cost solution?

Q: What are time and space complexity measured in?
A: \(b\): maximum branching factor of search tree
\(d\): depth of the least-cost solution
\(m\): maximum depth of the state space (may be \(\infty\))

Explain Breadth-First-Seach.

Q: When should the goal test happen in BFS?
A: At generation time (when expanded).

Q: Name the properties of breadth-first-search.
A: Completeness: Complete (if \(b\) is finite)
Time complexity: \(\mathcal{O}(b^d)\)
Space complexity: \(\mathcal{O}(b^d)\)
Optimal: Yes (if cost = 1 per step); not optimal in general

Explain Uniform-cost search.

Q: Name the properties of uniform-cost search.
A: Complete: Yes, if step cost \(\geq \varepsilon\)
Time complexity: \(\mathcal{O}(b^{1+\lfloor C^*/\varepsilon \rfloor})\) where \(C^*\) is the cost of an optimal solution
Space complexity: \(\mathcal{O}(b^{1+\lfloor C^*/\varepsilon \rfloor})\)
Optimal: Yes (when solution test at expansion time)

Q: Name the properties of DFS.
A: - Complete: No (fails in infinite-depth, spaces with loops)
- Time complexity: \(\mathcal{O}(b^m)\)
- Space complexity: \(\mathcal{O}(bm)\) (linear!)
- Optimal: No

Explain Depth-limited search.

Explain Iterative-deepening search.

Q: Name the properties of iterative deepening search
A: - Complete: Yes
- Time complexity: \(\mathcal{O}(b^d)\)
- Space complexity: \(\mathcal{O}(b\cdot d)\)
- Optimal: Yes (if step cost = 1)
Note: 11% more expensive than BFS

What is Bidirectional search?