Допустимая эвристика
term_id: admissible_heuristic
Category: basic_concepts
Definition
В задачах поиска путей и поиска в целом допустимая эвристика даёт нижнюю оценку фактической стоимости достижения целевого узла. Гарантируя, что оценочная стоимость всегда меньше или равна
Summary
Эвристическая функция в алгоритмах поиска, которая никогда не переоценивает истинную стоимость достижения цели, обеспечивая оптимальность.
Key Concepts
- Нижняя граница
- Гарантия оптимальности
- Поиск A*
- Оценка стоимости
Use Cases
- Планирование маршрутов в GPS-навигации
- Решение головоломок (например, головоломка 8-панелей)
- Планирование движения робота в среде с множеством препятствий