Алгоритм A*
Алгоритм Дейкстры находит кратчайший путь к цели, но ищет во всех направлениях сразу, даже в сторону от цели. Алгоритм A* добавляет одно знание — оценку того, как далеко еще до цели, — и поиск вдруг идет прямо к ней.
Идея
Когда вы ищете маршрут на карте, вы не изучаете дороги, ведущие прочь от места назначения, так же тщательно, как дороги, ведущие к нему. Алгоритм A* делает то же самое. Каждая вершина получает сумму: расстояние от старта на данный момент, g, плюс оценку оставшегося расстояния, h. Поиск всегда продолжается из вершины с наименьшей суммой, поэтому вершины, лежащие в сторону цели, идут первыми.
Шаг за шагом
Дайте старту расстояние 0 и поместите его в очередь с суммой h(start). Повторяйте: возьмите вершину с наименьшей суммой и сделайте ее расстояние окончательным. Если это цель, остановитесь: пройдя назад по запомненным вершинам, вы получите путь. Иначе для каждого соседа, чье расстояние еще не окончательное, вычислите его расстояние через эту вершину. Если оно меньше текущего, уменьшите его, запомните эту вершину как путь к соседу и дайте соседу сумму его нового расстояния и его оценки. При равных суммах выбор вершины с меньшей оценкой обычно быстрее приводит к цели.
Пример
Пусть старт — A, а цель — D. Длина A–B равна 2 и B–D — 2, а A–C — 1 и C–D — 5. Оценки по прямой до D: 3 от A, 2 от B и 3 от C. A начинает с суммой 0 + 3 = 3. Взятие A дает B сумму 2 + 2 = 4, а C — сумму 1 + 3 = 4. При равенстве A* берет B, вершину с меньшей оценкой, и B дает D сумму 4 + 0 = 4. Теперь у D наименьшая сумма и наименьшая оценка, поэтому ее берут: кратчайший путь — A → B → D длиной 4, а C, которая ведет не туда, так и не получает окончательного расстояния. Алгоритм Дейкстры сначала сделал бы окончательной C, потому что это ближайшая к A вершина.
Хорошая оценка
Оценка никогда не должна быть больше настоящего расстояния до цели; такая оценка называется допустимой, и с ней A* всегда находит кратчайший путь. Прямая допустима, потому что никакой маршрут не короче прямой. Если к тому же оценка никогда не уменьшается больше чем на длину ребра при переходе от одной вершины к следующей, она согласованная, и ни одну вершину с окончательным расстоянием никогда не придется рассматривать заново. Чем ближе оценка к истине, тем меньше вершин нужно A*. Оценка 0 допустима, но бесполезна: тогда A* становится алгоритмом Дейкстры. Слишком большая оценка ускоряет A*, но может пропустить кратчайший путь.
История и применение
Питер Харт, Нильс Нильссон и Бертрам Рафаэл из Stanford Research Institute опубликовали A* в 1968 году, работая над роботом Shakey, одним из первых мобильных роботов. Их более ранние версии назывались A1 и A2; звездочка отмечала версию, оптимальность которой они доказали. Сегодня A* ведет персонажей в обход препятствий в видеоиграх, планирует маршруты и движения роботов и решает головоломки, такие как игра в 15, где оценка складывает, насколько далеко каждая фишка от своего места.
Попробуйте сами
Откройте приложение и нажмите Шаг. Числа на ребрах — их длины, которые здесь соответствуют тому, какой длины они нарисованы, а пунктир показывает оценку по прямой до цели. Очередь под графом перечисляет вершины по сумме, начиная с наименьшей. Когда расстояние цели становится окончательным, строка состояния сравнивает, сколько вершин сделал окончательными A*, с тем, сколько понадобилось бы алгоритму Дейкстры. Выберите цель в дальнем углу большого графа, чтобы увидеть наибольшую разницу.
Часто задаваемые вопросы
Что означает звездочка в A*?
Харт, Нильссон и Рафаэл сначала описали алгоритмы, которые назвали A1 и A2. A* («A звездочка») — версия, о которой они доказали, что она находит кратчайший путь, раскрывая меньше всего вершин среди сравнимых алгоритмов с той же оценкой, если оценка согласованная.
Какова временная сложность A*?
В худшем случае, с бесполезной оценкой, A* выполняет ту же работу, что и алгоритм Дейкстры: O((V + E) log V) с двоичной кучей. С хорошей оценкой он делает окончательными лишь часть вершин, поэтому на практике работает быстро.
Какая эвристика хороша для A*?
Она должна быстро вычисляться, никогда не завышать настоящее расстояние и быть к нему как можно ближе. На сетке, где можно двигаться только вверх, вниз, влево и вправо, обычно выбирают манхэттенское расстояние; на карте — расстояние по прямой.
Что, если эвристика завышает расстояние?
Тогда A* может вернуть путь, который не самый короткий, потому что может закончить раньше, чем рассмотрит лучший маршрут. Некоторые программы делают это намеренно (взвешенный A*), чтобы немного пожертвовать качеством пути ради большой скорости.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать алгоритм A*