Алгоритм A* — различия между версиями
| Строка 8: | Строка 8: | ||
==Оценка времени работы== | ==Оценка времени работы== | ||
==Применение== | ==Применение== | ||
| + | ==Ссылки== | ||
| + | *[http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Алгоритм_поиска_A* Википедия] | ||
| + | *[http://en.wikipedia.org/wiki/A*_search_algorithm A*_search_algorithm Wikipedia] | ||
| + | *[http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей и различных оптимизациях А* в частности] | ||
| + | |||
| + | [[Категория: Алгоритмы и структуры данных]] | ||
| + | [[Категория: Кратчайшие пути в графах ]] | ||
Версия 19:11, 2 ноября 2011
Алгоритм А*("A star", "А звёздочка") находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Содержание
Эвристика
Все вершины графа перевзвешиваются и f(v) = g(v) + h(v), где g(v) - наименьшая стоимость пути в v из стартовой вершины, h(v) - эвристическое приближение стоимости пути от v до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
Псевдокод
Доказательство оптимальности и корректности
А* находит
