Алгоритм A* — различия между версиями
| Строка 1: | Строка 1: | ||
Алгоритм '''А*'''("A star", "А звёздочка") находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной. | Алгоритм '''А*'''("A star", "А звёздочка") находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной. | ||
| − | =Доказательство оптимальности и корректности= | + | ==Эвристика== |
| − | =Оценка времени работы= | + | Все вершины графа перевзвешиваются и f(v) = g(v) + h(v), где g(v) - наименьшая стоимость пути в v из стартовой вершины, h(v) - эвристическое приближение стоимости пути от v до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку. |
| − | =Применение= | + | ==Псевдокод== |
| + | |||
| + | ==Доказательство оптимальности и корректности== | ||
| + | А* находит | ||
| + | ==Оценка времени работы== | ||
| + | ==Применение== | ||
Версия 20:17, 31 октября 2011
Алгоритм А*("A star", "А звёздочка") находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Содержание
Эвристика
Все вершины графа перевзвешиваются и f(v) = g(v) + h(v), где g(v) - наименьшая стоимость пути в v из стартовой вершины, h(v) - эвристическое приближение стоимости пути от v до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
Псевдокод
Доказательство оптимальности и корректности
А* находит
