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

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

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

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

Псевдокод

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

function Depth-Limited-Search-Forward(u, Δ, F) is
    if Δ = 0 then
        F ← F $\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 μ $\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 μ $\neq$ null then
               return Build-Path(s, μ, B) (Found a relay node)
       F, Δ ← ∅, Δ + 1