Разница между первым поиском по ширине и итерационным углублением

Я понимаю BFS и DFS, но для жизни я не могу понять разницу между итерационным углублением и BFS. Очевидно, что итеративное углубление имеет такое же использование памяти, как и DFS, но я не могу понять, как это возможно, поскольку он просто расширяется, как BFS. Если кто-нибудь сможет прояснить это, это будет потрясающе.

дерево для работы, если необходимо:

    A
   / \
  B   C
 /   / \
D   E   F

Ответы

Ответ 1

Из того, что я понимаю, итерационное углубление делает DFS до глубины 1, тогда DFS доходит до глубины 2... до глубины n и т.д., пока не найдет больше уровней

Например, я думаю, что дерево будет считаться

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

Я считаю, что он в значительной степени делает отдельную DFS с ограничением глубины для каждого уровня и выбрасывает память.

Ответ 2

Из моего понимания алгоритма IDDFS (поиск по глубине с углублением глубины) - это просто поиск по глубине, выполняемый несколько раз, углубление уровня узлов, поиск на каждой итерации. Поэтому требования к памяти такие же, как поиск по глубине, потому что максимальная итерация глубины - это всего лишь полный поиск по глубине.

Поэтому для примера дерева, которое вы указали, первая итерация посетила бы node A, вторая итерация посетила бы узлы A, B и C, а третья итерация посетила бы все узлы дерева.

Причина, по которой это реализовано, заключается в том, что если поиск имеет ограничение по времени, то алгоритм, по крайней мере, будет иметь представление о том, что такое "хороший выигрыш" node, если он достигнет предельного срока до делая полный обход дерева.

Это отличается от поиска по ширине, потому что на каждой итерации узлы посещаются так же, как они были бы в поиске по глубине, а не в первом поиске. Как правило, алгоритмы IDDFS, вероятно, сохраняют "лучший результат" node, найденный с каждой итерации.

Ответ 3

использование памяти - это максимальное количество узлов, которое она сохраняет в любой точке. а не количество посещенных узлов.

в любое время, когда IDFS необходимо хранить только узлы в ветки, они расширяются. Только A и C, если мы расширяем C (например, в вашем примере). BFS должен сохранять все узлы глубины, которую он ищет. для просмотра эффекта возьмите дерево с коэффициентом ветвления 8, а не 2. для поиска на глубину 3, BFS должен хранить массивные 64 узла. Для IDFS требуется только 3.