Inteligência Artificial  
Aula 04 Busca Heurística  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.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 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 Heurística  
Algoritmos de Busca Heurística:  
Busca Gulosa  
A*  
A busca heurística leva em conta o objetivo para decidir qual  
caminho escolher.  
Conhecimento extra sobre o problema é utilizado para guiar o  
processo de busca.  
Busca Heurística  
Como encontrar um barco perdido?  
Busca Cega -> Procura no oceano inteiro.  
Busca Heurística -> Procura utilizando informações  
relativas ao problema.  
Exemplo: correntes marítimas, vento, etc.  
Busca Heurística  
Função Heurística (h)  
Estima o custo do caminho mais barato do estado atual até  
o estado final mais próximo.  
São específicas para cada problema.  
Exemplo:  
Encontrar a rota mais curta entre duas cidades:  
h(n) = distância em linha reta direta entre o n e o final.  
Função Heurística  
Estado Atual  
Estado Objetivo  
Busca Heurística  
Algoritmos de Busca Heurística:  
Busca Gulosa  
A*  
Busca Gulosa  
Estratégia:  
Expande os nós que se encontram mais próximos do  
objetivo (uma linha reta conectando os dois pontos no  
caso de distancias), desta maneira é provável que a busca  
encontre uma solução rapidamente.  
A implementação do algoritmo se assemelha ao utilizado na  
busca cega, entretanto utiliza-se uma função heurística para  
decidir qual o nó deve ser expandido.  
Busca Gulosa  
Arad  
366  
Sibiu  
253  
Timissoara  
329  
Zerind  
374  
Arad  
366  
0
Mehadia  
Neamt  
Oradea  
Pitesti  
241  
234  
380  
100  
Arad  
66  
Fagaras  
176  
Oradea  
380  
Rimnicu Vilcea  
Bucharest  
193  
3
Craiova  
Drobeta  
Eforie  
160  
242  
161  
176  
77  
Rimnicu Vilcea 193  
Sibiu  
263  
Bucharest  
0
Fagaras  
Giurgiu  
Iasi  
Sibiu  
253  
329  
199  
374  
80  
Timisoara  
Vaslui  
226  
244  
151  
Função Heurística (h):  
Distancia em linha reta  
Lugoj  
Zerind  
Hirsova  
Urziceni  
Busca Gulosa  
Custo de busca mínimo:  
No exemplo, não expande nós fora do caminho.  
Não é ótima:  
No exemplo, escolhe o caminho que é mais econômico à  
primeira vista, via Fagaras.  
Porém, existe um caminho mais curto via Rimnicu Vilcea.  
Não é completa:  
Pode entrar em loop se não detectar a expansão de  
estados repetidos.  
Pode tentar desenvolver um caminho infinito.  
Busca Gulosa  
Ir de Iasi para Fagaras?  
Busca A*  
Estratégia:  
Combina o custo do caminho g(n) com o valor da  
heurística h(n)  
g(n) = custo do caminho do nó inicial até o nó n  
h(n) = valor da heurística do nó n até um nó objetivo  
(distancia em linha reta no caso de distancias espaciais)  
f(n) = g(n) + h(n)  
É a técnica de busca mais utilizada.  
Busca A*  
Arad  
0+366=366  
Sibiu  
Timissoara  
Zerind  
1
40+253=393 118+329=447 75+374=449  
Arad  
Fagaras  
Oradea  
Rimnicu Vilcea  
220+193=413  
2
80+366=646 239+176=415 291+380=671  
Arad  
366  
0
Mehadia  
Neamt  
Oradea  
Pitesti  
241  
234  
380  
100  
Bucharest  
Craiova  
Drobeta  
Eforie  
Sibiu  
38+253=591  
Bucharest  
Craiova  
Pitesti  
Sibiu  
160  
242  
161  
176  
77  
3
450+0=450  
366+160=526 317+100=417 300+253=553  
Rimnicu Vilcea 193  
Bucharest  
418+0=418  
Craiova  
Rimnicu Vilcea  
414+193=607  
Fagaras  
Giurgiu  
Iasi  
Sibiu  
253  
329  
199  
374  
80  
455+160=615  
Timisoara  
Vaslui  
226  
244  
151  
Lugoj  
Zerind  
Hirsova  
Urziceni  
Busca A*  
A estratégia é completa e ótima.  
Custo de tempo:  
Exponencial com o comprimento da solução, porém boas funções heurísticas  
diminuem significativamente esse custo.  
Custo memória:  
Guarda todos os nós expandidos na memória.  
Nenhum outro algoritmo ótimo garante expandir menos nós.  
Definindo Heurísticas  
Cada problema exige uma função  
heurística diferente.  
Não se deve superestimar o custo  
real da solução.  
Como escolher uma boa função  
heurística para o jogo 8-Puzzle?  
Definindo Heurísticas  
Estado Atual  
Estado Objetivo  
A quantidade de  
peças for a do lugar  
7
Definindo Heurísticas  
Definindo Heurísticas  
2
Outra Heurística?  
Definindo Heurísticas  
Número de movimentos  
necessários para colocar  
cada peça no seu lugar  
2
10  
Definindo Heurísticas  
1
0
2
9
2
Definindo Heurísticas  
Como escolher uma boa função  
heurística para o jogo 8-Puzzle?  
h¹ = número de elementos fora do lugar.  
h² = soma das distâncias de cada número à  
sua posição final (movimentação horizontal e  
vertical).  
Qual das heurísticas é melhor?  
Exemplo - A*  
1
2 3 4 5  
X
1
2
3
4
Exemplo - A*  
Qual é o espaço de estados?  
Quais são as ações possíveis?  
Qual será o custo das ações?  
Exemplo - A*  
Heurística do A*: f(n) = g(n) + h(n)  
g(n) = custo do caminho  
h(n) = função heurística  
Qual seria a função heurística h(n) mais adequada  
para este problema?  
A distancia em linha reta é uma opção.  
Exemplo - A*  
Como calcular a heurística h(n)?  
Distancia de Manhattan  
Exemplo - A*  
O próximo passo é gerar a árvore de busca e  
expandir os nós que tiverem o menor valor  
resultante da função heurística f(n).  
f(n) = g(n) + h(n)  
Exemplo - A*  
[
1,1]  
[
2,1]  
[
1,2]  
[
[
1,2] = f(n) = ?? + ??  
2,1] = f(n) = ?? + ??  
Exemplo - A*  
1
2 3 4 5  
X
1
2
3
4
Exemplo - A*  
[
1,1]  
[
2,1]  
[
1,2]  
[
1,1]  
[2,2]  
[
[
1,1] = f(n) = ?? + ??  
2,2] = f(n) = ?? + ??  
Exemplo - A*  
1
2 3 4 5  
1
2
X
3
4
Exercícios  
(1) Qual seria uma boa heurística para o jogo  
da velha?  
Exercícios  
(2) Supondo que é necessário utilizar um algoritmo de busca  
para resolver um problema no qual são necessárias respostas  
instantâneas. Mas, mesmo utilizando o A* com uma boa  
função heurística, o tempo gasto com o processo de busca  
ainda está muito grande. O que pode ser feito para otimizar  
esse processo?  
Caminhos pré-calculados.  
Custos pré-calculados.  
Caminhos Pré-Calculados  
Tabela pré-calculada com os melhores caminhos.  
Armazena-se somente o próximo nó que deve ser seguindo do nó  
atual ao nó destino.  
Custos Pré-Calculados  
Saber qual o melhor caminho entre dois nós somente é útil  
quando se sabe onde se deseja ir.  
Uma tabela pré-calculada com os custos de locomoção entre  
quaisquer dois nós também é uma informação muito util.  
Leitura Complementar  
Russell, S. and Norvig, P. Artificial Intelligence: a  
Modern Approach, 3nd Edition, Prentice-Hall,  
2009.  
Capítulo 4: Informed Search and Exploration