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

Problemas de Busca

A busca é uma das técnicas centrais da Inteligência Artificial (IA). Ela é usada para encontrar soluções em problemas que envolvem múltiplas possibilidades.

• Ideal para ambientes observáveis, discretos, determinísticos e conhecidos.
• Uma estratégia de busca percorre sistematicamente alternativas até encontrar uma sequência de passos que leva à solução.

A busca pode ser:

• Busca Cega (sem informação): não usa conhecimento do problema, só explora sistematicamente.
• Busca com Informada (com heurísticas): usa heurísticas ou conhecimento para guiar a exploração.

Definição Formal de um Problema de Busca

Um problema de busca pode ser definido por 5 componentes principais:

1. Estado inicial
   • Onde o agente começa.
   • Ex.: No aspirador de pó, a posição inicial do robô e da sujeira.
2. Ações possíveis
   • O que o agente pode fazer em cada estado.
   • Ex.: “Esquerda”, “Direita” ou “Aspirar” para o robô aspirador.
3. Modelo de transição (Função SUCESSOR)
   • Mostra para qual estado o agente irá ao executar uma ação.
   • Ex.: SUCESSOR(S, A) → retorna o novo estado.
4. Teste objetivo
   • Determina se um estado é objetivo.
   • Ex.: Todas as casas limpas no aspirador de pó.
5. Função de custo do caminho
   • Associa um custo numérico a cada sequência de ações.
   • Ex.: cada movimento ou ação custa 1.

Espaço de estados:

• Conjunto de todos os estados possíveis a partir do estado inicial.

Exemplos Clássicos de Problemas de Busca

Mundo do Aspirador de Pó:

• Estados: posição do agente + estado de limpeza das casas.
• Estado inicial: qualquer configuração de sujeira.
• Ações: Esquerda, Direita, Aspirar.
• Modelo de transição: estado muda conforme a ação (ex.: aspirar → limpa a casa).
• Teste objetivo: todas as casas limpas.
• Custo de caminho: cada ação = 1.

Problema das 8 Rainhas:

• Estados: qualquer arranjo de 0 a 8 rainhas no tabuleiro.
• Estado inicial: tabuleiro vazio.
• Ações: adicionar uma rainha em um quadrado vazio.
• Modelo de transição: tabuleiro com uma nova rainha.
• Teste objetivo: 8 rainhas no tabuleiro sem se atacarem.
• Custo de caminho: cada rainha colocada = 1.

Busca de Soluções

Para resolver o problema:

1. Formulamos a árvore de busca
   • Nó raiz: estado inicial
   • Filhos: estados resultantes das ações possíveis
   • Fronteira: conjunto de nós que ainda podem ser expandidos
2. Processo de busca
   • Escolhe um nó da fronteira
   • Expande: gera todos os estados sucessores
   • Adiciona os novos nós à fronteira
   • Repete até encontrar um estado objetivo
3. Soluções
   • São sequências de ações do estado inicial ao objetivo
   • A busca pode parar no primeiro objetivo ou continuar para achar o menor custo

Problema de Estados Repetidos

Durante a busca, estados podem se repetir e isso gera:

• Caminhos redundantes
• Árvores de busca infinitas
• Grande aumento de custo

Estratégias para lidar com estados repetidos:

• Tree-Search: não evita estados repetidos (pode gerar loops).
• Graph-Search: mantém lista de estados visitados e não os repete.

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.