Algorithms For Dummies

Going heuristically around by A*

The A* algorithm speedily produces best shortest paths in a graph by combining 

the Dijikstra greedy search discussed in Chapter 9 with an early stop (the algo-

rithm stops when it reaches its destination vertex) and a heuristic estimate (usu-

ally based on the Manhattan distance) that hints at the graph area to explore first. 

A* was developed at the Artificial Intelligence Center of Stanford Research Insti-

tute (now called SRI International) in 1968 as part of the Shakey the robot project. 

Shakey was the first mobile robot to autonomously decide how to go somewhere 

(although it was limited to wandering around a few rooms in the labs). To render 

---

CHAPTER 20