Эвристический поиск. 
Символический искусственный интеллект: математические основы представления знаний

Исторически одним из первых и самым известным в ИИ алгоритмом для поиска оптимальных (по суммарному весу или длине) путей в графе пространства поиска считается алгоритм А* (читается как «А-звездочка», или «A-стар»). Этот алгоритм был впервые описан в 1968 г. Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем¹. В их работе он упоминается как «алгоритм А». В классическом варианте^[1][2] алгоритм А* применим в дискретном пространстве поиска, представленном^[3] графом поиска с нагруженными дугами. Этот эвристический поиск сортирует узлы графа по значению функции, которая оценивает длину кратчайшего пути, проходящего через данный узел и идущего от начального узла к одному из целевых. Таким образом, этот алгоритм сочетает в себе учет длин оптимальных путей из уже исследованной части графа поиска из алгоритма Дейкстры¹ с эвристикой наискорейшего спуска^[4][5] для еще неисследованной части графа.

Нильс Нильсен (Nils John Nilsson), родился в 1933 г. — американский ученый, один из основоположников направления и автор многих популярных книг по искусственному интеллекту.

«Искусственный интеллект ставит перед собой и более серьезную задачу построения теории интеллекта, базируйшейся на обработке информации… Поскольку построение такой общей теории пока остается в значительной степени нерешенной задачей, то мы сконцентрируем внимание на тех принципах, которые касаются инженерной задачи построения интеллектуальных машин».

• [1] Hart Р. Е., Nilsson N.J., Raphael В. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics SSC4. 1968. No. 2.P. 100−107.
• [2] Нильсон H. Принципы искусственного интеллекта.
• [3] Способы представления в программах различных математических структур обсуждаются в дополнении в конце главы.
• [4] Алгоритм Дейкстры поиска кратчайшего пути в графе описан в отступлении в этомпараграфе.
• [5] Метод наискорейшего спуска описан в п. 2.2.2.