The pseudocode for A* search in 1.4.4 is as follows:
function A*-GRAPH-SEARCH(problem, frontier) return a solution or failure
reached ← an empty dict mapping nodes to the cost to each one
frontier ← INSERT((MAKE-NODE(INITIAL-STATE[problem]),0), frontier)
while not IS-EMPTY(frontier) do
node, node.CostToNode ← POP(frontier)
if problem.IS-GOAL(node.STATE) then return node
if node.STATE is not in reached or reached[node.STATE] > node.CostToNode then
reached[node.STATE] = node.CostToNode
for each child-node in EXPAND(problem, node) do
frontier ← INSERT((child-node, child-node.COST + CostToNode), frontier)
return failure
Seem that it's actually describing UCS, as heuristics are not mentioned.
CostToNode can't be the estimated total cost. If so, child-node.COST + CostToNode would make no sense. We can rename CostToNode to BackwardCost to make this clearer.
Furthermore I assume child-node.BackwardCost ← child-node.COST + node.BackwardCost is calculated in EXPAND(). We can't assign the priority popped (the estimated total cost) to BackwardCost.
I think the following would be correct:
function A*-GRAPH-SEARCH(problem, frontier) return a solution or failure
reached ← an empty dict mapping nodes to the cost to each one
initial ← INITIAL-STATE[problem]
frontier ← INSERT((MAKE-NODE(initial), initial.Heuristic), frontier)
while not IS-EMPTY(frontier) do
node ← POP(frontier)
if problem.IS-GOAL(node.STATE) then return node
if node.STATE is not in reached or reached[node.STATE] > node.BackwardCost then
reached[node.STATE] = node.BackwardCost
for each child-node in EXPAND(problem, node) do
frontier ← INSERT((child-node, child-node.BackwardCost + child-node.STATE.Heuristic), frontier)
return failure
Also I'm curious why reached is constructed in the function, but frontier is not.
The pseudocode for A* search in 1.4.4 is as follows:
Seem that it's actually describing UCS, as heuristics are not mentioned.
CostToNodecan't be the estimated total cost. If so,child-node.COST + CostToNodewould make no sense. We can renameCostToNodetoBackwardCostto make this clearer.Furthermore I assume
child-node.BackwardCost ← child-node.COST + node.BackwardCostis calculated inEXPAND(). We can't assign the priority popped (the estimated total cost) toBackwardCost.I think the following would be correct:
Also I'm curious why
reachedis constructed in the function, butfrontieris not.