Heurisitics Flashcards
(19 cards)
Front
Back
What is a heuristic function in search algorithms?
A function that estimates the cost to reach the goal from a given state.
What are the two main properties of an admissible heuristic?
- It never overestimates the true cost to reach the goal.\n2. It is optimistic, meaning h(n) ≤ h*(n) for all nodes.
What does it mean for a heuristic to be consistent (monotonic)?
For all nodes n and successors n’:
h(n) ≤ c(n, n’) + h(n’)
It ensures that the estimated cost always decreases along a path.
Can a heuristic be consistent but not admissible?
No. Consistency implies admissibility, but not vice versa.
What is the impact of a heuristic being inadmissible?
It can cause A* to find non-optimal paths or even miss the goal if not handled carefully.
What happens if a heuristic is zero everywhere?
A* becomes equivalent to uniform-cost search (Dijkstra’s algorithm).
What happens if a heuristic overestimates the cost?
The algorithm may become greedy and miss the optimal path.
Define the Manhattan distance heuristic. When is it admissible?
h(n) = |x₁ - x₂| + |y₁ - y₂| \nAdmissible in grid environments with only horizontal/vertical movement and uniform cost.
Define the Euclidean distance heuristic. When is it admissible?
h(n) = sqrt((x₁ - x₂)² + (y₁ - y₂)²)\nAdmissible if diagonal movement is allowed and cost corresponds to Euclidean distance.
What is the effect of scaling a heuristic by a constant factor >1?
It can make the heuristic inadmissible and cause non-optimal paths in A*.
What is the effect of scaling a heuristic by a constant factor <1?
The heuristic remains admissible, but A* behaves more like uniform-cost search (slower, more exploration).
What is the role of heuristics in A* search?
They guide the search towards the goal more efficiently by estimating remaining cost.
What is the function used by A* to rank nodes?
f(n) = g(n) + h(n)\nWhere g(n) is the cost to reach n, and h(n) is the estimated cost to goal.
What’s the danger of a heuristic that returns negative values?
It can cause incorrect prioritization and violate A*’s optimality guarantees.
What is a perfect heuristic?
A heuristic that returns the exact cost to the goal from any node. Denoted h*(n).
Is a more accurate heuristic always better?
Not necessarily — more accurate heuristics can be more expensive to compute, which may offset the gain.
What is a dominant heuristic?
Given two admissible heuristics h₁ and h₂, if h₁(n) ≥ h₂(n) for all n, then h₁ dominates h₂, and A* using h₁ will expand no more nodes than with h₂.
What does informed search mean?
A search that uses heuristics to guide decision-making (e.g., A*, greedy search).
