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

Definição

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

1. Expande primeiro o nó raiz (estado inicial).
2. Depois expande todos os nós do mesmo nível de profundidade.
3. Só então passa para o próximo nível da árvore de busca.

Estrutura usada: Fila (FIFO — First In, First Out).

Ordem de expansão: por níveis.

Como funciona

1. Coloca o nó raiz na fila (profundidade 0).
2. Remove o primeiro nó da fila (o mais antigo) e expande, gerando seus sucessores.
3. Coloca todos os sucessores no final da fila.
4. Repete o processo até:
   • Encontrar o estado objetivo, ou
   • Fila ficar vazia (nenhuma solução).

Exemplo 1 – Árvore de Busca

Suponha esta árvore e que o objetivo é chegar ao nó D:

Passos da BFS:

1. Fila inicial: [A]
2. Expande A → adiciona B, C, D → [B, C, D]
3. Verifica B → adiciona E, F → [C, D, E, F]
4. Verifica C → (sem filhos) → [D, E, F]
5. Verifica D → É objetivo! ✅

• Ordem de visita: A → B → C → D.

• Encontrou o objetivo no nível mais raso.

Exemplo 2 – Problema das Cidades

Imagine um grafo de cidades conectadas (trecho simplificado):

Objetivo: Sair de Arad e chegar a Bucareste, assumindo custo uniforme.

Execução da BFS:

1. Começa em Arad → adiciona [Sibiu, Zerind]
2. Verifica Sibiu → [Zerind, Fagaras]
3. Verifica Zerind → [Fagaras, Oradea]
4. Verifica Fagaras → [Oradea,Bucareste]
5. Verifica Oradea (Sem Filhos) → [Bucareste]
6. encontra Bucareste ✅

💡 A BFS garantiu o menor número de passos até o objetivo.

Propriedades da BFS

Características

• Completa: ✅ Sim, se b (fator de ramificação) e d (profundidade da solução mais rasa) forem finitos.

• Ótima: ✅ Sim, se todas as ações tiverem o mesmo custo.

• Tempo: O(b^d) — porque no pior caso visita todos os nós até a profundidade d.

• Espaço: O(b^d) — precisa guardar todos os nós na memória.

Vantagens

• Sempre encontra a solução mais curta em número de passos (ótima com custo uniforme).
• Simples de implementar.

Desvantagens

• Consome muita memória, pois guarda todos os nós do nível atual antes de passar ao próximo.
• Fica lenta em espaços de estados grandes.

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.