Изменения

Перейти к: навигация, поиск

Алгоритм A*

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

Навигация