Изменения

Все вершины графа перевзвешиваются и <tex>f(v) = g(v) + h(v)</tex>, где <tex>g(v) </tex> - наименьшая стоимость пути в v из стартовой вершины, <tex>h(v) </tex> - эвристическое приближение стоимости пути от v до конечной цели. <tex>h(v) </tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.К примеру, если <tex>(h(v) == 0)</tex>, то А* превращается в [http://chernykh.net/images/stories/Person/deiksteira.jpg Дейкстру ]. Если <tex>h(v)</tex> всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.