Алгоритмы и структуры данных

Алгоритм А*

Используется для поиска кратчайшего пути. A* сочетает в себе элементы алгоритма Дейкстры и жадного поиска по принципу «наилучшее первое» для поиска оптимального пути с учетом предполагаемой стоимости.

Ключевые идеи:
⁃ Эвристическая функция h(n):
Оценивает стоимость от текущего узла до цели. Эвристика помогает эффективно направлять поиск к цели.
⁃ Функция стоимости g(n):
Представляет фактическую стоимость от начального узла до текущего узла.
⁃ Общая стоимость f(n):
представляет собой сумму функции стоимости и эвристики: f(n) = g(n) + h(n).

Временная сложность алгоритма A* зависит от эвристики. В худшем случае, число вершин, исследуемых алгоритмом, растёт экспоненциально по сравнению с длиной оптимального пути, но сложность становится полиномиальной, когда эвристика удовлетворяет следующему условию:
| h(n) - h*(n) | <= O (log h*(x))
где h* — оптимальная эвристика, то есть точная оценка расстояния из вершины x к цели.

www.tgoop.com/the_algorithms/4595

5.7K viewsNov 7, 2023 at 09:03

Алгоритм А*

Используется для поиска кратчайшего пути. A* сочетает в себе элементы алгоритма Дейкстры и жадного поиска по принципу «наилучшее первое» для поиска оптимального пути с учетом предполагаемой стоимости.

Ключевые идеи:
⁃ Эвристическая функция h(n):
Оценивает стоимость от текущего узла до цели. Эвристика помогает эффективно направлять поиск к цели.
⁃ Функция стоимости g(n):
Представляет фактическую стоимость от начального узла до текущего узла.
⁃ Общая стоимость f(n):
представляет собой сумму функции стоимости и эвристики: f(n) = g(n) + h(n).

Временная сложность алгоритма A* зависит от эвристики. В худшем случае, число вершин, исследуемых алгоритмом, растёт экспоненциально по сравнению с длиной оптимального пути, но сложность становится полиномиальной, когда эвристика удовлетворяет следующему условию:
| h(n) - h*(n) | <= O (log h*(x))
где h* — оптимальная эвристика, то есть точная оценка расстояния из вершины x к цели.

BY Алгоритмы и структуры данных