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

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

Сорт	Алгоритм поиска
Структура данных	Дерево , График
Худшая производительность	$O(b^{d})$, где $b$ является фактором ветвления и $d$ это глубина самого мелкого раствора
Наихудшая пространственная сложность	$O(d)$
Оптимальный	да (для невзвешенных графиков)

В информатике — итеративный поиск с углублением или, точнее, итеративный поиск в глубину с углублением. (IDS или IDDFS) — это стратегия поиска в пространстве состояний /графе, в которой ограниченная по глубине версия поиска в глубину запускается повторно с увеличением пределов глубины, пока цель не будет найдена. IDDFS оптимален, что означает, что он находит самую поверхностную цель. Поскольку он посещает все узлы дерева поиска вплоть до глубины $d$ перед посещением каких-либо узлов на глубине $d+1$, совокупный порядок первого посещения узлов фактически такой же, как и при поиске в ширину . Однако IDDFS использует гораздо меньше памяти.

Алгоритм для ориентированных графов

Следующий псевдокод показывает IDDFS, реализованную в виде рекурсивной DFS с ограниченной глубиной (называемой DLS) для ориентированных графов . Эта реализация IDDFS не учитывает уже посещенные узлы.

функция  IDDFS(root)  предназначена      для  глубины  от  0  до  ∞  do         найдено, осталось ← DLS(корень, глубина)         если  найдено ≠  ноль   , то              вернуть  найденное         иначе, если  не осталось  ,              верните   нулевую  функцию  DLS (узел, глубина)  ,      если  глубина = 0,  тогда,          если  узел является целью  , тогда              верните  (узел,  true  )         else              return  (  null  ,  true  )  (не найден, но может иметь дочерние элементы)      else, если  глубина > 0  , то         Any_remaining  false          foreach  дочерний  узел  ←  do             найдено, осталось ← DLS(дочерний, глубина-1)             если  найдено ≠ ноль,  то                  вернуть  (найдено,  правда  )                если  останется  , то                 Any_remaining ← true  (найден хотя бы один узел на глубине, позвольте IDDFS углубиться)          return  (  null  , Any_remaining) 

Если целевой узел найден DLS , IDDFS вернет его, не заглядывая глубже. В противном случае, если хотя бы один узел существует на этом уровне глубины, оставшийся флаг позволит IDDFS продолжить работу.

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

Характеристики

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

Итеративные углубленные посещения штатов проводятся несколько раз, и это может показаться расточительным. Однако если IDDFS исследует дерево поиска на глубину $d$, большая часть общих усилий направлена ​​на глубокое изучение состояний $d$. Относительно количества состояний на глубине $d$, стоимость повторного посещения состояний выше этой глубины всегда невелика.

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

Второе преимущество — оперативность алгоритма. Поскольку ранние итерации используют небольшие значения для $d$, они выполняются чрезвычайно быстро. Это позволяет алгоритму практически сразу же предоставлять ранние сведения о результате с последующими уточнениями по мере необходимости. $d$ увеличивается. При использовании в интерактивной обстановке, например, в программе для игры в шахматы , эта возможность позволяет программе играть в любое время с текущим лучшим ходом, найденным в результате поиска, который она завершила на данный момент. Это можно сформулировать так: каждая глубина поиска корекурсивно . обеспечивает лучшее приближение решения, хотя работа, выполняемая на каждом этапе, является рекурсивной Это невозможно при традиционном поиске в глубину, который не дает промежуточных результатов.

Асимптотический анализ

Временная сложность

Временная сложность IDDFS в (хорошо сбалансированном) дереве оказывается такой же, как и при поиске в ширину, т.е. $O(b^{d})$, где $b$ является фактором ветвления и $d$ это глубина цели.

Доказательство

При итеративном поиске с углублением узлы на глубине $d$ расширяются один раз, те, что на глубине $d-1$ расширяются дважды и так далее до корня дерева поиска, которыйрасширенный $d+1$ раз. Таким образом, общее количество расширений в итеративном поиске с углублением равно

