Pesquisa aprofundada iterativa em profundidade - Iterative deepening depth-first search

Aprofundamento iterativo - pesquisa primeiro

Classe	Algoritmo de busca
Estrutura de dados	Árvore , Gráfico
Desempenho de pior caso	${\ displaystyle O (b ^ {d})}$ , onde está o fator de ramificação e é a profundidade da solução mais rasa ${\ displaystyle b}$${\ displaystyle d}$
Pior caso de complexidade de espaço	${\ displaystyle O (d)}$

Algoritmos de pesquisa de gráfico e árvore
α – β UMA* B * Retrocedendo Feixe Bellman – Ford Best-first Bidirecional Borůvka Ramificação e limite BFS Museu Britânico D * DFS Dijkstra Edmonds Floyd – Warshall Fringe search Escalada IDA * Aprofundamento iterativo Johnson Ponto de salto Kruskal BFS Lexicográfico LPA * Prim SMA *
Listagens
Algoritmos de gráfico Algoritmos de busca Lista de algoritmos de gráfico
tópicos relacionados
Programaçao dinamica Travessia do gráfico Travessia de árvore Jogos de busca
v t e

Na ciência da computação , a pesquisa de aprofundamento iterativa ou, mais especificamente, a pesquisa de aprofundamento iterativo em profundidade (IDS ou IDDFS) é uma estratégia de pesquisa de espaço de estado / gráfico em que uma versão limitada de profundidade da pesquisa em profundidade é executada repetidamente com limites de profundidade crescentes até que objetivo é encontrado. O IDDFS é ideal como pesquisa em amplitude , mas usa muito menos memória; a cada iteração, ele visita os nós na árvore de pesquisa na mesma ordem da pesquisa em profundidade, mas a ordem cumulativa em que os nós são visitados pela primeira vez é efetivamente primeiro em largura.

Algoritmo para gráficos direcionados

O pseudocódigo a seguir mostra o IDDFS implementado em termos de um DFS recursivo de profundidade limitada (chamado DLS) para gráficos direcionados . Esta implementação de IDDFS não leva em conta os nós já visitados e, portanto, não funciona para gráficos não direcionados .

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)

Se o nó objetivo for encontrado, o DLS desenrola a recursão que retorna sem outras iterações. Caso contrário, se pelo menos um nó existir nesse nível de profundidade, o sinalizador restante permitirá que o IDDFS continue.

2-tuplas são úteis como valor de retorno para sinalizar o IDDFS para continuar a aprofundar ou parar, caso a profundidade da árvore e a associação ao objetivo sejam desconhecidas a priori . Outra solução poderia usar valores sentinela em vez de representar resultados de nível não encontrados ou restantes .

Propriedades

O IDDFS combina a eficiência de espaço da pesquisa em profundidade e a completude da pesquisa em amplitude (quando o fator de ramificação é finito). Se houver uma solução, ele encontrará um caminho de solução com o menor número de arcos.

Uma vez que o aprofundamento iterativo visita estados várias vezes, pode parecer um desperdício, mas acaba não sendo tão caro, uma vez que em uma árvore a maioria dos nós está no nível inferior, então não importa muito se os níveis superiores são visitados vários vezes.

A principal vantagem do IDDFS na pesquisa da árvore do jogo é que as pesquisas anteriores tendem a melhorar as heurísticas comumente usadas, como a heurística killer e a poda alfa-beta , de modo que uma estimativa mais precisa da pontuação de vários nós na pesquisa de profundidade final pode ocorrer, e a pesquisa é concluída mais rapidamente, pois é feita em uma ordem melhor. Por exemplo, a poda alfa-beta é mais eficiente se procurar os melhores movimentos primeiro.

Uma segunda vantagem é a capacidade de resposta do algoritmo. Como as iterações iniciais usam pequenos valores para , elas são executadas com extrema rapidez. Isso permite que o algoritmo forneça indicações iniciais do resultado quase imediatamente, seguidas por refinamentos conforme aumentos. Quando usado em um ambiente interativo, como em um programa de jogo de xadrez , esse recurso permite que o programa jogue a qualquer momento com o melhor lance atual encontrado na pesquisa que ele completou até agora. Isso pode ser formulado como cada profundidade da pesquisa produzindo co- recursivamente uma melhor aproximação da solução, embora o trabalho feito em cada etapa seja recursivo. Isso não é possível com uma pesquisa em profundidade tradicional, que não produz resultados intermediários. ${\ displaystyle d}$${\ displaystyle d}$

