Search Strategies
A general method in AI that explores paths from a start state to a goal.
What is a search strategy?
Best-First Search selects the node with the lowest value of this function.
What is h(n)?
Greedy Search does not guarantee this key property.
What is optimality?
A heuristic is admissible when it never does this to the actual cost.
What is overestimate?
This function estimates the cost from any node to the goal.
What is a heuristic function?
This type of search selects the most promising node based on evaluation.
What is Best-First Search?
One limitation of Best-First Search regarding the final path found.
What is it may not be optimal?
The main drawback of Greedy Search is that it ignores this.
What is the path cost (g(n))?
When the heuristic is both admissible and consistent, A* guarantees this.
What is optimality (and completeness)?
The method of designing heuristics by simplifying the original problem.
What is problem relaxation?
Search variant that explores neighbors without heuristic guidance.
What is Hill Climbing?
Greedy Best‑First focuses exclusively on what?
What is front‑end cost to goal?
A typical map navigation heuristic used is ___ distance.
What is Euclidean distance?
A* is complete when the search space is ___.
What is finite?
Measurement of how many nodes are expanded during search.
What is time complexity?
A* uses this combined function to pick the next node.
What is f(n) = g(n) + h(n)?
Best‑First uses only this to pick which node to expand next.
What is heuristic h(n)?
Continues exploring until finding the goal without considering cost.
What is pure greedy?
A* is complete when the search space is ___.
What is admissible?
Condition h(n) ≤ c(n,n') + h(n') guarantees this property.
What is consistency?
search that uses the least path cost so far.
What is Uniform Cost Search?
Data structure commonly used to implement Best-First Search.
What is a priority queue?
The main drawback of Greedy Search is that it ignores this
What is the path cost (g(n))?
If a heuristic satisfies the triangle inequality, it is considered this.
What is consistent (or monotonic)?
The number of nodes explored during search is referred to as this.
What is time complexity?