A brief introduction to the A* algorithm

We'll now look at how an A* algorithm works. In this algorithm, we'll calculate two costs. We'll be taking four pieces of input: our start state (a set of implicitly given states), a state transition operator, a goal state, and the heuristic value of each node. Based on those, we'll be calculating our actual cost, g(n) (which we also calculated in our Dijkstra's algorithm). Along with the actual cost, we'll calculate one more cost: the final cost (f(n)). The final cost will be the actual cost plus the heuristic cost (h(n)). The formula is as follows:

In the preceding formula, the following applies:

• g(n) is the actual cost of traversing from the initial state to state n
• h(n) is the estimated cost of reaching the goal from state n

We are given the following information:

[S,s,O,G,h]

In the preceding...