Análise assintótica

Complexidade de tempo

A complexidade de tempo do IDDFS em uma árvore (bem balanceada) funciona para ser o mesmo que a pesquisa em largura, ou seja , onde está o fator de ramificação e é a profundidade do objetivo. ${\ displaystyle O (b ^ {d})}$${\ displaystyle b}$${\ displaystyle d}$

Prova

Em uma pesquisa de aprofundamento iterativa, os nós em profundidade são expandidos uma vez, aqueles em profundidade são expandidos duas vezes e assim por diante até a raiz da árvore de pesquisa, que é expandida vezes. Portanto, o número total de expansões em uma pesquisa de aprofundamento iterativa é ${\ 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 _ { i = 0} ^ {d} (d + 1-i) b ^ {i}}$

onde é o número de expansões em profundidade , é o número de expansões em profundidade e assim por diante. Fatorar dá ${\ 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})}$

Agora vamos . Então nós temos ${\ 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})}$

Isso é menos do que a série infinita

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

que converge para

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

Ou seja, temos

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

Como ou é uma constante independente de (a profundidade), se (ou seja, se o fator de ramificação for maior que 1), o tempo de execução da pesquisa de aprofundamento iterativa em profundidade é . ${\ displaystyle (1-x) ^ {- 2}}$${\ displaystyle \ left (1 - {\ frac {1} {b}} \ right) ^ {- 2}}$${\ displaystyle d}$${\ displaystyle b> 1}$${\ displaystyle O (b ^ {d})}$

Exemplo

Para e o número é ${\ displaystyle b = 10}$${\ displaystyle d = 5}$

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

No conjunto, uma pesquisa de aprofundamento iterativa desde a profundidade até a profundidade expande apenas cerca de mais nós do que uma única pesquisa de largura ou profundidade limitada para profundidade , quando . ${\ displaystyle 1}$${\ displaystyle d}$${\ displaystyle 11 \%}$${\ displaystyle d}$${\ displaystyle b = 10}$

Quanto maior o fator de ramificação, menor a sobrecarga de estados repetidamente expandidos, mas mesmo quando o fator de ramificação é 2, a pesquisa de aprofundamento iterativa leva apenas cerca de duas vezes mais do que uma pesquisa completa primeiro. Isso significa que a complexidade de tempo do aprofundamento iterativo ainda é . ${\ displaystyle O (b ^ {d})}$

Complexidade do espaço

A complexidade espacial do IDDFS é , onde está a profundidade do objetivo. ${\ displaystyle O (d)}$${\ displaystyle d}$

Prova

Visto que o IDDFS, em qualquer ponto, está engajado em uma pesquisa em profundidade, ele precisa apenas armazenar uma pilha de nós que representa o ramo da árvore que está expandindo. Uma vez que encontra uma solução de comprimento ideal, a profundidade máxima dessa pilha é e, portanto, a quantidade máxima de espaço é . ${\ displaystyle d}$${\ displaystyle O (d)}$

Em geral, o aprofundamento iterativo é o método de pesquisa preferido quando há um grande espaço de pesquisa e a profundidade da solução não é conhecida.

Exemplo

Para o seguinte gráfico:

uma pesquisa em profundidade começando em A, assumindo que as bordas esquerdas no gráfico mostrado são escolhidas antes das bordas direitas, e assumindo que a pesquisa lembra os nós visitados anteriormente e não os repetirá (uma vez que este é um pequeno gráfico), irá visitar o nós na seguinte ordem: A, B, D, F, E, C, G. As arestas percorridas nesta busca formam uma árvore Trémaux , uma estrutura com importantes aplicações na teoria dos grafos .

