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