Definition
A heuristic function (algorithm) or simply a heuristic is a shortcut to solving a problem when there are no exact solutions for it or the time to obtain the solution is too long.
Speed vs Accuracy
From the definition, we can conclude that the goal is to find a faster solution or an approximate one, even if it is not optimal. In other words, when using a heuristic, we trade accuracy for the speed of the solution.
For example, greedy algorithms usually produce quick but sub-optimal solutions. A greedy algorithm to find the largest sum in the following tree would go for the red path while the optimal path is the green one:
Admissible Heuristic
Heuristics don’t always lead to a lower cost. However, those that don’t overestimate the true or the lowest possible cost of a solution are called admissible heuristics. This characteristic can guarantee the optimality of the solution. An admissible heuristic can be found by simplifying the original problem in terms of its constraints, reducing it to a less constrained problem. As an example, let’s consider the eight puzzle problem:
We start from the state on the left, and we want to reach the goal state on the right. As a heuristic solution to this puzzle, we can think of the Hamming distance between the two states, which is the number of misplaced tiles highlighted in green. Here, we have relaxed the constraints of the problem by assuming that we can just pick up a tile and put it in its right place.
This solution is admissible (i.e., it is a lower bound) in that the optimal solution can not have fewer steps than this one.