Node Evaluation Process

The Core Formula: f(n) = g(n) + h(n)

At every step, A* must make an informed decision: "Which node should I explore next?" This formula is the engine behind that decision, determining the exploration order. By summing the actual cost incurred so far and the estimated cost remaining, A* balances accuracy (G) with ambition (H).

• g(n): This is the accumulated cost from the start node to the current node n. It represents the path we have already traveled, which is known and fixed.
• h(n): This is the heuristic estimate—the "educated guess"—of the cost from node n to the goal node.
• f(n): The total estimated cost of the cheapest path through node n.

The Philosophy of Evaluation

A* is effectively a Best-First Search. By constantly picking the node with the lowest f(n) from the openSet, the algorithm prioritizes paths that appear promising overall. If h(n) is accurate and admissible, this strategy is mathematically guaranteed to find the absolute shortest path while ignoring less promising areas of the graph.

Detailed Evaluation Cycle

1. Initialization: The start node is evaluated. Its g cost is 0, its h cost is calculated via the chosen heuristic, and its f value is h itself. It is then added to the openSet.
2. Selection (The "Focus" Step): In each iteration, A* scans the openSet and identifies the node with the lowest f(n). If multiple nodes have the same f(n), a common tie-breaking strategy is to pick the node with the lowest h(n) (the one closest to the goal).
3. Expansion (Node Processing): The selected node is moved from the openSet to the closedSet. It is now "visited" and finalized.
4. Neighbor Assessment: For each unvisited neighbor m of the current node:
   • Calculate a tentative g value: current.g + cost(current, neighbor).
   • If the neighbor is already in the openSet and the new tentative g is higher than the existing g for that node, ignore this path; it is inefficient.
   • If the neighbor is new or this new path has a lower g, update the neighbor: set its parent to the current node, update its g, h, and f values, and add/update it in the openSet.

Step-by-Step Example

Imagine navigating a 3x3 grid from (0,0) to (2,2) with a cost of 1 per move (no diagonal movement). Let's evaluate a node at (0,1) with a goal at (2,2).

• g(n): We moved from (0,0) to (0,1). The cost is 1.
• h(n): Using Manhattan Distance: |0-2| + |1-2| = 2 + 1 = 3.
• f(n): 1 + 3 = 4.

If another node at (1,0) has g=1, h=3, its f is also 4. A* will pick one arbitrarily (or based on tie-breaking) to expand first.