Realizar a mesma pesquisa sem lembrar os nós visitados anteriormente resulta em visitar nós na ordem A, B, D, F, E, A, B, D, F, E, etc. para sempre, capturados no A, B, D, F , Ciclo E e nunca alcançando C ou G.

O aprofundamento iterativo evita esse loop e alcançará os seguintes nós nas seguintes profundidades, supondo que prossiga da esquerda para a direita como acima:

• 0: A
• 1: A, B, C, E

(O aprofundamento iterativo agora viu C, quando uma pesquisa convencional em profundidade não viu.)

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

(Ele ainda vê C, mas veio depois. Também vê E por um caminho diferente e volta para F duas vezes.)

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

Para este gráfico, à medida que mais profundidade é adicionada, os dois ciclos "ABFE" e "AEFB" simplesmente ficarão mais longos antes que o algoritmo desista e tente outra ramificação.

Algoritmos relacionados

Semelhante ao aprofundamento iterativo é uma estratégia de pesquisa chamada pesquisa de alongamento iterativo que funciona com limites crescentes de custo de caminho em vez de limites de profundidade. Ele expande os nós na ordem de aumento do custo do caminho; portanto, o primeiro objetivo que encontra é aquele com o custo do caminho mais barato. Mas o alongamento iterativo incorre em sobrecarga substancial que o torna menos útil do que o aprofundamento iterativo.

Aprofundamento iterativo A * é a melhor pesquisa que executa o aprofundamento iterativo com base em valores " f " semelhantes aos calculados no algoritmo A * .

IDDFS bidirecional

O IDDFS tem uma contraparte bidirecional, que alterna duas buscas: uma iniciando no nó de origem e movendo-se ao longo dos arcos direcionados, e outra iniciando no nó de destino e prosseguindo ao longo dos arcos direcionados na direção oposta (do nó principal do arco para o do arco nó da cauda). O processo de pesquisa primeiro verifica se o nó de origem e o nó de destino são iguais e, em caso afirmativo, retorna o caminho comum que consiste em um único nó de origem / destino. Caso contrário, o processo de pesquisa para a frente expande os nós filhos do nó de origem (set ), o processo de pesquisa para trás expande os nós pai do nó de destino (conjunto ), e é verificado se e cruzam. Nesse caso, um caminho mais curto é encontrado. Caso contrário, a profundidade da pesquisa é incrementada e o mesmo cálculo ocorre. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$

Uma limitação do algoritmo é que o caminho mais curto consistindo em um número ímpar de arcos não será detectado. Suponha que tenhamos um caminho mais curto. Quando a profundidade atingir dois saltos ao longo dos arcos, a busca para a frente continuará para de e a busca para trás continuará de para . De forma pictórica, as fronteiras de pesquisa passarão umas pelas outras e, em vez disso, será retornado um caminho abaixo do ideal que consiste em um número par de arcos. Isso é ilustrado nos diagramas abaixo: ${\ displaystyle \ langle s, u, v, t \ rangle.}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$

No que diz respeito à complexidade do espaço, o algoritmo colore os nós mais profundos no processo de busca progressiva para detectar a existência do nó do meio onde os dois processos de busca se encontram.

A dificuldade adicional de aplicar IDDFS bidirecional é que se os nós de origem e destino estiverem em componentes fortemente conectados diferentes, digamos , se não houver nenhum arco saindo e entrando , a pesquisa nunca terminará. ${\ displaystyle s \ in S, t \ in T}$${\ displaystyle S}$${\ displaystyle T}$

Complexidades de tempo e espaço

O tempo de execução do IDDFS bidirecional é dado por

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

e a complexidade do espaço é dada por

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

onde é o número de nós no -path mais curto . Uma vez que a complexidade do tempo de execução da pesquisa em profundidade de aprofundamento iterativo é , a aceleração é aproximadamente ${\ displaystyle n}$${\ displaystyle s, t}$${\ displaystyle \ sum _ {k = 0} ^ {n} b ^ {k}}$

${\ 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)}} \ approx {\ frac {b ^ {n + 1}} {2b ^ {n / 2 + 1}}} = \ Theta (b ^ {n / 2}) .}$

Pseudo-código

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

Referências