A* Search Algorithm - History

History

In 1968 Nils Nilsson suggested a heuristic approach for Shakey the Robot to navigate through a room containing obstacles. This path-finding algorithm, called A1, was a faster version of the then best known formal approach, Dijkstra's algorithm, for finding shortest paths in graphs. Bertram Raphael suggested some significant improvements upon this algorithm, calling the revised version A2. Then Peter E. Hart introduced an argument that established A2, with only minor changes, to be the best possible algorithm for finding shortest paths. Hart, Nilsson and Raphael then jointly developed a proof that the revised A2 algorithm was optimal for finding shortest paths under certain well-defined conditions. They thus named the new algorithm in Kleene star syntax to be the algorithm that starts with A and includes all possible version numbers or A*.

Read more about this topic:  A* Search Algorithm

Famous quotes containing the word history:

    Books of natural history aim commonly to be hasty schedules, or inventories of God’s property, by some clerk. They do not in the least teach the divine view of nature, but the popular view, or rather the popular method of studying nature, and make haste to conduct the persevering pupil only into that dilemma where the professors always dwell.
    Henry David Thoreau (1817–1862)

    Anything in history or nature that can be described as changing steadily can be seen as heading toward catastrophe.
    Susan Sontag (b. 1933)

    What we call National-Socialism is the poisonous perversion of ideas which have a long history in German intellectual life.
    Thomas Mann (1875–1955)