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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Поиск источников: «Итеративный поиск с углублением в глубину» - новости · газеты · книги · ученый · JSTOR ( январь 2017 г. ) ( Узнайте, как и когда удалить это шаблонное сообщение )

Итеративный поиск в глубину с углублением
Класс	Алгоритм поиска
Структура данных	Дерево , График
Наихудшая производительность	${\ Displaystyle О (Ь ^ {d})}$ , где - коэффициент ветвления, - глубина самого мелкого решения ${\ displaystyle b}$ ${\ displaystyle d}$
Сложность пространства в наихудшем случае	${\ displaystyle O (d)}$ ^[1]^{: 5}

Алгоритмы поиска по графам и деревьям
α – β А * B * Возврат Луч Беллман – Форд Лучший первый Двунаправленный Борувка Ветвь и граница BFS британский музей D * DFS Дейкстра Эдмондс Флойд – Уоршалл Поиск бахромы скалолазание ИДА* Итеративное углубление Джонсон Точка прыжка Крускал Лексикографическая BFS LPA * Прим SMA *
Списки
Алгоритмы графа Алгоритмы поиска Список алгоритмов графа
похожие темы
Динамическое программирование Обход графа Обход дерева Искать игры
v т е

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

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

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

функция IDDFS (корень) предназначена  для глубины от 0 до ∞ do найдено, осталось ← DLS (корень, глубина) если найдено ≠ нуль ,  то  возвращение нашел еще , если не оставаясь затем  возвращать  нульфункция DLS (узел, глубина) -  если глубина = 0, тогда  если узел является целью, тогда  return (node, true ) иначе  return ( null , true ) (Не найден, но могут иметь потомков) иначе , если глубина> 0 , то any_remaining ← ложно  Еогеасп ребенок из узла дел найдено, осталось ← DLS (дочерний элемент, глубина − 1) если найдено ≠ null, то  вернуть (найдено, true ) если осталось, то any_remaining ← true (На глубине найден хотя бы один узел, пусть IDDFS углубится)  return ( null , any_remaining)

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

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

Свойства [ править ]

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

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

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

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

Асимптотический анализ [ править ]

Сложность времени [ править ]

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

Доказательство [ править ]

При итеративном поиске с углублением узлы на глубине расширяются один раз, узлы на глубине расширяются дважды и так далее до корня дерева поиска, который расширяется раз. ^[1]^:⁵ Таким образом, общее количество расширений в итеративном поиске с углублением равно ${\ displaystyle d}$ ${\ displaystyle d-1}$ ${\ displaystyle d + 1}$

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

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

{\ displaystyle b ^ {d} (1 + 2b ^ {- 1} + 3b ^ {- 2} + \ cdots + (d-1) b ^ {2-d} + db ^ {1-d} + ( г + 1) б ^ {- г})}

Теперь давай . Тогда у нас есть ${\ displaystyle 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

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

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

Космическая сложность [ править ]

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

Доказательство [ править ]

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

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

Пример [ править ]

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

поиск в глубину, начиная с 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: A, B, C, E

(Итеративное углубление теперь показало C, тогда как обычный поиск в глубину - нет.)

2: A, B, D, F, C, G, E, F

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

3: A, B, D, F, E, C, G, E, F, B

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

Связанные алгоритмы [ править ]

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

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

Двунаправленная IDDFS [ править ]

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

Одним из ограничений алгоритма является то, что кратчайший путь, состоящий из нечетного числа дуг, не будет обнаружен. Предположим, у нас есть кратчайший путь. Когда глубина достигнет двух скачков по дугам, прямой поиск продолжится от , а обратный поиск продолжится от до . Графически границы поиска будут проходить друг через друга, и вместо этого будет возвращен неоптимальный путь, состоящий из четного числа дуг. Это показано на следующих диаграммах: $\langle s,u,v,t\rangle .$ $v$ $u$ $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, μ) (Рекурсивно вычислить путь к узлу ретрансляции) удалить последний узел из π вернуть π B (добавить стек обратного поиска) $\circ$

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

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

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

Ссылки [ править ]

^ Б с д е е г Корф, Richard E. (1985). «Итеративное углубление в глубину» (PDF) . Cite journal requires |journal= (help)
^ Корф, Ричард (1985). «Итеративное углубление в глубину: поиск оптимального допустимого дерева». Искусственный интеллект . 27 : 97–109. DOI : 10.1016 / 0004-3702 (85) 90084-0 .
^ Дэвид Пул; Алан Макворт. «3.5.3 Итеративное углубление Глава 3 Поиск решений ‣ Искусственный интеллект: основы вычислительных агентов, 2-е издание» . artint.info . Проверено 29 ноября 2018 .
^ a b c d Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-790395-2
^ Рассел; Норвиг (1994). Искусственный интеллект: современный подход .

[re1985-1] Б с д е е г Корф, Richard E. (1985). «Итеративное углубление в глубину» (PDF) . Cite journal requires |journal= (help)

[2] Корф, Ричард (1985). «Итеративное углубление в глубину: поиск оптимального допустимого дерева». Искусственный интеллект . 27 : 97–109. DOI : 10.1016 / 0004-3702 (85) 90084-0 .

[3] Дэвид Пул; Алан Макворт. «3.5.3 Итеративное углубление Глава 3 Поиск решений ‣ Искусственный интеллект: основы вычислительных агентов, 2-е издание» . artint.info . Проверено 29 ноября 2018 .

[rn3-4] Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-790395-2

[5] Рассел; Норвиг (1994). Искусственный интеллект: современный подход .

[1]