При поиске в глубину вы начинаете с некоторого узла на графике и непрерывно исследуете его все глубже и глубже, в то время как вы можете найти новые узлы, которые еще не достигнуты (или пока не найдете решение). Каждый раз, когда у DFS заканчиваются ходы, он возвращается к последней точке, где он может сделать другой выбор, а затем исследует оттуда. Это может быть серьезной проблемой, если ваш граф очень большой и есть только одно решение, так как вы можете в конечном итоге исследовать весь граф по одному пути DFS только для того, чтобы найти решение после просмотра каждого узла. Хуже того, если график бесконечен (например, ваш график состоит из всех чисел), поиск может не завершиться. Более того, как только вы найдете нужный вам узел, у вас может не быть оптимального пути к нему (вы могли бы перебрать весь график в поисках решения, даже если он был рядом с начальным узлом!)
Одним из возможных решений этой проблемы было бы ограничение глубины любого пути, используемого DFS. Например, мы можем выполнить поиск в DFS, но остановим поиск, если мы когда-нибудь выберем путь длиной более 5. Это гарантирует, что мы никогда не исследуем ни один узел, который находится на расстоянии более пяти от начального узла, что означает, что мы никогда не исследуем бесконечно или (если граф не очень плотный), мы не ищем весь граф. Однако это означает, что мы можем не найти искомый узел, поскольку не обязательно исследовать весь граф.
Идея, лежащая в основе итеративного углубления, состоит в том, чтобы использовать этот второй подход, но продолжать увеличивать глубину на каждом уровне. Другими словами, мы могли бы попытаться исследовать, используя все пути длины один, затем все пути длины два, затем длину три и т. Д., Пока мы не найдем нужный узел. Это означает, что мы никогда не будем исследовать бесконечные тупиковые пути, поскольку длина каждого пути ограничена некоторой длиной на каждом шаге. Это также означает, что мы находим кратчайший путь к узлу назначения, так как если мы не нашли узел на глубине d, но нашли его на глубине d + 1, то не может быть пути длиной d (или мы взял бы это), поэтому путь длины d + 1 действительно оптимален.
Причина, по которой это отличается от DFS, заключается в том, что он никогда не сталкивается с тем случаем, когда он проходит чрезвычайно длинный и обходной путь вокруг графа, никогда не завершаясь. Длина путей всегда ограничена, поэтому мы никогда не исследуем ненужные ветви.
Причина, по которой это отличается от BFS, заключается в том, что в BFS необходимо одновременно хранить все дополнительные узлы в памяти. Это занимает память O (b d ), где b - коэффициент ветвления. Сравните это с использованием памяти O (d) от итеративного углубления (чтобы сохранить состояние для каждого из d узлов в текущем пути). Конечно, BFS никогда не исследует один и тот же путь несколько раз, в то время как итеративное углубление может исследовать любой путь несколько раз, так как увеличивает предел глубины. Однако асимптотически оба имеют одинаковое время выполнения. BFS завершается за O (b d ) шагов после рассмотрения всех O (b d ) узлов на расстоянии d. Итеративное углубление использует время O (b d ) на уровень, что в сумме составляет O (b d ) в целом, но с более высоким постоянным коэффициентом.
Короче говоря:
- DFS не гарантирует, что найдет оптимальный путь; итеративное углубление.
- DFS может исследовать весь граф до нахождения целевого узла; Итеративное углубление делает это, только если расстояние между начальным и конечным узлом является максимальным на графике.
- BFS и итеративное углубление выполняются в O (b d ), но итеративное углубление имеет более высокий постоянный коэффициент.
- BFS использует O (b d ) памяти, в то время как итеративное углубление использует только O (d).
Надеюсь, это поможет!