Окончательные
В очереди
Проверенные ребра

  • Текущая
  • В очереди
  • Окончательные
  • Путь
  • Оценка по прямой
Щелчок по вершине задает

Подробнее об алгоритме A*

Алгоритм A*

Алгоритм A* находит кратчайший путь от старта до цели, как алгоритм Дейкстры, но примерно знает, где цель. Каждая вершина получает оценку оставшегося расстояния — прямую до цели, и поиск всегда продолжается из вершины с наименьшей суммой расстояния на данный момент и этой оценки. Щелкните вершину, чтобы начать с нее, выберите цель и пройдите по шагам, чтобы увидеть, как поиск идет к цели и оставляет нетронутыми целые углы графа. Нажмите Пуск, чтобы посмотреть поиск, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Щелкните вершину, чтобы сделать ее стартом; переключите щелчок на Цель и щелкните другую вершину, чтобы сделать ее целью. Число на каждом ребре — его длина, число на каждой вершине — ее расстояние на данный момент, а пунктир — оценка оставшегося расстояния по прямой. Ряд под графом — это очередь, от меньшей суммы к большей, с суммой каждой вершины: расстояние на данный момент плюс оценка. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Щелкните вершину, чтобы сделать ее стартом. Переключите щелчок на Цель и щелкните другую вершину, чтобы сделать ее целью.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
  3. Следите за суммами в очереди и пунктирной оценкой по прямой. В конце сравните, сколько вершин понадобилось A* и сколько алгоритму Дейкстры.

Как работает алгоритм A*

Дайте старту расстояние 0 и поместите его в очередь. У каждой вершины в очереди есть сумма: ее расстояние на данный момент плюс оценка оставшегося расстояния. Повторяйте: возьмите вершину с наименьшей суммой и сделайте ее расстояние окончательным. Если это цель, остановитесь. Иначе для каждого соседа, чье расстояние еще не окончательное, прибавьте длину ребра к расстоянию вершины; если получилось меньше текущего расстояния соседа, уменьшите его, запомните вершину как путь к соседу и поместите соседа в очередь с новой суммой.

Почему оценка не должна быть слишком большой

A* находит кратчайший путь, пока оценка никогда не говорит, что цель дальше, чем на самом деле: такая оценка называется допустимой. Прямая — допустимая оценка, ведь никакая дорога между двумя местами не короче прямой. Слишком большая оценка может заставить A* пропустить лучший маршрут; оценка 0 везде превращает A* в алгоритм Дейкстры, который надежен, но ищет во всех направлениях. Чем лучше оценка, тем меньше вершин нужно A*. В приложении каждое ребро такой длины, как нарисовано, с округлением вверх, поэтому прямая — надежная оценка.

Часто задаваемые вопросы

Что такое алгоритм A*?

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

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

Оценка расстояния до цели, которая никогда не больше настоящего кратчайшего расстояния. С допустимой оценкой A* всегда находит кратчайший путь. Классический пример — расстояние по прямой на карте.

Быстрее ли A*, чем алгоритм Дейкстры?

Обычно да, если нужен путь к одной цели и есть хорошая оценка: A* делает окончательными меньше вершин, потому что вершины вдали от цели получают большие суммы. С оценкой 0 он делает ровно то же, что и алгоритм Дейкстры. Алгоритм Дейкстры лучше, когда нужны расстояния до всех вершин.

Где используется A*?

В видеоиграх, чтобы вести персонажей в обход препятствий, в планировщиках маршрутов, в планировании движения роботов и в программах для головоломок, таких как игра в 15, где оценка считает, насколько далеко фишки от своих мест.

Отправляется ли мой граф куда-нибудь?

Нет. Граф создается и обходится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор