Explain what is heuristic cost function in A* Search and how to calculate one?

A* Search relies on a knowledge and heuristic cost function for the given node as a way to decide which node it should visit next. In most cases, this cost function is denoted as f(x).

The cost function is calculated as a sum of two other functions:

• g(x) – The function that represents the cost of moving from the starting node to a given node.
• h(x) – The estimated cost from the given node to the goal node.
• f(x) = g(x)+h(x)

We obviously don’t know the exact movement cost from the given note to the goal node, which is the reason why h(x) is also often referred to as the “heuristic”.

The calculation of h(x) can be done in various ways:

• The Manhattan distance from node n to the goal is often used. This is a standard heuristic for a grid. It’s measured as he distance between two points measured along axes at right angles. In a plane with p1 at (x1, y1) and p2 at (x2, y2), it is |x1 - x2| + |y1 - y2|.

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy)

• The Euclidean Distance Heuristic. If your units can move at any angle (instead of grid directions), then you should probably use a straight line distance:

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * sqrt(dx * dx + dy * dy)

• If h(x) = 0, A* becomes Dijkstra’s algorithm, which is guaranteed to find a shortest path.

The heuristic function must be:

• admissible, h(x) <= dist(x, t), which means it can never overestimate the cost to reach the goal. Both the Manhattan distance and h(x) = 0 are admissible.
• monotone, h(u) <= cost(u, v) + h(v) (triangle inequality)
• It must be cheap to compute. It should be certainly O(1), and should preferably look at the current node alone.

The algorithm always picks the node with the lowest f(x) value. The fewer steps we take from the starting point combined with how close we get to the goal makes the value of f(x) lower if we’re going with the shortest path to the goal. Walking away from the goal, and making more steps than needed to get there increases the f(x) function.