1. Problem Model
- How shortest-path problems are modeled
- State representation in graph search
- The role of path cost
- The role of heuristic estimation
- The evaluation function of A*
A* operates on a formal model of search where the goal is to find an optimal path between two nodes in a weighted graph.
Understanding this model is essential before analyzing the algorithm itself.
1.1 Graph Model
The problem is defined over a weighted graph:
where each edge has an associated cost:
The objective is to find a minimum-cost path from a start node s to a goal node t.
1.2 State Representation
Each node in the graph corresponds to a state in the search space.
A state contains:
- current node
- accumulated path cost
- parent reference (for reconstruction)
The algorithm explores states by expanding neighbors.
1.3 Path Cost
The function g(n) represents the exact cost from the start node to n.
It is computed incrementally as the search progresses.
This is the same cost function used in Dijkstra’s algorithm.
1.4 Heuristic Estimate
The function h(n) estimates the remaining cost from n to the goal.
It is not exact, but provides directional guidance.
The effectiveness of A* depends heavily on this estimate.
1.5 Evaluation Function
A* evaluates nodes using:
This represents the estimated total cost of a solution path passing through node n.
The algorithm expands the node with the smallest value of f(n).
1.6 Key Insight
A* balances two components:
- g(n): cost already incurred
- h(n): estimated remaining cost
This allows A* to interpolate between:
- Dijkstra (when h(n) = 0)
- Greedy Search (when g(n) is ignored)
Next: Part 2 — Heuristic Functions
The heuristic function is the core component that makes A* an informed search algorithm.
In the next part, we formalize what heuristics are, how they guide the search, and introduce key properties such as admissibility and consistency.