A* path cost and heuristic example

A* search expands the node with the lowest evaluation f(n) = g(n) + h(n), where g(n) is the actual path cost from the start to n, and h(n) is the heuristic (estimated) cost from n to the goal. If h(n) never overestimates the true cost (admissible), A* returns an optimal path.

Example graph

Edge costs: S-A = 1, S-B = 4, A-B = 2, A-C = 5, A-D = 12, B-C = 2, C-G = 3, D-G = 3. Goal = G.

(Admissible: the true cost from S is 8 ≥ 7, from A is 7 ≥ 6, from B is 5 ≥ 4, from C is 3 ≥ 2, from D is 3 ≥ 3.)

S(h=7) --1--> A(h=6) --2--> B(h=4) --2--> C(h=2) --3--> G
S      --4--> B
A      --5--> C
A      --12-> D(h=3) --3--> G

Execution

Solution path: S → A → B → C → G with path cost g = 1 + 2 + 2 + 3 = 8.

Other paths cost more: S-B-C-G = 9, S-A-C-G = 9, S-A-D-G = 16.

How both costs are used

• g(n) makes A* prefer cheap paths already travelled (it corrects a wrong heuristic: when D looks attractive with h = 3 its large g = 13 gives f = 16, so it is not expanded).
• h(n) steers the search towards the goal, so A* does not expand nodes in all directions like uniform-cost search.
• Together f(n) estimates the cheapest total path through n, so the first time the goal is selected for expansion, the path found is the best one.