Итеративный поиск в глубину с углублением - Iterative deepening depth-first search

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

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

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

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

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

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

function IDDFS(root) is
    for depth from 0 to ∞ do
        found, remaining ← DLS(root, depth)
        if found ≠ null then
            return found
        else if not remaining then
            return null

function DLS(node, depth) is
    if depth = 0 then
        if node is a goal then
            return (node, true)
        else
            return (null, true)    (Not found, but may have children)

    else if depth > 0 then
        any_remaining ← false
        foreach child of node do
            found, remaining ← DLS(child, depth−1)
            if found ≠ null then
                return (found, true)   
            if remaining then
                any_remaining ← true    (At least one node found at depth, let IDDFS deepen)
        return (null, any_remaining)

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ displaystyle 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}}$ , для ${\ displaystyle abs (x) <1}$

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

пример

Для и номер ${\ displaystyle b = 10}$${\ displaystyle d = 5}$

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

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

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

Космическая сложность

Пространство сложности из IDDFS есть , где есть глубина цели. ${\ displaystyle O (d)}$${\ displaystyle d}$

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

Поскольку IDDFS в любой момент занимается поиском в глубину, ей нужно хранить только стек узлов, который представляет ветвь дерева, которое она расширяет. Поскольку он находит решение оптимальной длины, максимальная глубина этого стека равна , а значит, и максимальный объем пространства . ${\ displaystyle d}$${\ displaystyle 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: 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» просто станут длиннее, прежде чем алгоритм откажется и попытается выполнить другую ветвь.

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

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

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

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

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

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

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

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

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

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

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

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

${\ displaystyle b ^ {n / 2},}$

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

${\ displaystyle {\ 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)}} \ приблизительно {\ frac {b ^ {n + 1}} {2b ^ {n / 2 + 1}}} = \ Theta (b ^ {n / 2}) .}$

Псевдокод

function Build-Path(s, μ, B) is
    π ← Find-Shortest-Path(s, μ) (Recursively compute the path to the relay node)
    remove the last node from π
    return π ${\displaystyle \circ }$ B (Append the backward search stack)

function Depth-Limited-Search-Forward(u, Δ, F) is
    if Δ = 0 then
        F ← F ${\displaystyle \cup }$ {u} (Mark the node)
        return
    foreach child of u do
        Depth-Limited-Search-Forward(child, Δ − 1, F)

function Depth-Limited-Search-Backward(u, Δ, B, F) is
    prepend u to B
    if Δ = 0 then
        if u in F  then
            return u (Reached the marked node, use it as a relay node)
        remove the head node of B
        return null
    foreach parent of u do
        μ ← Depth-Limited-Search-Backward(parent, Δ − 1, B, F)
        if μ ${\displaystyle \neq }$ null then
            return μ
    remove the head node of B
    return null

function Find-Shortest-Path(s, t) is
   if s = t then
       return <s>
   F, B, Δ ← ∅, ∅, 0
   forever do
       Depth-Limited-Search-Forward(s, Δ, F)
       foreach δ = Δ, Δ + 1 do
           μ ← Depth-Limited-Search-Backward(t, δ, B, F)
           if μ ${\displaystyle \neq }$ null then
               return Build-Path(s, μ, B) (Found a relay node)
       F, Δ ← ∅, Δ + 1

использованная литература