CCT-UFCA/Ciência da Computação/Inteligência Artificial/Busca em profundidade

Busca em Profundidade - Definição

A busca em profundidade é uma estratégia de busca sem informação (cega) que:

1. Sempre expande o nó mais profundo que está na fronteira.
2. Explora um caminho até não haver mais sucessores (nó folha) ou até atingir um limite.
3. Ao chegar num beco sem saída, retrocede (backtracking) para explorar outros caminhos.

• Estrutura usada: Pilha (LIFO — Last In, First Out).
• Ordem de expansão: segue um ramo até o fim antes de voltar.

Como funciona (versão árvore)

1. Coloca o nó raiz na pilha.
2. Remove o último nó adicionado (topo da pilha) e expande.
3. Coloca os sucessores no topo da pilha.
4. Repete até encontrar o objetivo ou não haver mais nós.

Exemplo – Árvore de Busca (Objetivo: M)

Execução DFS:

1. Pilha: [A]
2. Expande A → adiciona C, B → [C, B]
3. Expande B → adiciona E, D → [C, E, D]
4. Expande D → adiciona I, H → [C, E, I, H]
5. Expande H → sem filhos → [C, E, I]
6. Expande I → sem filhos → [C, E]
7. Expande E → sem filhos → [C]
8. Expande C → adiciona G, F → [G, F]
9. Expande F → sem filhos → [G]
10. Expande G → adiciona M, L → [M, L]
11. Expande M → Objetivo encontrado ✅

Ordem de visita: A → B → D → H → I → E → C → F → G → M.

DFS Ilimitada

Características

• Não tem limite de profundidade.
• Segue o ramo até profundidade máxima possível antes de retroceder.
• Pode entrar em loop infinito em grafos com ciclos.

Exemplo de loop

Se houver um caminho que retorna a um estado anterior (A → B → A → B...), a DFS ilimitada pode nunca encontrar o objetivo, mesmo que ele exista em outro ramo.

DFS Limitada

Características

• Adota limite fixo de profundidade (L).
• Ao atingir esse limite, trata o nó como folha (não expande mais).
• Evita loops infinitos, mas pode perder soluções se L < profundidade do objetivo.

Exemplo

Objetivo está a profundidade 5. Se definirmos limite L = 3, a busca nunca o encontrará. Se definirmos L = 6, ela encontra, mas pode não ser ótima.

Comparação – DFS Ilimitada vs Limitada

Característica	DFS Ilimitada	DFS Limitada (l)
Limite de profundidade	❌ Não	✅ Sim
Loop infinito	❌ Possível	✅ Evitado
Completa	❌ Não (exceto grafos finitos)	❌ Não se l < d
Ótima	❌ Não	❌ Não
Uso	Espaços profundos, soluções rápidas	Quando temos noção da profundidade máxima

Referências

1. RUSSELL, S. J.; NORVIG, P. Inteligência artificial. 3 ed. LTC, 2013. 1016 p.
2. COPPIN, B. Inteligência Artificial. 1a ed. LTC, 2010. 664 p.