Suppose I have a admissible and consistent heuristic.
Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?
Look at this pseudocode from wikipedia:
function A*(start,goal)
closedset := the empty set // The set of nodes already evaluated.
openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node
came_from := the empty map // The map of navigated nodes.
g_score[start] := 0 // Cost from start along best known path.
// Estimated total cost from start to goal through y.
f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
while openset is not empty
current := the node in openset having the lowest f_score[] value
if current = goal
return reconstruct_path(came_from, goal)
remove current from openset
add current to closedset
for each neighbor in neighbor_nodes(current)
tentative_g_score := g_score[current] + dist_between(current,neighbor)
if neighbor in closedset
if tentative_g_score >= g_score[neighbor]
continue
if neighbor not in openset or tentative_g_score < g_score[neighbor]
came_from[neighbor] := current
g_score[neighbor] := tentative_g_score
f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
if neighbor not in openset
add neighbor to openset
return failure
I suppose it should be true. Because of this:
if current = goal
return reconstruct_path(came_from, goal)
If it wasn't true then this test would not guarantee me that the solution is optimal right?
What I don't get and the reason I am asking this question is this:
if neighbor in closedset
if tentative_g_score >= g_score[neighbor]
continue
If the neighbor is in closed list, it means that it has already been expanded. Why are they testing the scores then? Why would not the next condition work?
if neighbor in closedset
continue