Эффективный поиск в графах: от Uniform Cost Search к алгоритму A* 2:02
В современных задачах искусственного интеллекта и программирования поиск оптимального решения зачастую требует не только глубоких знаний структуры проблемы, но и эффективных алгоритмов, способных учитывать ограничения. В шестой лекции курса CS221 Стэнфордского университета, посвященной теме «Поиск II», основной акцент был сделан на развитии методов поиска, которые позволяют находить минимальную стоимость пути в графах, содержащих циклы.
Поиск с равномерной стоимостью (UCS) 6:00
Uniform Cost Search (UCS), известный также как алгоритм Дейкстры, является фундаментальным методом поиска, который позволяет эффективно работать в графах с циклами, при условии, что все веса ребер неотрицательны. В отличие от динамического программирования, где поиск осуществляется «от конца к началу» (на основе будущих затрат), UCS фокусируется на вычислении прошлых затрат — минимальной стоимости пути от начального состояния до текущего.
Основные характеристики и механика UCS:
- Стратегия обработки: Состояния процесса разделяются на три группы: исследованные (explored), границы (frontier) и еще не исследованные.
- Приоритизация: Алгоритм использует очередь с приоритетами (priority queue) для выбора состояния с наименьшей накопленной стоимостью (past cost).
- Оптимальность: Как утверждает лектор, приоритет в очереди в точности соответствует минимальной стоимости пути до этого состояния.
- Гарантии: При неотрицательных весах ребер UCS гарантированно находит путь с минимальной стоимостью, так как «расширение» границ происходит равномерно, не допуская необоснованного пропуска оптимальных маршрутов.
Тем не менее, у UCS есть существенный недостаток: он абсолютно не «осведомлен» о том, где находится целевое состояние. Из-за этого алгоритм тратит вычислительные ресурсы на исследование всех направлений, что в больших графах делает поиск крайне медленным.
Революция A*: введение эвристик 30:47
Для решения проблемы неэффективности UCS был представлен алгоритм A (A-Star). Его главная идея заключается в использовании эвристики* — функции $h(n)$, которая аппроксимирует будущую стоимость пути от текущего состояния до цели.
A* по своей сути является «умной» версией UCS, где стоимость каждого действия модифицируется с учетом эвристического прогноза.
- Модификация затрат: К исходной стоимости действия добавляется изменение эвристики: $h(\text{successor}) - h(\text{current})$.
- Направленность: Благодаря эвристике алгоритм «смещается» в сторону цели, эффективно игнорируя бесперспективные участки графа.
- Условие корректности: Чтобы A сохранял гарантию поиска оптимального решения, эвристика должна быть согласованной* (consistent). Это означает, что модифицированные стоимости ребер должны оставаться неотрицательными.
Искусство создания эвристик: релаксация проблем 57:13
Создание хорошей эвристики — это часто задача конкретной предметной области. Однако лектор предложил универсальный методологический подход: релаксация (расслабление) задачи.
Принцип релаксации заключается в намеренном удалении определенных ограничений исходной проблемы, что делает ее значительно проще для решения. Ключевые способы реализации этого принципа:
- Удаление физических препятствий: Например, игнорирование стен в сетке (манхэттенское расстояние как эвристика).
- Изменение стоимости действий: Например, предоставление бесплатных «билетов» на транспорт, чтобы не учитывать их лимит в состоянии системы.
- Разделение задач: Сведение сложной задачи (например, пятнашки) к сумме нескольких независимых подзадач, где плитки могут накладываться друг на друга.
По мнению лектора, любая эвристика, полученная как будущая стоимость «расслабленной» проблемы, автоматически будет обладать свойством согласованности, что избавляет исследователя от необходимости сложных математических доказательств.
