Admissibility of an algorithm typically refers to whether a search algorithm is guaranteed to find an optimal solution, assuming one exists. An admissible algorithm always finds the least-cost path to the goal (the optimal solution) if such a path exists. For example, in pathfinding problems, an admissible algorithm ensures that the path found is the shortest or has the least cost among all possible paths.
In the context of heuristic search algorithms, such as A* (A-star), admissibility is closely tied to the heuristic function used. For A* to be admissible, the heuristic function ℎ(𝑛) (which estimates the cost from node 𝑛 to the goal) must be optimistic, meaning it never overestimates the actual cost. In other words, it must always underestimate the cost. Formally, this is written as:
ℎ(𝑛)≤ℎ∗(𝑛), where ℎ∗(𝑛) is the true cost from node 𝑛 to the goal.
Admissibility is crucial in applications where finding the best possible solution is important, such as in routing, game playing (e.g., chess), and various optimization problems.
Let us understand overestimation and underestimation with an example.
Example of Overestimation:
Let’s suppose, you are going to purchase shoes and shoes have a price of $1000. Before making the purchase, you estimated that the shoes would be worth $1200, When you went to the store, the shopkeeper informed you that the shoe’s actual price was $1000, which is less than your estimated value, indicating that you had overestimated their value by $200. so this is the case of Overestimation.
1200 > 1000, i.e., h(n) ≥ h*(n)
∴ Overestimation
Example of Underestimation:
Similar to the last situation, you are planning to buy a pair of shoes. This time, you estimate the shoe value to be $800. However, when you arrive at the store, the shopkeeper informs you that the shoes’ true price is $1000, which is higher than your estimate, indicating that you had underestimated their value by $200. In this situation, Underestimation has occurred.
800 < 1000, i.e., h(n) ≤ h*(n)
∴ Underestimation
Now, let us understand this in a bit more detail with the help of A* Algorithm.
In the graph above, X is the start node and Y is the goal node. In between these two nodes there are intermediate nodes A and, B and all values which are in the above diagram are actual cost values means h*(n).
Overestimation
Let’s suppose,
H(A)= 60
H(B)= 50
So, using A* equation, f(n) = G(n) + h(n)
by putting values
f(A) = 100 + 60 = 160
f(B) = 100 + 50 = 150
by comparing f(A) & f(B), f(A) > f(B) so choose path of B node and apply A* equation again
f(Y) = g(Y) + h(Y) [here h(Y) is 0, Goal state]
= 140 + 0 [g(Y)=100+40=140 this is actual cost i.e. h*(B)]
= 140
The least cost to get from X to Y, as shown in the mentioned graph is 130, however, in Case 1, we took into consideration the expected costs h(n) of A & B, which were 60 & 50, respectively. As a result, 140 > 130 according to the Overestimation condition h(n) ≥ h*(n), and here, since the value of node f(A) is bigger than f(Y), we are unable to proceed along a different path which is from node A.
Underestimation
Let’s suppose,
H(A) = 20 [This are estimated values i.e. h(n)]
H(B) = 10
So, using A* equation, f(n) = G(n) + h(n)
by putting values
f(A) = 100 + 20 = 120
f(B) = 100 + 10 = 110, by comparing f(A) & f(B), f(A) > f(B), so choose path of B node and apply A* equation again
f(Y) = g(Y) + h(Y) [here h(Y) is 0, because it is goal state]
= 140 + 0 [g(Y) = 100 + 40 = 140 this is actual cost i.e. h*(B)]
= 140
Now, notice that f(Y) is the same in both circumstances but, in 2nd case by comparing the f(A) with f(Y) i.e. 120 < 140 as it means we can go from node A. Therefore A* will go with f(A), which has a value of 120.