$b^{d}+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^{2}+db+(d+1)=\sum _{i=0}^{d}(d+1-i)b^{i}$

где $b^{d}$ количество расширений на глубине $d$, $2b^{d-1}$ количество расширений на глубине $d-1$, и так далее. Факторинг $b^{d}$ дает

$b^{d}(1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+db^{1-d}+(d+1)b^{-d})$

Теперь позвольте $x={\frac {1}{b}}=b^{-1}$. Тогда у нас есть

$b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})$

Это меньше, чем бесконечная серия

$b^{d}(1+2x+3x^{2}+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)$

который сходится к

$b^{d}(1-x)^{-2}=b^{d}{\frac {1}{(1-x)^{2}}}$, для $abs(x)<1$

То есть у нас есть

$b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})\leq b^{d}(1-x)^{-2}$, для $abs(x)<1$

С $(1-x)^{-2}$ или $\left(1-{\frac {1}{b}}\right)^{-2}$ является константой, не зависящей от $d$ (глубина), если $b>1$ (т. е. если коэффициент ветвления больше 1), время выполнения итеративного поиска с углублением в глубину равно $O(b^{d})$.

Пример

Для $b=10$ и $d=5$ номер

$\sum _{i=0}^{5}(5+1-i)10^{i}=6+50+400+3000+20000+100000=123456$

В общем, итеративный углубляющийся поиск из глубины. $1$ вплоть до глубины $d$ расширяется только примерно $11\%$ больше узлов, чем один поиск в ширину или с ограничением по глубине $d$, когда $b=10$.

Чем выше коэффициент ветвления, тем меньше накладные расходы на многократно расширяемые состояния. но даже когда коэффициент ветвления равен 2, итеративный поиск с углублением занимает примерно вдвое больше времени, чем полный поиск в ширину. Это означает, что временная сложность итеративного углубления по-прежнему велика. $O(b^{d})$.

Пространственная сложность

Пространственная сложность IDDFS составляет $O(d)$, где $d$ это глубина цели.

Доказательство

Поскольку IDDFS в любой момент выполняет поиск в глубину, ему нужно хранить только стек узлов, который представляет ветвь дерева, которое он расширяет. Поскольку он находит решение оптимальной длины, максимальная глубина этого стека равна $d$, и, следовательно, максимальный объем пространства равен $O(d)$.

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

Пример

Для следующего графика:

поиск в глубину, начиная с A, предполагая, что левые ребра в показанном графе выбраны раньше правых ребер, и предполагая, что поиск запоминает ранее посещенные узлы и не будет повторять их (поскольку это небольшой граф), посетит узлы в следующем порядке: A, B, D, F, E, C, G. Ребра, пройденные в этом поиске, образуют дерево Тремо — структуру, имеющую важные применения в теории графов .

Выполнение того же поиска без запоминания ранее посещенных узлов приводит к посещению узлов в порядке A, B, D, F, E, A, B, D, F, E и т. д. навсегда, попадая в A, B, D, F. , цикл E и никогда не достигает C или G.

Итеративное углубление предотвращает этот цикл и достигает следующих узлов на следующих глубинах, при условии, что оно происходит слева направо, как указано выше:

• 0: А
• 1: А, Б, В, Е

(Теперь при итеративном углублении появился C, а при обычном поиске в глубину — нет.)

• 2: А, Б, Г, Ж, В, Г, Е, Ж

(Он по-прежнему видит C, но появился позже. Кроме того, он видит E по другому пути и дважды возвращается к F.)

• 3: А, Б, Г, Ж, Е, С, Г, Е, Ж, Б

Для этого графика по мере увеличения глубины два цикла «ABFE» и «AEFB» просто станут длиннее, прежде чем алгоритм сдастся и попробует другую ветвь.

Связанные алгоритмы

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

Итеративное углубление A* — это поиск по принципу «наилучшее первое», который выполняет итеративное углубление на основе значений « f », аналогичных тем, которые вычислены в алгоритме A* .

Двунаправленный IDDFS

