The A* search algorithm is a widely used pathfinding and graph traversal algorithm in artificial intelligence and computer science. It combines the strengths of Dijkstra's algorithm and Greedy Best-First Search to efficiently find the shortest path between two nodes in a graph. The key to its efficiency lies in the use of a heuristic cost function.
Definition of Heuristic Cost Function
In A* search, the heuristic cost function, denoted as $$ h(n) $$, is an estimate of the cost to reach the goal from a given node $$ n $$. The total cost function $$ f(n) $$ used by A* is defined as:
$$ f(n) = g(n) + h(n) $$
where:
$$ g(n) $$ is the actual cost from the start node to the current node $$ n $$.
$$ h(n) $$ is the heuristic estimate of the cost from node $$ n $$ to the goal.
The heuristic function $$ h(n) $$ must be admissible, meaning it never overestimates the true cost to reach the goal. This ensures that A* will always find the optimal path if one exists.
Properties of a Good Heuristic Function
A useful heuristic function should have the following properties:
Admissibility: The heuristic should never overestimate the cost to reach the goal, i.e., $$ h(n) \leq \text{true cost} $$.
Consistency (Monotonicity): For every node $$ n $$ and its successor $$ n' $$, the estimated cost should satisfy $$ h(n) \leq c(n, n') + h(n') $$, where $$ c(n, n') $$ is the cost to move from $$ n $$ to $$ n' $$. Consistency implies admissibility.
Non-negativity: The heuristic value should be non-negative.
Zero at Goal: The heuristic value should be zero at the goal node, i.e., $$ h(\text{goal}) = 0 $$.
Calculating a Heuristic Function
The heuristic function is problem-specific and often based on domain knowledge. Here are some common methods to calculate heuristic functions:
Euclidean Distance: Used in spatial problems where the cost is the straight-line distance between two points.
$$
h(n) = \sqrt{(x_{\text{goal}} - x_n)^2 + (y_{\text{goal}} - y_n)^2}
$$
Manhattan Distance: Used in grid-based problems where movement is restricted to horizontal and vertical directions.
$$
h(n) = |x_{\text{goal}} - x_n| + |y_{\text{goal}} - y_n|
$$
Chebyshev Distance: Used in grid-based problems where diagonal movement is allowed.
$$
h(n) = \max(|x_{\text{goal}} - x_n|, |y_{\text{goal}} - y_n|)
$$
Domain-Specific Heuristics: For specific problems like the 8-puzzle, heuristics such as the number of misplaced tiles or the sum ...
