INF 1771 Inteligência Artificial  
Aula 05 Busca Local  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Métodos de Busca  
Busca Cega ou Exaustiva:  
Não sabe qual o melhor da fronteira a ser expandido. Apenas  
distingue o estado objetivo dos não objetivos.  
Busca Heurística:  
Estima qual o melhor 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 o caminho para a solução é  
irrelevante.  
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  
utilizar um algoritmo 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.  
O caminho seguido pelo algoritmo não é guardado.  
Busca Local  
Vantagens:  
Ocupam pouquíssima memória (normalmente constante).  
Podem encontrar soluções razoáveis em grandes ou  
infinitos espaços de estados.  
São uteis para resolver problemas de otimização.  
Buscar por estados que atendam a uma função objetivo.  
Busca Local  
Panorama do Espaço de Estados:  
Local = Estado;  
Elevação = Valor de custo  
da função heurística;  
Busca-se o máximo ou  
mínimo global;  
Busca Local  
Principais Algoritmos:  
Hill Climbing  
Simulated Annealing  
Local Beam  
Genetic Algorithms  
Pseudocódigo Hill Climbing  
Função Hill-Climbing(Problema) retorna um estado que é o máximo local  
Inicio  
EstadoAtual FazNó(Problema[EstadoInicial])  
loop do  
Vizinho ← SucessorDeMaiorValor(EstadoAtual)  
se Vizinho[Valor] for menor ou igual EstadoAtual[Valor] então  
retorna EstadoAtual  
EstadoAtual ← Vizinho  
Fim  
Consiste de de um loop que continuamente move-se para os estados que aumentam  
o valor em sua função de avaliação.  
Termina quando atinge um "pico" onde nenhum vizinho tem um valor maior.  
Não mantem uma árvores de busca.  
Hill Climbing Exemplo  
Problema: 8 Rainhas (estados completos)  
Em cada estado: 8 rainhas no tabuleiro, uma em  
cada coluna.  
Ações:  
Mover uma rainha para outro quadrado na  
mesma coluna.  
Função Heurística (h):  
Número de rainhas sendo atacadas.  
Objetivo:  
h = 0 (nenhuma rainha sendo atacada)  
Hill Climbing Exemplo  
h = 17  
Melhor movimento: 12  
Hill Climbing  
É um algoritmo guloso escolhe sempre o primeiro  
melhor vizinho para progredir na busca.  
Essa abordagem pode ter bons resultados em alguns  
problemas. Sendo capaz de progredir rapidamente para  
a solução problema.  
Mas, sofre de três sérios problemas:  
Máximos locais  
Planícies  
Encostas e Picos  
Hill Climbing  
Máximos Locais  
Planícies  
Hill Climbing Exemplo  
Ações Possíveis:  
Pegar um bloco e colocar ele sobre a mesa.  
Pegar um bloco e colocar ele sobre outro bloco.  
Heurística:  
+1 para cada bloco em cima do bloco onde ele deve estar.  
-1 para cada bloco em cima do bloco errado.  
Hill Climbing Exemplo  
Máximo Local  
Hill Climbing  
Encostas e Picos  
Hill Climbing Exemplo  
Problema: 8 Rainhas  
Inicializando aleatoriamente o estado inicial:  
O algoritmo fica em preso em um máximo local em 86%  
das vezes.  
Resolve apenas 14% das instancias.  
Quando tem sucesso, resolve o problema em  
aproximadamente 4 passos nada mal para um  
espaço de estados com 17 milhões de estados.  
Hill Climbing  
Variações:  
Random-Restart Hill Climbing;  
Não é ótimo e não é completo.  
O desempenho do Hill Climbing depende muito do  
formato do panorama do espaço de estados.  
Exercício  
1) Como tratar ambientes contínuos?  
Discretização  
Métodos matemáticos  
Busca Online  
Todos os métodos de busca vistos até o momento são  
offline, ou seja, o agente calcula todos antes passos  
antes de agir.  
Agentes de busca online devem intercalar entre busca  
e execução das ações.  
Apropriado para ambientes dinâmicos, desconhecidos  
e também para espaços de busca muito grandes.  
Busca Online - Exemplo  
Informações:  
Ações(s)  
Lista de ações possíveis no estado s.  
C(s, a, s’)  
Custo da execução da ação a no estado s  
resultando no estado s’.  
TesteObjetivo(s)  
Testa se s é o estado objetivo.  
O agente somente tem acesso aos estados  
sucessores após executar as ações.  
Busca em Profundidade Online  
Realiza uma busca em profundidade executando as ações  
fisicamente durante o processo até chegar no estado objetivo.  
Se todos os vizinhos de um estado já foram visitados é  
necessário retornar fisicamente para a posição anterior.  
Busca Local Online  
O hill climbing é naturalmente um algoritmo de busca online.  
Problema:  
Na sua forma mais simples, pode deixar o agente parado em um  
máximo local sem ter para onde ir.  
Não é possível reiniciar o processo randomicamente porque o agente  
não pode teletransportar.  
Solução:  
Caminhada aleatória ao chegar em uma máximo local.  
Busca Local Online  
A caminhada aleatória garante que o agente eventualmente  
vai encontrar o objeto ou completar o processo de  
exploração.  
Esse processo pode ser lento.  
Qual Algoritmo Usar?  
Leitura Complementar  
Russell, S. and Novig, P. Artificial Intelligence: a  
Modern Approach, 2nd Edition, Prentice-Hall,  
2003.  
Capítulo 4: Informed Search and Exploration