A* Search

In the preceding section, you learned that the path found by a greedy BFS is as follows:

Figure 19

The total distance covered is 14.24. However, the actual optimal solution is shown in the following diagram:

Figure 20

The total distance covered is 12. This means that the greedy BFS algorithm is not optimal. The problem is that the heuristic function doesn't consider the costs already incurred. A* Search proposes a new heuristic function, which computes the sum of the cost incurred and the estimated cost to reach the goal state.

For our application, the heuristic function can compute the sum of the distance traveled from the root node to the current node, and the straight line distance to the goal state. Let's look at the example that we saw in the previous section and compute this new heuristic function for the three nodes Car Park, Bus Stop, and Student...