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

Question

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

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

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

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

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

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

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

Answer 2

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

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

Причина, по которой он реализован, заключается в том, что, если у поиска есть ограничение во времени, то у алгоритма, по крайней мере, есть какое-то представление о том, что является узел «хорошей оценки», если он достигнет ограничения по времени, прежде чем пройти полное обход дерево.

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

Answer 3

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

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

Answer 4

В каждой итерации итерационного поиска у нас есть предел, и мы пересекаем график, используя подход DFS, однако для каждого этапа каждой итерации нам просто нужно отслеживать только узлы внутри пути от корня до глубины D Анкет Это сохранение в памяти.

Например, посмотрите на последний ряд изображения ниже. Если бы мы использовали BFS, мы должны были отслеживать все узлы до глубины 2. Но, поскольку мы используем DFS, нам не нужно держать все в памяти, так как какие -либо узлы уже посещаются, так что мы не посещаем Нужны они, или еще не посетили, поэтому мы добавим его позже. Мы просто держим свой путь к корню (серый путь).

Картина из книги искусственного интеллекта Питера Норвига и Стюарта Рассела