Описание тега a-star
A* - алгоритм кратчайшего пути по графу, который использует эвристическую функцию для ускорения поиска.
A* - это алгоритм кратчайшего пути с одним источником, который использует эвристическую функцию для ускорения поиска. Алгоритм похож на алгоритм Дейкстры, но использует эвристическую оценку каждого узла, чтобы определить, какой узел следует исследовать в первую очередь.
Алгоритм A* является как полным [всегда найдет путь, если он существует], так и оптимальным [находит кратчайший путь], если предоставленная эвристическая функция допустима. Если существует более одного пути с одинаковой "самой низкой" оценкой стоимости, алгоритм вернет путь, исследованный первым.
Пример использования: поиск пути для агента на плоскости, похожей на сетку, от единственного источника до цели.