Поиск A*

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

Подробнее: A* оценивает каждый узел по f = g + h. Здесь g — известная стоимость от старта, h — оценка оставшегося расстояния до цели. Следующим рассматривается узел с наименьшим f.