The value A* uses to choose the next node
In the A* algorithm, g(n) is the cost of the path from the start node to node n, and h(n) is the heuristic value of node n.
Which value does A* use to decide which node to visit next?
A the smallest g(n)
B the smallest h(n)
C the smallest g(n) + h(n)
D the largest g(n) + h(n)
[1]
- 1
Match each option to an algorithm. Choosing the smallest g(n) alone is Dijkstra's algorithm (A). Choosing the smallest h(n) alone ignores the distance already travelled (B). The largest total (D) would pick the worst node.
- 2
A* adds the cost so far to the estimated cost still to go, f(n) = g(n) + h(n), and visits the unvisited node with the smallest f(n). Answer C (1).
Answer
C
Examiner tip
Examiner tip: remember the three letters: g = cost so far, h = estimate to the goal, f = g + h. Dijkstra is A* with every h equal to 0.
Common mistake: choosing B. Following only the heuristic heads towards the goal but can choose a very long route to get there.