How's A* able to abandon a non efficient path following a better one?

Consider the A* algorithm.

In Google it is possible to find a good pseudo-code:

function A*(start,goal)
     closedset := the empty set                 // The set of nodes already evaluated.     
     openset := set containing the initial node // The set of tentative nodes to be evaluated.
     came_from := the empty map                 // The map of navigated nodes.
     g_score[start] := 0                        // Distance from start along optimal path.
     h_score[start] := heuristic_estimate_of_distance(start, goal)
     f_score[start] := h_score[start]           // Estimated total distance from start to goal through y.
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset
                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x

                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
                 Update(closedset,y)  
                 Update(openset,y)  

     return failure

 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

Well there is one thing I do not understan开发者_高级运维d: Consider to have the situation in the picture:

How is A* able to change from a->b->c to a->d... ??? Well I mean, A* starts from a node and navigates through nodes. At a certain point a node have more than one neighbour, well, A* is able to follow a path generated by a neighbour, but at a certain point it is able to switch... and come back on its steps starting from a previou node and taking a different road EVEN if the abandoned path did't cross that one...

In the code, what's the condition that enables this envirinment?

A* is a generalization of Dijkstra's Algorithm, which again is a generalization of Breadth-First Search (BFS). It looks like you might be confused about the "path switching" because you think of a search operation as something resembling Depth-First Search (DFS). DFS follows a path to its end, then backtracks a little bit and tries other paths, then backtracks even further, and so on. This corresponds to how you would perform a search operation in real life (i.e., if you had to find your way out of a labyrinth). BFS, on the other hand, maintains a queue of nodes that it intends to visit. In each iteration, it picks the node from the front of the queue, examines its neighbours and adds the unvisited neighbours to the back of the queue. Then it proceeds with the next node at the front of the queue. It is not possible to do this in real life, as it would require the ability to teleport between different nodes. :-) Dijkstra and A* are based on the same idea, but they use a priority queue instead, in which you always select the "unfinished" node that is closest to the start node. So those algorithms are actually built around the idea of always switching paths: always investigate the node that presently seems to offer the best path.