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

Question

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

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

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

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

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

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

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

Answer 2

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

это дерево будет читаться

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

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

Answer 3

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

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

Answer 4

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

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

Изображение взято из книги по искусственному интеллекту Питера Норвига и СтюартаРассел