How would A* search a graph?

Question

An A* search will start at node S and continue to node G. At node S, the open list will contain A and B with values 7 and 6 respectively. Create a table showing the open list for each node that is visited as the A* algorithm progresses.

Can anyone explain to me how A* will search this.

open list = [S]; closed list = []
open list = [A,B]; closed list = [S]
whats next?

Answer 1

A* is a best-first algorithm, which means that it explores a graph by expanding the most promising node chosen according to a specified rule. In this case, the rule is that the most promising node is the one with the smallest f-value, where f(n) = g(n) + h(n), i.e. the sum of what was already walked (g-value) plus what our heuristic "promise" us that is the remaining of the path (h-value) is minimum.

Thus, let me write the open list in order, since generally the open list for A* is a priority queue:

it 0: open list = [S]; closed list = []

it 1: in this iteration we will have closed list = [S] and a PQ of open nodes with,
open list = 
| (B, 6) | (g = 3 + h = 3)
| (A, 7) | (g = 2 + h = 5)

after this, B is the most promising path (6 < 7) so this node will be put in the closed list,

it 2: closed list = [S,B];
open list = 
| (A, 7) | (g = 2 + h = 5)
| (D, 10) | (g = 6 + h = 4)
| (C, 11) | (g = 8 + h = 3)

and again the algorithm chooses to expand the node with lower f-value (A),

it 3: closed list = [S,B,A];
open list = 
| (C, 9) | (g = 6 + h = 3) <-- new path found with lower g-value, we update the node
| (D, 10) | (g = 6 + h = 4)

after updating the cost of the path found to C (S->A->C) which has a lower cost than (S->B->C), that node becomes the most promising for A*,

it 4: closed list = [S,B,A,C];
open list =
| (F, 9) | (g = 8 + h = 1)
| (D, 10) | (g = 6 + h = 4)
| (E, 13) | (g = 10 + h = 3)

F is now the most promising and it is expanded,

it 5: closed list = [S,B,A,C,F];
open list = 
| (G, 9) | (g = 9 + h = 0)
| (D, 10) | (g = 6 + h = 4)
| (E, 13) | (g = 10 + h = 3)

we have already added the goal node to the open list, but this doesn't mean the algorithm finishes, since there might be (not in this problem) still other paths shorter than the one already found (S->A->C->F->G). The algorithm will finish when a goal node is expanded. In the next iteration we expand again the most promising node.

it 6: we expand the goal node G.

The algorithm finishes and returns the path S->A->C->F->G with cost 9.

---

Please pay attention that your heuristic function is consistent, which means that once a node is expanded (or put to the closed list) by the A* search algorithm, the cost by which it was reached is the lowest possible (assuming no negative cost cycles). This also means that the heuristic is admissible and A* guarantees the solution found is the shortest possible path from S to G. Even more, when A* uses a consistent heuristic it is an optimal algorithm, i.e. there is no other algorithm that with the same heuristic information can expand less nodes and still guarantee to find the shortest path.