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

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

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

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

Функция IDDFS(root ) для  глубины от 0 до ∞ do найдено, осталось ← DLS(корень, глубина) если найдено ≠ null  , то  вернуть найдено , иначе если не осталось , то  вернуть  nullФункция DLS(узел, глубина) —  если глубина = 0 , то  если узел является целью , то  возвращается (узел, истина ) , иначе  возвращается ( ноль , истина ) (Не найдено, но могут быть дочерние элементы) иначе если глубина > 0 тогда any_remaining ← false  foreach child of node do найдено, осталось ← DLS(ребенок, глубина−1) если найдено ≠ null, то  вернуть (найдено, true ) , если осталось, то any_remaining ← true (Найден хотя бы один узел на глубине, позвольте IDDFS углубляться)  вернуть ( null , any_remaining)

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

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

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

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

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

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

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

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

Сложность времени

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

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

При итеративном углубляющем поиске узлы на глубине расширяются один раз, узлы на глубине расширяются дважды и так далее до корня дерева поиска, который расширяется раз. ^[1]^{: 5} Таким образом, общее количество расширений при итеративном углубляющем поиске равно $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), то время выполнения итеративного углубляющего поиска в глубину равно . $(1-x)^{-2}$ $\left(1-{\frac {1}{b}}\right)^{-2}$ $d$ $b>1$ $O(b^{d})$

Пример

Для и число равно $b=10$ $d=5$

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

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

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

Сложность пространства

Пространственная сложность IDDFS равна [ ^1]^{: 5,} где — глубина цели. $O(d)$ $d$

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

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

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

Пример

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

поиск в глубину, начинающийся с 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» будут просто становиться длиннее, прежде чем алгоритм сдастся и попробует другую ветвь.

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

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

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

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

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

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

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

Дополнительная сложность применения двунаправленного 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, μ) (Рекурсивное вычисление пути к узлу ретрансляции) удалить последний узел из π вернуть π B (добавить стек обратного поиска) $\circ$

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

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

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

Ссылки

^ abcdefgh Корф, Ричард (1985). «Итеративное углубление в глубину: оптимальный поиск по допустимому дереву». Искусственный интеллект . 27 : 97–109. doi :10.1016/0004-3702(85)90084-0. S2CID 10956233.
^ ab Дэвид Пул; Алан Макворт. "3.5.3 Итеративное углубление‣ Глава 3 Поиск решений ‣ Искусственный интеллект: основы вычислительных агентов, 2-е издание". artint.info . Получено 29 ноября 2018 г. .
^ abcd Рассел, Стюарт Дж.; Норвиг , Питер (2003), Искусственный интеллект: Современный подход (2-е изд.), Аппер Сэдл Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-790395-2
^ Рассел; Норвиг (1994). Искусственный интеллект: современный подход .