## Definition **Greedy Best-First Search** expands the node with the lowest **heuristic value $h(n)$** alone — ignoring the path cost $g(n)$. It is "greedy" because it prefers nodes that *appear* closest to the goal without accounting for how far they are from the start. ## Algorithm Identical to [[A Star Algorithm]] but orders the frontier by $h(n)$ instead of $f(n) = g(n) + h(n)$. ## Properties - **Complete:** no, in infinite spaces (can get stuck). - **Optimal:** no. - **Time:** worst-case $O(b^m)$ but often much better with a good heuristic. - **Space:** $O(b^m)$ — keeps all explored nodes. ## Trade-offs vs A* - **Pro:** very fast in practice — often expands far fewer nodes than A*. - **Con:** the path it finds is usually *not* optimal. For applications where *any* reasonable solution is acceptable (route suggestion, exploratory search), greedy can be the right choice. For applications requiring optimality, use A*. ## Pathological Cases A misleading heuristic can lead greedy search arbitrarily astray. Example: in route planning, a node *geographically* close to the goal might be on the wrong side of an impassable obstacle. $h$ says "close"; reality says "expensive detour ahead." ## Connection to Best-First Family "Best-first" is the umbrella for any algorithm that selects a node by some evaluation function. Greedy uses $h(n)$; A* uses $g(n) + h(n)$; UCS uses $g(n)$. They are points on the same axis. ## Related - [[Heuristic Search]] - [[A Star Algorithm]] - [[Beam Search]]