What defines an admissible heuristic?

An admissible heuristic is defined as one that never overestimates the actual cost to reach the goal from any given node. This property is crucial because it ensures that the heuristic provides a lower bound on the actual cost needed, allowing algorithms like A* to guarantee that they will find the optimal solution if one exists.

When a heuristic is admissible, it implies that the estimated cost to reach a goal state is either accurate or underestimated, which prevents the algorithm from getting misled by faulty estimates. This characteristic is essential for the efficiency and effectiveness of search algorithms in AI, particularly in pathfinding and graph traversal scenarios where finding the most cost-effective path is paramount.

While the concept of consistency (or monotonicity) across all nodes is significant, it is a separate property that ensures the heuristic behaves well in terms of the estimated cost between nodes. Notably, an admissible heuristic can indeed be consistent, but consistency is not a requirement for admissibility. Therefore, the statement that an admissible heuristic never overestimates the actual cost directly captures the essence of what makes it advantageous in search algorithms.