Искусственный интеллект: временная сложность НБА * Поиск

Question

Я изучаю алгоритмы информированного поиска, и для нового двунаправленного поиска A * я знаю, что сложность пространства равна O (b ^ d), где d - глубина самого мелкого целевого узла, а b - коэффициент ветвления.Я пытался выяснить, какова его временная сложность, но я не смог найти точную информацию об этом на онлайн-ресурсах.Является ли точное время сложности NBA * Поиск неизвестно и в чем разница между оригинальным двунаправленным A *?Любые идеи приветствуются.

Answer 1

Если у вас есть конкретные модели вашей проблемы (например, равномерно растущий граф в обоих направлениях с удельными затратами на единицу и числом состояний, растущим экспоненциально), тогда большинство алгоритмов двунаправленного поиска требуют O (b ^ (d / 2)) расширений узлов и требуется время O (b ^ (d / 2)). Но эта простая модель не является реальной моделью большинства реальных проблем.

Учитывая это, я бы не рекомендовал прилагать значительные усилия для изучения Нового Двунаправленного A *.

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

Были предложены другие варианты алгоритмов NBS, такие как DVCBS , которые следуют той же базовой структуре, не имеют тех же гарантий, но хорошо работают на практике.