Алгоритм A*
Троє дослідників SRI описали пошук, що поєднує пройдену вартість із оцінкою решти шляху, і довели: за допустимої оцінки знайдений шлях оптимальний.
Чому це важливо
Евристика перестала бути здогадкою: за чіткої умови на оцінку пошук лишається і швидким, і правильним.
Алгоритм виріс із задачі планування маршруту для робота Shakey. Умова допустимості вимагає, щоб оцінка не перевищувала справжньої вартості. A* лишається базовим алгоритмом у плануванні шляху й досі; та сама ідея керованого пошуку працює і в сучасних методах на кшталт пошуку в дереві Монте-Карло. У виправленні грудня 1972 року (ACM SIGART Newsletter 37) автори пишуть, що в статті доведено допустимість A*, тобто знаходження шляху мінімальної вартості, коли він існує, якщо оцінка є нижньою межею справжньої вартості, і оптимальність за кількістю розкритих вершин за додаткового припущення про узгодженість; читач показав, що доведення оптимальності цього припущення не використовує, тож результат загальніший, а узгодженість і далі дозволяє не відкривати закриту вершину вдруге.