IDDFS имеет двунаправленный аналог, который чередует два поиска: один начинается с исходного узла и движется по направленным дугам, а другой начинается с целевого узла и продолжается по направленным дугам в противоположном направлении (от головного узла дуги к хвостовому узлу дуги). Процесс поиска сначала проверяет, что исходный узел и целевой узел совпадают, и если это так, возвращает тривиальный путь, состоящий из одного исходного/целевого узла. В противном случае процесс прямого поиска расширяет дочерние узлы исходного узла (установите $A$), процесс обратного поиска расширяет родительские узлы целевого узла (установите $B$), и проверяется, $A$ и $B$ пересекаться. Если да, то кратчайший путь найден. В противном случае глубина поиска увеличивается и выполняются те же вычисления.

Одним из ограничений алгоритма является то, что кратчайший путь, состоящий из нечетного числа дуг, не будет обнаружен. Предположим, у нас есть кратчайший путь $\langle s,u,v,t\rangle .$ Когда глубина достигнет двух прыжков по дугам, прямой поиск будет продолжаться от $u$ к $v$, и обратный поиск будет продолжаться от $v$ к $u$. Графически границы поиска будут проходить друг через друга, а вместо этого будет возвращен неоптимальный путь, состоящий из четного числа дуг. Это показано на диаграммах ниже:

Двунаправленный IDDFS

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

Дополнительная сложность применения двунаправленной IDDFS заключается в том, что если исходный и целевой узлы находятся в разных сильно связанных компонентах, скажем, $s\in S,t\in T$, если нет ухода дуги $S$ и входя $T$, поиск никогда не завершится.

Временные и пространственные сложности

Время работы двунаправленной IDDFS определяется выражением

$2\sum _{k=0}^{n/2}b^{k}$

а пространственная сложность определяется выражением

$b^{n/2},$

где $n$ количество узлов в кратчайшем $s,t$-путь. Поскольку сложность времени выполнения итеративного поиска в глубину с углублением равна $\sum _{k=0}^{n}b^{k}$, ускорение примерно

${\frac {\sum _{k=0}^{n}b^{k}}{2\sum _{k=0}^{n/2}b^{k}}}={\frac {\frac {1-b^{n+1}}{1-b}}{2{\frac {1-b^{n/2+1}}{1-b}}}}={\frac {1-b^{n+1}}{2(1-b^{n/2+1})}}={\frac {b^{n+1}-1}{2(b^{n/2+1}-1)}}\approx {\frac {b^{n+1}}{2b^{n/2+1}}}=\Theta (b^{n/2}).$

Псевдокод

функция  Build-Path(s, μ, B  )     π ← Find-Shortest-Path(s, μ)  (Рекурсивно вычислить путь к узлу ретрансляции)     удалить последний узел из π     вернуть  π $\circ$ B  (добавить стек обратного поиска) 

функция  Depth-Limited-Search-Forward(u, Δ, F)  - это      если  Δ = 0  , то         Ф ← Ф $\cup$ {u}  (отметьте узел)          return      foreach  child  of  u  do         Глубина-Ограниченный-Поиск-Вперед (дочерний, Δ - 1, F) 

функция  Depth-Limited-Search-Backward(u, Δ, B, F)  равна     добавить тебя к букве B     если  Δ = 0  , то          если  u  в  F  ,              верните  u  (достиг отмеченного узла, используйте его как узел ретрансляции)         удалить головной узел B         вернуть значение null      для каждого  родителя,  который  вы  делаете         μ ← Поиск с ограниченной глубиной назад (родительский, Δ − 1, B, F)         если  ц $\neq$ null   , затем              верните  μ    удалить головной узел B     вернуть ноль 

функция  Find-Shortest-Path(s, t)  —     если  s = t,  то         возвращает  <s>   F, B, Δ ← ∅, ∅, 0    навсегда делать        Поиск-вперед с ограниченной глубиной(s, Δ, F)        foreach  δ = Δ, Δ + 1  do            μ ← Поиск с ограниченной глубиной назад (t, δ, B, F)            если  ц $\neq$ null, затем                 верните  Build-Path(s, μ, B)  (найден узел ретрансляции)        F, Δ ← ∅, Δ + 1