Звезда жадная?

2024 Автор: Lynn Donovan | [email protected]. Последнее изменение: 2023-12-15 23:52

А * (А звезда ) A * - комбинация Дейкстры и Жадный . Он использует расстояние от корневого узла плюс эвристическое расстояние до цели. Алгоритм завершается, когда мы находим целевой узел.

Кроме того, завершен ли жадный лучший первый поиск?

В итоге, жадный BFS не полный , нет оптимальный , имеет временную сложность O (bm) и пространственную сложность, которая может быть полиномиальной. A * - это полный , оптимальный , а его временная и пространственная сложность O (bm). Итак, в целом A * использует больше памяти, чем жадный BFS. A * становится непрактичным, когда поиск пространство огромно.

Кроме того, допустим ли *? Если эвристическая функция допустимый , что означает, что он никогда не переоценивает фактическую стоимость достижения цели, A * гарантированно вернет путь с наименьшими затратами от начала до цели. Тогда значение цели f является стоимостью кратчайшего пути, так как h в цели равно нулю в допустимый эвристический.

Более того, почему * лучше, чем лучший первый поиск?

A * достигает лучше производительность за счет использования эвристики, чтобы направлять ее поиск . A * сочетает в себе преимущества Лучший - первый поиск и единообразная стоимость Поиск : обеспечить нахождение оптимизированного пути при повышении эффективности алгоритма с помощью эвристики.

Алгоритм A * завершен?

A * - это полный и всегда найдет решение, если оно существует. Взгляните на статью в Википедии. Если далее эвристика допустима и монотонна, то алгоритм также будет допустимым (т. е. оптимальным).