Informed Seach Flashcards
(9 cards)
What is informed search?
A search strategy that uses a heuristic to estimate the cost from the current node to the goal
What is a heuristic function h(n)?
It estimates the cost of the cheapest path from node n to the goal.
What is Greedy Best-First Search?
search strategy that expands the node with the lowest h(n); not guaranteed to be complete or optimal
Why is Greedy Best-First Search not optimal?
It may get stuck in loops or take a longer path if h(n) is misleading.
What is A* Search?
A search that uses f(n) = g(n) + h(n), combining actual cost so far and heuristic estimate.
What is an admissible heuristic?
A heuristic that never overestimates the true cost to reach the goal.
Why does A* Search find optimal solutions?
Because it uses admissible heuristics and evaluates total estimated cost.
What is Iterative Deepening A* (IDA*)?
A memory-efficient version of A* that searches with increasing f-cost limits.
What is Weighted A* Search?
A* search using f(n) = g(n) + αh(n), where α > 1; faster but not always optimal.