Изменения

*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку. Чем меньше <tex>f(v)</tex>, тем раньше вершина будет открыта и исследована алгоритмом. Таким образом множество альтернативных путей хранится открытые алгоритмом вершины хранятся в очереди с приоритетомпо значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент являются наилучшими, причем алгоритм учитывает путь уже пройденный до текущей вершины.  Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой]. Если мы можем перемещаться в четырех направлениях, в качестве эвристики стоит выбрать [http://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояние]<tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.  [http://ru.wikipedia.org/wiki/Расстояние_Чебышева Расстояние Чебышева] <tex>h(v) = \max{(|{v.x-goal.x}|, |{v.y-goal.y}|)}</tex> применяется когда к четырем направлениям добавляются диагонали. Если передвижение не ограниченно сеткой, то можно использовать евклидово расстояние по прямой <tex>h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}</tex>. Также стоит обратить внимание на то как соотносятся <tex>f(v)</tex> и <tex>h(v)</tex>. Если они измеряются в разных величинах(Например, <tex>g(v)</tex> это расстояние в километрах, а <tex>h(v)</tex> {{---}} оценка времени пути в часах) А* может выдать некорректный результат.