Aula 05 Busca Com Informa O II

Inteligência Artificial
Aula 05 – Busca com informação e exploração. Busca local

Métodos de busca
! Busca Cega ou Exaustiva:
– Não sabe qual o melhor nó da fronteira a ser expandido. Apenas distingue o estado objetivo dos não objetivos.

! Busca Heurística:
– Estima qual o melhor nó da fronteira a ser expandido com base em funções heurísticas.

• Busca Local:
– Operam em um único estado e movem-se para a vizinhança deste estado.

Busca Local
• Em muitos problemas de otimização o caminho para o objetivo é irrelevante.
– Queremos apenas encontrar o estado objetivo, não importando a sequência de ações.
– Espaço de estados = conjunto de configurações completas. • Queremos encontrar a melhor configuração.

– Neste caso podemos usar algoritmos de busca local.
• Mantêm apenas o estado atual, sem a necessidade de manter a árvore de busca.

Busca Local
• Exemplo:
– Jogo das n-rainhas: o que importa é a configuração final e não a ordem em que as rainhas foram acrescentadas.
– Outros exemplos:
•
•
•
•

Projeto de Circuitos eletrônicos;
Layout de instalações industriais;
Escalonamento de salas de aula;
Otimização de redes;

• Se o caminho para a solução não importa, podemos considerar uma classe diferente de algoritmos que não se preocupam com os caminhos: os algoritmos de busca local.

Busca Local
• Algoritmos de busca local operam sobre um único estado corrente, ao invés de vários caminhos. • Em geral se movem apenas para os vizinhos desse estado.
• Os caminhos seguidos pela busca não são guardados. Exemplo
• Colocar n rainhas em um tabuleiro n × n, sendo que cada linha, coluna ou diagonal pode ter apenas uma rainha.

Busca local
• Vantagens:
– Ocupam pouquíssima memória (normalmente constante).
– Podem encontrar soluções razoáveis em grandes ou infinitos espaços (contínuos) de estados.

• São uteis para resolver problemas de otimização. – Busca pelo melhor estado de acordo com a função objetivo
– Muitos problemas de otimização não se