Жадность сложность поиска в первый раз

Question

Я не могу понять, почему наихудшая временная сложность жадного поиска по принципу «лучший первый» - это O (b ^ m).

По моему мнению, жадный поиск по принципу «лучший в первую очередь» не позволяет отследить, верно? Это означает, что узлы могут расширяться только глубже и глубже. В общем, после запуска этого алгоритма должен быть только один путь, даже если путь неверный. (потому что оно неполное)

Я прав? Спасибо за ваши ответы!

Answer 1

Возможно, вы захотите посмотреть, как работает лучший сначала поиск . Он делает шаг, основанный (например) на эвристике, но может вернуться, чтобы пересмотреть это позже, если не найдет решение. Вот почему это поиск «лучший сначала», а не «только лучший». Это означает, что может произойти откат, который необходимо учитывать при анализе.