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 failureI 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]             continueIf 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
A* optimality of the expanded node
algorithms;algorithm analysis;search algorithms;correctness proof
Please, let me contribute to this question with some observations. Most of them refer to the reply by Shaull.First, and foremost, I found that the answer provided to the question pointed to by Shaull is a little bit strange. The property of monotonicity is defined there in a strange way and indeed, I posted a question ---note I am not saying that's wrong but just strange to me and not very common and frankly speaking, I am a little bit suspicious that it might be wrong.In the original question I see various questions so let's go by steps.First, consistency is usually defined as follows [Pearl, 1984]: a heuristic $h(n)$ is consistent if and only if $h(n) \leq c(n,n') + h(n')$ for every pair of nodes $n$ and $n'$ in the state space, where $c(n,n')$ stands for the cost of the shortest path joining $n$ and $n'$. I think it is clear that admissibility (i.e., $h(n) < h^*(n)$ where $h^*(n)$ is the true optimal cost of node $n$) is immediately implied from consistency if $h(t)=0$ where $t$ is the goal node. For this and other definitions see Common Misconceptions Concerning Heuristic Search.So far, no need to say Suppose I have a admissible and consistent heuristic. It just suffices saying Suppose I have a consistent heuristic. Now, regarding your first question. If you have a consistent heuristic, there is no need to reopen nodes or, equivalently, everytime a node $n$ is expanded by A$^*$, the path discovered to it is necessarily optimal.Proof: Let us assume this is not true and after expanding node $n$ through a path $\pi\langle s, n_1, n_2, \ldots, n_k, n\rangle$ there was another path $\pi'\langle s, n'_1, n'_2, \ldots, n'_l, n\rangle$ such that $g_{\pi}(n) > g_{\pi'}(n)$. Note that $f(n)=g(n)+h(n)$ so that from our assumption $f_{\pi}(n) > f_{\pi'}(n)$ since $h(n)$ takes the same value in spite of the path followed to node $n$. But this is impossible, since $n$ was expanded as a successor or the path $\pi$ so that $f_{\pi}(n) \leq f_{\pi'}(n)$. Of course, you might say that the error was committed somewhere along the path $\pi'$ because a node $n'_i$ had such a large value of $h(n'_i)$ that it was delayed in the OPEN list, but this is impossible by definition of consistency.From here it should be obvious that the condition:if current = goal return reconstruct_path(came_from, goal)works smoothly since once the goal is about to be expanded it is guaranteed that the path discovered to it is optimal.Regarding your second question, the reason of your post, Shaull already answered in the footnotes of his reply: if the heuristic function is consistent then nodes are never reopened and your condition:if neighbor in closedset continueis enough. However, in practice, it is just simply substituted by a different condition: when expanding a node, their children are only added to OPEN if it was never expanded (not in closedset) and also, it is not already in OPEN (not in openset). With the appropriate structures for managing the open and closed list this can be done very fastly. This trick make it unnecessary to use that statement. But again, bear in mind what Shaull says, the pseudocode you show in your post is intended to work also with inconsistent heuristic functions. What you are asking for are, indeed, simplifications that result from the assumption of consistency.Hope this helps,[Pearl, 1984] Judea Pearl. Heuristics. Addison-Wesley. 1984