Различие между Поиском в ширину и Повторяющимся углублением
Я понимаю BFS и DFS, но ни за что в жизни не могу выяснить различие между повторяющимся углублением и BFS. По-видимому Повторяющееся углубление имеет то же использование памяти как DFS, но я не могу видеть, как это возможно, поскольку это просто продолжает расширяться как BFS. Если бы кто-либо может разъяснить, что это было бы потрясающим.
дерево, чтобы продолжить работать при необходимости:
A
/ \
B C
/ / \
D E F
2 ответа
Насколько я понимаю, итеративное углубление выполняет DFS до глубины 1, затем выполняет DFS до глубины 2 ... до глубины n, и так далее, пока не будет найдено больше уровней
, например, я думаю, что это дерево будет be read
read visited depth
A A 1
ABC ABAC 2
ABDCEF ABDBACECF 3
Я считаю, что это в значительной степени создание отдельной DFS с ограничением глубины для каждого уровня и отбрасывание памяти.
Насколько я понимаю алгоритм, IDDFS (итеративный поиск с углублением в глубину) - это просто поиск в глубину, выполняемый несколько раз, увеличивая уровень узлов, поиск которых выполняется на каждой итерации.Следовательно, требования к памяти такие же, как и при поиске в глубину, поскольку итерация максимальной глубины - это просто полный поиск в глубину.
Следовательно, для примера дерева, которое вы дали, первая итерация посетит узел A, вторая итерация посетит узлы A, B и C, а третья итерация посетит все узлы дерева.
Причина, по которой он реализован таким образом, заключается в том, что, если поиск имеет временные ограничения, тогда алгоритм будет, по крайней мере, иметь некоторое представление о том, что такое узел "хорошей оценки", если он достигнет временного ограничения, прежде чем выполнять полный обход дерева.
Это отличается от поиска в ширину, потому что на каждой итерации узлы посещаются точно так же, как при поиске в глубину, а не как при поиске в ширину. Как правило, алгоритмы IDDFS, вероятно, будут хранить «лучший результат», найденный на каждой итерации.