Conditions for optimality: Admissibility and consistency

Admissibility and consistency are conditions that can guarantee optimality of solutions in heuristic search algorithms.

A heuristic function is said to be admissible if it never overestimates the actual cost of reaching the goal node from any given node. In other words, the heuristic function always returns a value that is less than or equal to the actual cost of reaching the goal node. If a heuristic function is admissible, then any algorithm that uses it to guide its search is guaranteed to find an optimal solution.

A heuristic function is said to be consistent (or monotonic) if the estimated cost of reaching a successor node plus the cost of moving from the current node to that successor is always less than or equal to the estimated cost of reaching the current node. In other words, the heuristic function is consistent if the estimated cost of reaching a node is always less than or equal to the sum of the estimated cost of reaching one of its successors and the cost of moving from the current node to that successor. If a heuristic function is consistent, then any algorithm that uses it to guide its search is guaranteed to find an optimal solution.

In general, consistency is a stronger condition than admissibility, as any consistent heuristic function is also admissible. However, some admissible heuristic functions may not be consistent.

Admissibility and consistency are important conditions for optimality in heuristic search algorithms, such as A* search. If the heuristic function used in the algorithm is admissible and consistent, then the algorithm is guaranteed to find the optimal solution with the lowest possible cost. If the heuristic function is not admissible or consistent, then the algorithm may not find the optimal solution or may take longer to do so.

In summary, admissibility and consistency are conditions that guarantee optimality of solutions in heuristic search algorithms. An admissible heuristic function never overestimates the actual cost of reaching the goal node, while a consistent heuristic function ensures that the estimated cost of reaching a node is always less than or equal to the sum of the estimated cost of reaching one of its successors and the cost of moving from the current node to that successor. If a heuristic function is both admissible and consistent, then any algorithm that uses it to guide its search is guaranteed to find an optimal solution.