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.

Get Hands-On Artificial Intelligence for Search now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.