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:

    A country grows in history not only because of the heroism of its troops on the field of battle, it grows also when it turns to justice and to right for the conservation of its interests.
    Aristide Briand (1862–1932)

    We have need of history in its entirety, not to fall back into it, but to see if we can escape from it.
    José Ortega Y Gasset (1883–1955)

    The greatest horrors in the history of mankind are not due to the ambition of the Napoleons or the vengeance of the Agamemnons, but to the doctrinaire philosophers. The theories of the sentimentalist Rousseau inspired the integrity of the passionless Robespierre. The cold-blooded calculations of Karl Marx led to the judicial and business-like operations of the Cheka.
    Aleister Crowley (1875–1947)