---
title: "A* path cost and heuristic example"
subject: "Artificial Intelligence"
chapter: 3
key: "semester_6/artificial_intelligence:a-star-path-cost-heuristic"
source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/a-star-path-cost-heuristic
site: BCT Engineering
---

# A* path cost and heuristic example

Artificial Intelligence · Chapter 3: Search Techniques

- Asked in: 2073 Magh, 8 marks
- Video: [A* Search | A Star Search algorithm Solved Example in Artificial Intelligence by Magesh Huddar](https://www.youtube.com/watch?v=lusRf5v-TI0) — Mahesh Huddar
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/a-star-path-cost-heuristic
- Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-3

## Question

Devise an example to show how the A* algorithm uses path cost and heuristic cost to generate the best solution.

## Short answer

A* expands nodes with lowest f(n) = g(n) + h(n), combining actual path cost with an admissible heuristic. In the example, it expands S, A, B, C, G and returns the optimal path S-A-B-C-G with path cost 8, beating paths costing 9 and 16.

## Answer

**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.

| Node | S | A | B | C | D | G |
|---|---|---|---|---|---|---|
| h(n) | 7 | 6 | 4 | 2 | 3 | 0 |

(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.)

```text
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
| Step | Node expanded | Generated nodes: g, h, f = g + h |
|---|---|---|
| 1 | S (f = 7) | A: g=1, h=6, f=**7**; B: g=4, h=4, f=8 |
| 2 | A (f = 7) | B via A: g=1+2=3, f=3+4=**7** (cheaper than 4, replaces old B); C: g=6, f=8; D: g=13, f=16 |
| 3 | B (g=3, f = 7) | C via B: g=3+2=5, f=5+2=**7** (better than 6) |
| 4 | C (g=5, f = 7) | G: g=5+3=8, h=0, f=**8** |
| 5 | G (f = 8, lowest in open list) | Goal reached |

**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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does A* use to pick the node to expand?
   A. f(n) = h(n)
   B. f(n) = g(n)
   C. f(n) = g(n) + h(n), the lowest first
   D. f(n) = g(n) - h(n), the highest first
   Answer: C. A* expands the node with the lowest f = g + h, the actual cost so far plus the estimated cost to the goal. (Key point: A* evaluation function)

2. In the example, D has h = 3 but is never expanded. Why?
   A. Its h value is too large
   B. Its large path cost g = 13 gives f = 16, much higher than other nodes
   C. D is not connected to the goal
   D. A* ignores nodes with h > 0
   Answer: B. g(n) penalises expensive paths already travelled, so D's f = 13 + 3 = 16 is not competitive. (Key point: Role of g(n))

3. What path and cost does A* return in the example?
   A. S-B-C-G, cost 9
   B. S-A-C-G, cost 9
   C. S-A-B-C-G, cost 8
   D. S-A-D-G, cost 16
   Answer: C. Via S-A-B-C-G the cost is 1 + 2 + 2 + 3 = 8, the cheapest. (Key point: Final path)

4. When is the first goal selected for expansion guaranteed optimal?
   A. When h overestimates the cost
   B. When h is admissible (never overestimates the true cost)
   C. When h = 0 for all nodes
   D. When all edges cost 1 only
   Answer: B. With an admissible heuristic, A* returns an optimal path. (Key point: Optimality condition)

## Related in Artificial Intelligence

- [Greedy best-first drawbacks; A*](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Agreedy-best-first-vs-astar) — Artificial Intelligence, chapter 3

## Related in other subjects

- [Linear solution techniques; CG algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asolution-techniques-cg-algorithm) — Computational Techniques in Civil Engineering, chapter 2
- [Dijkstra's shortest path algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adijkstra-algorithm-example) — Data Structure and Algorithm, chapter 10, asked 2×
- [TOH problem with solution for n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-n-disks-solution) — Data Structure and Algorithm, chapter 5, asked 2×
- [IRR choose best of four, 10-year study](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Airr-choose-best-abcd-study-10) — Engineering Economics, chapter 4