top of page
Dhruv Badaya

Why should the heuristic function of A* algorithm always underestimate? Give reason, example.

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.

56 views0 comments

Comentários


bottom of page