Графы-2x: алгоритм поиска пути A*

Введение

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

Реализация

Была написана реализация, отталкивающаяся от тех же принципов, что и ранее созданная реализация алгоритма Дейкстры. Итак, функция-шаблон, реализующая алгоритм А*, принимает следующие параметры (слова в кавычках, описывают поведение объектов, а не реальное представление их в памяти):

  • (вывод) ссылку на «массив» предшественников Pr, после выполнения алгоритма Pr[v] == u, если вершина с индексом v стоит сразу за вершиной с индексом u на искомом пути;
  • (ввод) ссылку на «матрицу» весов рёбер графа;
  • (ввод) ссылку на «массив» наборов смежности, каждый набор должен представлять собой STL-последовательность с input-итератором;
  • (ввод) индексы начальной и конечной (целевой) вершин искомого пути;
  • (ввод) количество вершин графа;
  • (ввод) эвристика, реализованная как бинарный функтор, принимающий два индекса вершин графа и возвращающий оценку расстояния;
  • (ввод, опционально) политика демонстрации работы алгоритма, предназначенная для визуализации (подробнее в AV-2).

Функция возвращает истину, если путь был найден, ложь в противном случае.

Основное отличие алгоритма поиска A* от алгоритма Дейкстры состоит в том, что при выборе ещё не пройденных вершин приоритет отдаётся тем вершинам, которые минимизируют сумму веса уже известного на момент пути (хранится в массиве gscore) и оценки остатка пути до целевой вершины. Эти суммы хранятся в массиве fscore, который используется компаратором ByArrayComparator при сравнении индексов вершин, помещаемых в объект openset (имеющий тип std::set<unsigned, ByArrayComparator<(…)>>).

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

Эта очередь называется «открытым множеством» (openset). Вершины, извлечённые из открытого множества, попадают в «закрытое множество» (closedset), после чего они уже не могут попасть в открытое множество.

Известно, что если эвристика даёт оценку кратчайшего пути снизу ( такая эвристика называется «допустимой» ), то алгоритм поиска A* находит кратчайший путь. В частности, эвристика может всегда возвращать 0, в этом случае алгоритм А* будет эквивалентен алгоритму Дейкстры с остановом при достижении целевой вершины.

С другой стороны, алгоритм А* позволяет ускорить процесс поиска с возможной потерей оптимальности результирующего пути. Известно, что если эвристика даёт оценку кратчайшего пути, которая не больше, чем в q раз превосходит вес реального кратчайшего пути, то алгоритм А* находит путь веса не более, чем в q раз большего, чем кратчайший путь (субоптимальное решение).

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

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: