Title: EAI / 04_informed_search

Q: Describe the idea of heuristic search.
A: - Use problem- or domain-specific knowledge during search
- Use a heuristic function \(h\rightsquigarrow \text{"desirability"}\) which estimates minimal costs from state \(n\) to a goal state

Q: Explain greedy search.
A: - uses evaluation function \(f(n)=h(n)\)
- does not take already "spent" costs into account
- expands node with the smallest \(f\)-value next

Q: Name the properties of greedy search.
A: - Complete: Only with loop checks
- Time complexity: \(\mathcal{O}(b^m)\)
- Space complexity: \(\mathcal{O}(b^m)\)
- Optimal: No

Q: Explain \(A^*\)-Search.
A: Use evaluation function \(f(n)=g(n)+h(n)\)
\(g(n)\): path costs from start to \(n\)
\(h(n)\): estimated cost to goal from \(n\)
\(f(n)\): estimated total cost of path though \(n\) to goal
\(h(n)\) has to be admissible

Q: When is a heuristic admissible?
A: \(h\) is admissible when for every node \(n\) the following holds:
1. \(h(n) \leq h^*(n)\) where \(h^*(n)\) is the true cost from \(n\) (\(h\) is optimistic)
2. \(h(n) \geq 0\)
3. \(h(G)=0\) for every goal \(G\)

Q: When is \(A^*\) using tree search optimal?
A: \(A^*\) using tree search is optimal if \(h\) is admissible.

Q: Define the property of a consistent heuristic.
A: A heuristic is consistent if, for every node \(n\), every successor \(n'\) of \(n\) and every operator \(a\),
\[h(n) \leq c(n,a,n')+h(n')\]holds, where \(c(n,a,n')\) are the path costs for \(a\).

Q: When is \(A^*\) using graph search optimal?
A: \(A^*\) using graph search is optimal when \(h\) is consistent

Q: Define the properties of \(A^*\).
A: - Complete: Yes (unless there are infinitley many nodes \(n\) with \(f(n) \leq f(G)\)
- Time complexity: exponential in \(\varepsilon \times d\), where \(\varepsilon\) = relative error and \(d\) = solution depth
- Space complexity: exponential
- Optimal: Yes

Q: When does a heuristic dominate another?
A: For admissible heuristics \(h_1\) and \(h_2\) we say \(h_2\) dominates \(h_1\) if \(h_2(n) \geq h_1(n)\) for every node \(n\).