Как работает алгоритм 'A Star' для поиска кратчайшего пути?

Алгоритм A* (A Star) ищет кратчайший путь между вершинами, основываясь на стоимости и «весе» рёбер. 1 Он пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. 2

Алгоритм разделяет все вершины на три категории: 1

1. Неизвестные вершины. 1 Это те, которые ещё не были посещены и не найдены. 1 Изначально все вершины, кроме стартовой, будут в этой категории. 1
2. Известные вершины. 1 Это те, о которых уже известно алгоритму и есть путь к ним. 1 Такие вершины сохраняются в «списке алгоритма» и становятся в очередь для их посещения и исследования. 1 Из этого списка исследуются те вершины, которые считаются наиболее перспективными. 1
3. Исследованные вершины. 1 В эту категорию попадают те вершины, которые уже были посещены алгоритмом A*. 1 К этим вершинам известен самый короткий путь, поэтому они попадают в «закрытый список» — этот список нужен для того, чтобы исключить многократное исследование одних и тех же вершин. 1

На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа — множеством частных решений, — которое размещается в очереди с приоритетом. 2 Приоритет пути определяется по значению f(x) = g(x) + h(x). 2

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

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