1679
правок
Изменения
→Описание
*<tex>g(v)</tex> {{---}} наименьшая стоимость пути в <tex>v</tex> из стартовой вершины,
*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели.
Чем меньше <tex>h</tex>, тем раньше вершина будет открыта и исследована алгоритмом. Таким образом открытые алгоритмом вершины хранятся в очереди с приоритетом по значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент являются наилучшими.
Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой].
