Алгоритм A*

Алгоритм А*("A star", "А звёздочка") находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.

Эвристика

Все вершины графа перевзвешиваются и f(v) = g(v) + h(v), где g(v) - наименьшая стоимость пути в v из стартовой вершины, h(v) - эвристическое приближение стоимости пути от v до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.

Доказательство оптимальности и корректности

А* находит

Ссылки

• Алгоритм_поиска_A* Википедия
• A*_search_algorithm Wikipedia
• Статья о поиске кратчайших путей и различных оптимизациях А* в частности