Aula 5 - Resolução de Problemas - Busca Informada

Prévia do material em texto

Resolução de 
Problemas: 
Buscas Informadas 
PROF. RICARDO P. MESQUITA
Sumário
Estratégias de Busca Com Informação
Busca Gulosa
Algoritmo A*
Variações no A*
Prof. Ricardo Mesquita 02/18
Estratégias de Busca com 
Informação
Busca com informação: estratégia que utiliza o 
conhecimento específico do problema, além da 
definição do próprio problema
Prof. Ricardo Mesquita 03/18
Estratégias de Busca com 
Informação
Abordagem geral: busca pela melhor escolha
◦ Trata-se de uma especialização da busca em árvore, na qual 
um nó é selecionado para expansão com base em uma função 
de avaliação f( n )
◦ Pode ser implementado por meio de uma fila de prioridades
◦ Apesar do nome (consagrado) não há como se garantir o que 
seria a “melhor escolha”
Prof. Ricardo Mesquita 04/18
Estratégias de Busca com 
Informação
Outro parâmetro importante das buscas 
informadas é a função heurística h( n ), que 
representa o custo estimado do caminho mais 
econômico do nó n até um nó objetivo
Prof. Ricardo Mesquita 05/18
Busca Gulosa
◦ Tenta expandir o nó mais próximo à meta, na suposição 
de que isso provavelmente levará a uma solução rápida
◦ Desse modo, ela avalia nós usando apenas a função 
heurística f( n ) = h( n )
◦ Pode levar a mínimos (máximos) locais
◦ É semelhante à busca em profundidade, pelo fato de 
preferir seguir um único caminho até o objetivo
◦ Possui os mesmos defeitos da busca em profundidade: 
não é ótima e é incompleta
Prof. Ricardo Mesquita 06/18
Exemplo
Considere o problema de ir de Arad a Bucareste
Prof. Ricardo Mesquita 07/18
Usando Busca Gulosa
Prof. Ricardo Mesquita 08/18
Arad 366
Sibiu Timisoara Zerind
374329253
Fagaras R. VilceaOradea
193176380
Bucareste
0
Algoritmo A*
◦ Forma mais conhecida de busca pela melhor 
escolha
◦ Avalia os nós combinando g( n ), o custo para se 
alcançar n, e h( n ), o custo de ir do nó n até o 
objetivo 
f( n ) = g( n ) + h( n )
Prof. Ricardo Mesquita 09/18
Algoritmo A*
◦ A análise do caráter ótimo do algoritmo A* é 
direta se for usada com uma busca em árvore
◦ A* será ótimo se h( n ) for uma heurística 
admissível, isto é, desde que h( n ) nunca 
superestime o custo para alcançar o objetivo
◦ Ou seja, h é uma estimativa do custo para se alcançar o 
objetivo. Usamos h*( n ), assim temos:
f*( n ) = g( n ) + h*( n )
Prof. Ricardo Mesquita 10/18
Algoritmo A*
Vamos enunciar o algoritmo em alto nível:
1. Criar um grafo G contendo o estado inicial S
2. Colocar S em uma lista chamada ABERTOS
3. Criar outra lista denominada FECHADOS
4. Se ABERTOS = , então FALHA
5. Senão, selecionar um nó de ABERTOS e colocar em FECHADOS
6. Se o nó satisfaz a condição de término, PARE (sucesso)
7. Senão, gerar o conjunto M de filhos desse nó
8. Colocar M em ABERTOS, verificando se há repetições de algum elemento tanto 
em ABERTOS quanto em FECHADOS (deve-se descartar repetições)
9. Reordenar ABERTOS segundo a função de avaliação
10. Vá para o passo 4
Prof. Ricardo Mesquita 11/18
Algoritmo A*
Vamos considerar novamente o problema de ir de 
Arad a Bucareste.
Então:
◦ g(n) é o custo (conhecido) de se ir de uma cidade até 
a próxima.
◦ Veja os rótulos das arestas do grafo representativo.
◦ h*(n) é uma estimativa do que falta para se atingir o 
destino. 
◦ A distância reta da cidade atual até Bucareste é um bom 
estimador e nunca irá superestimar a distância da estrada!
Prof. Ricardo Mesquita 12/18
Algoritmo A*
Prof. Ricardo Mesquita 13/18
Considerações
A* expande todos os nós com f( n ) < C*, onde C*
representa o custo do caminho da solução ótima
A* pode expandir alguns nós diretamente no 
“contorno objetivo” ( f( n ) = C* ) antes de 
selecionar um nó objetivo
Prof. Ricardo Mesquita 14/18
Variações no A*
AIA* (A* com Aprofundamento Iterativo):
◦ Tem o objetivo de tentar reduzir requisitos de memória
◦ Ao invés da profundidade, o valor de corte é determinado pela 
função de avaliação.
◦ A cada iteração, o valor de corte é o menor custo de f de 
qualquer nó que tenha excedido o corte na iteração anterior
◦ É prático para problemas cujo custo do passo é unitário
◦ Evita a sobrecarga da manutenção de uma fila ordenada de nós 
Prof. Ricardo Mesquita 15/18
Variações no A*
LMA* (A* Limitado pela memória)
LMSA* (A* Limitado pela memória simplificado)
◦ Funciona como o A* até completar o espaço disponível 
de memória
◦ A partir daí, precisa descartar um nó antigo para 
prosseguir com a busca
◦ O LMSA* sempre descarta o pior nó folha, armazenando 
seu valor no nó pai
Prof. Ricardo Mesquita 16/18
Exercício
Utilize o Algoritmo A* para encontrar uma solução 
para o Jogo das oito peças dadas as seguintes 
condições
Prof. Ricardo Mesquita 17/18
Dúvidas?