# How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more

Taken from Artificial Intelligence A Modern Approach :

Notice how a node doesn't gets added to the frontier twice in Graph-Search, And then take a look at this :

Now obviously this is not true as in the following example :

Bucharest will be added to the frontier first with path sibiu->fagaras->bucharest, while the second path which is more optimal will be omitted.

Am i missing something or is just a false claim?

A* isn't based on the GRAPH-SEARCH algorithm but on the UNIFORM-COST-SEARCH one:

function UNIFORM-COST-SEARCH(problem) returns a solution or failure
node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
frontier ← a priority queue ordered by PATH-COST,
with node as the only element
explored ← an empty set

loop do
if EMPTY?(frontier) then return failure

node ← POP(frontier)  /* chooses the lowest-cost node in frontier */
if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

for each action in problem.ACTIONS(node.STATE) do
child ← CHILD-NODE(problem, node, action)
if child.STATE is not in explored or frontier then
frontier ← insert(child, frontier)
else if child.STATE is in frontier with higher PATH-COST then
replace that frontier node with child


Uniform cost search algorithm is identical to the general graph search algorithm (in your question) except:

• for the use of a priority queue and
• the addition of en extra check in case a shorter path to a frontier state is discovered.

A* is identical to UNIFORM-COST-SEARCH except that uses $g + h$ instead of $g$.

So assuming the following distances (straight-line distance to Bucharest) for the h heuristic function:

Sibiu          253     Fagaras 176
Rimnicu Vilcea 193     Pitesti 100
Bucharest        0


the second path will NOT be omitted. Stages in an A* search for Bucharest are (numbers show $f = g + h$):

(a) Sibiu 0 + 253 = 253
(b) Fagaras = 99 + 176 = 275, Rimnicu Vilcea = 80 + 193 = 273
(c) Pitesti = 177 + 100 = 277
(d) Bucharest (via Fagaras) = 310 + 0 = 310


A* search keeps going, choosing Pitesti for expansion:

(e) Bucharest (via Pitesti) = 278 + 0 = 278