What is an admissible heuristic? Why is admissibility required for optimality in A* tree search?

Admissible Heuristic

A heuristic function h(n) is admissible if it never overestimates the actual cost to reach the nearest goal state from node n:

where h^*(n) is the true optimal cost.

Optimality Proof: If h(n) were to overestimate, A* might prematurely terminate at a suboptimal goal node thinking the optimal goal path is more expensive than it truly is. Admissibility guarantees that optimal paths are never pruned or overlooked.