The heuristic function ℎ(𝑛) in the A* algorithm should always underestimate the true cost to reach the goal from node 𝑛n to ensure that the algorithm remains both complete and optimal. This is known as the heuristic being admissible.
The following are the reasons why A* algorithm must be admissible:
If the heuristic is admissible (i.e., it never overestimates the true cost), A* is guaranteed to find the shortest path. This is because A* will never ignore a potentially optimal path due to an overestimated cost.
A* will always terminate and find a solution if one exists when the heuristic is admissible and the cost of each step is finite. The algorithm ensures that all possible paths are considered, and the best path is selected.