Week 4: Heuristic Search Flashcards
What is a heuristic in AI search?
A rule of thumb or educated guess that estimates the cost from a given state to the goal.
Define h(n) in heuristic search.
h(n) is the estimated cost to reach the goal from node n.
What is the value of h(n) when n is a goal state?
h(n) = 0
What is best-first search?
An informed search strategy that selects the most promising node based on an evaluation function f(n).
What does f(n) represent in heuristic search?
An evaluation function that estimates the total cost of a solution path through node n.
What is greedy best-first search?
A search strategy that selects nodes with the lowest h(n) value, ignoring cost so far (g(n)).
What is the evaluation function for greedy best-first search?
f(n) = h(n)
What is A* search?
A search strategy using f(n) = g(n) + h(n), combining path cost and heuristic estimate.
What does g(n) represent in A* search?
The path cost from the start node to node n.
What is the evaluation function for A* search?
f(n) = g(n) + h(n)
Why is A* search considered optimal?
Because it guarantees the lowest-cost solution if the heuristic is admissible.
What is an admissible heuristic?
A heuristic that never overestimates the cost to reach the goal.
What is a consistent (monotonic) heuristic?
A heuristic where h(n) ≤ c(n, a, n’) + h(n’) for all nodes, ensuring optimality in A*.
Is greedy best-first search complete?
No, it is not complete as it can get stuck in loops.
Is A* search complete?
Yes, if the branching factor is finite and step costs are non-negative.
What is the time and space complexity of greedy best-first search?
O(b^m), where b is branching factor and m is maximum depth.
What is the main drawback of greedy best-first search?
It is not optimal and can lead to long detours or loops.
What is a priority queue in heuristic search?
A data structure that selects the next node based on the lowest f(n) value.
What is the heuristic used in the Romania route-finding example?
Straight-line distance to Bucharest.
In A*, what happens if h(n) is always 0?
A* becomes equivalent to uniform-cost search.
What is the benefit of using an informed search strategy?
It can dramatically reduce the number of nodes explored compared to uninformed search.
What is local search in AI?
Search techniques that operate using a single current node and move to neighbors, e.g., hill climbing.
Name two optimization-focused search algorithms.
Hill climbing and genetic algorithms.
What is the difference between uninformed and informed search?
Uninformed search uses no problem-specific info, informed search uses heuristics to guide search.
