Подтвердить что ты не робот

Итерационное углубление против поиска по глубине

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

Я понял, что поиск по глубине продолжается все глубже и глубже.

В итерационном углублении вы устанавливаете значение уровня, если на этом уровне нет решения, вы увеличиваете это значение и начинаете с нуля (корень).

Разве это не то же самое, что поиск по глубине?

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

4b9b3361

ОТВЕТЫ

Ответ 1

В первом поиске сначала вы начинаете с некоторого node на графике и постоянно исследуете все глубже и глубже в графике, пока вы можете найти новые узлы, которые еще не достигли (или пока не найдете решение), Каждый раз, когда DFS заканчивается, он возвращается к последней точке, где он может сделать другой выбор, а затем исследует оттуда. Это может быть серьезной проблемой, если ваш график чрезвычайно велик и существует только одно решение, так как вы можете изучить весь график по одному пути DFS, чтобы найти решение после просмотра каждого node. Хуже того, если граф бесконечен (возможно, ваш граф состоит из всех чисел, например), поиск может не завершиться. Более того, как только вы найдете node, который вы ищете, у вас может не быть оптимального пути к нему (вы могли бы зацикливаться на графике, ища решение, даже если оно было рядом с началом node! )

Одним из возможных решений этой проблемы было бы ограничить глубину любого пути, принятого DFS. Например, мы могли бы выполнить поиск по DFS, но остановим поиск, если мы когда-нибудь пройдем путь длиной больше 5. Это гарантирует, что мы никогда не будем изучать любые node расстояния более пяти с начала node, что означает что мы никогда не исследуем бесконечно или (если граф не очень плотный), мы не просматриваем весь график. Однако это означает, что мы не можем найти node, который мы ищем, поскольку мы не обязательно изучаем весь график.

Идея итеративного углубления состоит в том, чтобы использовать этот второй подход, но продолжать увеличивать глубину на каждом уровне. Другими словами, мы можем попробовать изучить все пути длины один, затем все пути длины два, затем три длины и т.д., Пока мы не найдем node. Это означает, что мы никогда не заканчиваем изучение по бесконечным тупиковым путям, так как длина каждого пути ограничена некоторой длиной на каждом шаге. Это также означает, что мы находим кратчайший путь к пункту назначения node, поскольку, если мы не нашли node на глубине 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 может исследовать весь график перед поиском цели node; итерационное углубление только делает это, если расстояние между началом и концом node является максимальным на графике.
  • BFS и итеративное углубление выполняются в O (b d), но итеративное углубление имеет более высокий постоянный коэффициент.
  • BFS использует память O (b d), а итеративное углубление использует только O (d).

Надеюсь, это поможет!

Ответ 2

В wikipedia есть достойная страница.

Основная идея, которую я думаю, вы пропустили, состоит в том, что итеративное углубление - это, прежде всего, эвристика. Когда решение, вероятно, будет найдено близко к корневому итерационному углублению, он будет считать его относительно быстрым, в то время как прямой поиск по глубине сначала может сделать "неправильное" решение и потратить много времени на бесплодную глубокую ветвь.

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

Ответ 3

Просто добавив к тому, что уже здесь, но вот несколько видео из Университета Денвера Moving AI Lab, которые показывают различия.

http://movingai.com/dfid.html

Вы можете видеть в своих примерах, что итеративное углубление выигрывает, когда цель является неглубокой (глубина решения 3, глубина дерева), и решение находится справа, но DFS выигрывает независимо от того, что, если решение находится в последней строке.

В этом чтении я рассказывал о программировании шахмат, а затем я думал о quiescence search проверить это, если вы хотите узнать больше о стратегиях поиска для программирования ИИ.