Эвристический поиск и A*

Эвристический поиск использует специфическую для задачи оценку оставшейся стоимости до цели, чтобы определить, какие состояния исследовать в первую очередь; A* является его каноническим алгоритмом, расширяющим состояния в порядке суммы уже понесенных затрат и оценочных затрат до цели.

Definition

Эвристический поиск — это информированный поиск, который упорядочивает границу с помощью оценочной функции, объединяющей известную стоимость от начала с эвристической оценкой оставшейся стоимости; A* использует f(n) = g(n) + h(n) и является оптимальным, когда h допустима.

Scope

Эта тема охватывает информированные (эвристические) стратегии поиска, сосредоточенные на поиске по первому наилучшему совпадению и алгоритме A*, включая разработку и свойства эвристических функций (допустимость, согласованность/монотонность), гарантии оптимальности и эффективности, которые эти свойства обеспечивают, а также варианты с ограниченной памятью, такие как итеративное углубление A* (IDA*). В ней рассматривается, как строятся эвристики (ослабленные задачи, базы данных шаблонов) и как они соотносят точность с вычислительными затратами. Изучение эвристик на основе данных относится к подобласти машинного обучения.

Core questions

• Что делает эвристику допустимой и почему допустимость гарантирует оптимальность A*?
• Как согласованность (монотонность) усиливает гарантии и предотвращает повторное расширение узлов?
• Как разрабатываются хорошие эвристики, например, из ослабленных версий задачи?
• Как варианты с ограниченной памятью, такие как IDA*, сохраняют оптимальность при ограниченном пространстве?

Key concepts

• оценочная функция f = g + h
• допустимая эвристика
• согласованная (монотонная) эвристика
• жадный поиск по первому наилучшему совпадению
• поиск A*
• итеративное углубление A* (IDA*)
• эвристическое доминирование
• ослабленная задача и базы данных шаблонов

Key theories

Оптимальность A* при допустимых эвристиках

Когда эвристика h никогда не переоценивает истинную оставшуюся стоимость, A* расширяет узлы по возрастанию f = g + h и гарантированно возвращает путь с наименьшей стоимостью; среди алгоритмов, использующих ту же эвристическую информацию, A* является оптимально эффективным.

Разработка эвристик через ослабление

Допустимые эвристики могут быть систематически получены путем решения ослабленной версии задачи (той, которая имеет меньше ограничений на действия), поскольку точная стоимость более простой задачи является нижней границей для исходной; доминирующие (более информированные) эвристики расширяют меньше узлов.

Эвристический поиск с ограниченной памятью

Итеративное углубление A* выполняет последовательные поиски в глубину, ограниченные возрастающим порогом стоимости f, достигая оптимальности, подобной A*, с памятью, линейной по глубине решения.

Clinical relevance

Эвристический поиск используется для определения маршрутов на картах и в играх, планирования движений в робототехнике, а также в поисковых системах автоматизированных планировщиков и решателей головоломок; практическое искусство разработки эвристик напрямую определяет, могут ли большие задачи быть решены за приемлемое время.

History

Алгоритм A* был представлен Хартом, Нильссоном и Рафаэлем (1968), что дало эвристическому поиску формальную основу оптимальности. Монография Перла 1984 года «Эвристики» (Heuristics) предоставила окончательную теоретическую трактовку, а IDA* Корфа 1985 года решила проблему затрат памяти A*. Эти результаты остаются основным материалом в образовании по искусственному интеллекту.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

Что такое допустимая эвристика?

Эвристика является допустимой, если она никогда не переоценивает истинную стоимость достижения цели из любого состояния. Допустимость — это условие, при котором A* гарантированно находит оптимальное (наименее затратное) решение.

В чем разница между жадным поиском по первому наилучшему совпадению и A*?

Жадный поиск по первому наилучшему совпадению расширяет состояние, которое кажется ближайшим к цели только по эвристике (h), что быстро, но может быть далеко от оптимального. A* добавляет фактическую стоимость, понесенную до сих пор (g), расширяя по f = g + h, что сохраняет оптимальность, когда эвристика допустима.