top of page

When do we say that the search is admissible? You can take the example of A*.

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.



242 views0 comments

Commentaires


bottom of page