0
$\begingroup$

Taken from Artificial Intelligence A Modern Approach :

GRAPH-SEARCH

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

enter image description here

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

enter image description here

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?

$\endgroup$
2
$\begingroup$

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)

     add node.STATE to explored
     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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.