Эта статья требует дополнительных ссылок для проверки . ( январь 2017 г. ) ( Узнайте, как и когда удалить это шаблонное сообщение ) |
Класс | Алгоритм поиска |
---|---|
Структура данных | Дерево , График |
Наихудшая производительность | , где - коэффициент ветвления, - глубина самого мелкого решения |
Сложность пространства в наихудшем случае | [1] : 5 |
Алгоритмы поиска по графам и деревьям |
---|
Списки |
|
похожие темы |
|
В информатике итеративный поиск с углублением или, более конкретно , итеративный поиск с углублением в глубину [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]
Второе преимущество - скорость отклика алгоритма. Поскольку в ранних итерациях используются небольшие значения для , они выполняются очень быстро. Это позволяет алгоритму практически сразу предоставлять ранние признаки результата с последующими уточнениями по мере увеличения. При использовании в интерактивной обстановке, например, в программе для игры в шахматы , эта возможность позволяет программе играть в любое время с текущим лучшим ходом, найденным в ходе поиска, который она завершила на данный момент. Это можно сформулировать так: каждая глубина поиска совместно рекурсивно дает лучшее приближение решения, хотя работа, выполняемая на каждом шаге, является рекурсивной. Это невозможно при традиционном поиске в глубину, который не дает промежуточных результатов.
Асимптотический анализ [ править ]
Сложность времени [ править ]
Временная сложность из IDDFS в (хорошо сбалансированный) дерево работает, чтобы быть таким же , как поиск в ширину, то есть , [1] : 5 , где это коэффициент ветвления и является глубина цели.
Доказательство [ править ]
При итеративном поиске с углублением узлы на глубине расширяются один раз, узлы на глубине расширяются дважды и так далее до корня дерева поиска, который расширяется раз. [1] : 5 Таким образом, общее количество расширений в итеративном поиске с углублением равно
где - количество расширений на глубине , - количество расширений на глубине и т. д. Факторинг дает
Теперь давай . Тогда у нас есть
Это меньше, чем бесконечная серия
который сходится к
- , для
То есть у нас есть
, для
Поскольку или является константой, не зависящей от (глубины), то если (т. Е. Если коэффициент ветвления больше 1), время выполнения итеративного поиска углубления в глубину равно .
Пример [ править ]
Для и номер
В целом итеративный поиск с углублением от глубины до глубины расширяется только на большее количество узлов, чем один поиск в ширину или поиск с ограничением по глубине до глубины , когда . [5]
Чем выше коэффициент ветвления, тем меньше накладные расходы на многократно расширенные состояния, [1] : 6, но даже когда коэффициент ветвления равен 2, итеративный поиск с углублением занимает примерно вдвое больше времени, чем полный поиск в ширину. Это означает, что временная сложность итеративного углубления сохраняется .
Космическая сложность [ править ]
Пространство сложность из IDDFS является , [1] : 5 , где есть глубина цели.
Доказательство [ править ]
Поскольку IDDFS в любой момент занимается поиском в глубину, ей нужно хранить только стек узлов, который представляет ветвь дерева, которое она расширяет. Поскольку он находит решение оптимальной длины, максимальная глубина этого стека равна , а значит, и максимальный объем пространства .
В общем, итеративное углубление является предпочтительным методом поиска, когда существует большое пространство поиска и глубина решения неизвестна. [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, который чередует два поиска: один, начиная с исходного узла и двигаясь по направленным дугам, а другой, начиная с целевого узла и продолжая идти по направленным дугам в противоположном направлении (от дуги головной узел к хвостовому узлу дуги). Процесс поиска сначала проверяет, что исходный узел и целевой узел совпадают, и, если да, возвращает тривиальный путь, состоящий из одного исходного / целевого узла. В противном случае процесс прямого поиска расширяет дочерние узлы исходного узла (набора ), процесс обратного поиска расширяет родительские узлы целевого узла (набора ), и проверяется, ипересекаются. Если да, то кратчайший путь найден. В противном случае глубина поиска увеличивается, и выполняется то же вычисление.
Одним из ограничений алгоритма является то, что кратчайший путь, состоящий из нечетного числа дуг, не будет обнаружен. Предположим, у нас есть кратчайший путь. Когда глубина достигнет двух скачков по дугам, прямой поиск продолжится от , а обратный поиск продолжится от до . Графически границы поиска будут проходить друг через друга, и вместо этого будет возвращен неоптимальный путь, состоящий из четного числа дуг. Это показано на следующих диаграммах:
Что касается сложности пространства, алгоритм окрашивает самые глубокие узлы в процессе прямого поиска, чтобы обнаружить наличие среднего узла, где встречаются два процесса поиска.
Дополнительная сложность применения двунаправленной IDDFS заключается в том, что если исходный и целевой узлы находятся в разных сильно связанных компонентах, например , если нет выходящей и входящей дуги , поиск никогда не завершится.
Сложности времени и пространства [ править ]
Время работы двунаправленной IDDFS определяется выражением
а сложность пространства определяется выражением
где - количество узлов в кратчайшем пути . Поскольку временная сложность итеративного углубленного поиска в глубину равна , ускорение примерно
Псевдокод [ править ]
функция Build-Path (s, μ, B) равна π ← Find-Shortest-Path (s, μ) (Рекурсивно вычислить путь к узлу ретрансляции) удалить последний узел из π вернуть π B (добавить стек обратного поиска)
функция Depth-Limited-Search-Forward (u, Δ, F) - если Δ = 0, то F ← F {u} (Отметить узел) вернуть для каждого дочернего элемента u do Поиск вперед с ограничением по глубине (ребенок, Δ - 1, F)
функция Depth-Limited-Search-Backward (u, Δ, B, F) равна добавить u к B если Δ = 0, то если u в F, то верните u (достиг отмеченного узла, используйте его как узел ретрансляции) удалить головной узел B возвращать нуль Еогеасп родителя из U сделать μ ← Глубина-Ограниченный-Поиск-Назад (родительский, Δ - 1, B, F) если μ null, то верните μ удалить головной узел B вернуть ноль
Функция Find-кратчайший путь (s, т) является , если s = т , то вернуться <s> F, B, Δ ← ∅, ∅, 0 навсегда сделать Поиск вперед с ограниченной глубиной (s, Δ, F) для каждого δ = Δ, Δ + 1 do μ ← Поиск с ограничением по глубине назад (t, δ, B, F) если μ null, вернуть Build-Path (s, μ, B) (найден узел ретрансляции) 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). Искусственный интеллект: современный подход .