Informed Search: A*, Admissible & Consistent Heuristics

A* expands the frontier node of smallest $f(n)=g(n)+h(n)$; an admissible heuristic makes tree-search A* optimal while the stronger consistency condition is needed for graph-search A*, and real-time cousins like LRTA* trade optimality for a bounded $O(n^2)$ worst case.