Изменения
Нет описания правки
Алгоритм '''А*'''("A star", "А звёздочка") находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
==Эвристика==Все вершины графа перевзвешиваются и f(v) = g(v) + h(v), где g(v) - наименьшая стоимость пути в v из стартовой вершины, h(v) - эвристическое приближение стоимости пути от v до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.==Псевдокод== ==Доказательство оптимальности и корректности==А* находит ==Оценка времени работы====Применение==
